TD

Exercice 1: vocabulaires

Sur les deux graphes ci-dessous:

flowchart LR F((F)) --- D((D)) D --- E((E)) D --- C((C)) E --- B((B)) C --- B E --- A((A)) B --- A F --- A E --- F D --- G((G)) G --- B

flowchart RL F((F)) --> D((D)) E((E)) --> D D --> C((C)) E --> B((B)) C --> B E --> A((A)) E --> F D --> G((G)) G --> B A --> A

1. Donner l'ordre.
2. Donner le nombre d'arêtes ou d'arcs.
3. Donner les sommets adjacents à A
4. Donner le degré du sommet A
5. Donner trois chemins allant de E à B

Exercice 2: modélisation

Modéliser par un graphe les situations suivantes (que représentent les sommets et les arrêtes (ou arcs)):

1. Réseau routier
2. Boggle
3. Labyrinthe

Exercice 3: représentations

1. Soit le graphe suivant:

   flowchart RL
   A((1)) --- B((2))
   B --- B
   B --- C((3))
   B --- D((4))

   1. Donner le liste d'adjacence de ce graphe
   2. Donner la matrice d'adjacence de ce graphe

2. Soit la matrice d'adjacence suivante:

   \({\begin{pmatrix}1&1&1&0&1\\0&0&1&1&0\\1&0&0&1&0\\0&1&0&1&1\\0&1&0&0&0\\\end{pmatrix}}\)

   1. Donner le diagramme de ce graphe
   2. Donner le liste d'adjacence de ce graphe

Exercice 4: utilisation d'une interface

En utilisant l'interface du cours, écrire un programme permettant de créer le graphe correspondant au diagramme suivant:

flowchart RL
F((F)) --> D((D))
E((E)) --> D
D --> C((C))
E --> B((B))
C --> B
E --> A((A))
E --> F
D --> G((G))
G --> B
A --> A