TD6

Exercice 1

Voici la liste d’adjacence d’un graphe.

• [9]: les sommets du graphe
• Le dessiner
  1 \rightarrow (1, 3, 5, 7)
  2 \rightarrow (1, 4, 6, 9)
  3 \rightarrow (4, 6, 9)
  4 \rightarrow (7)
  5 \rightarrow (3, 4, 5)
  6 \rightarrow (1, 9)
  7 \rightarrow (3, 4, 7)
  8 \rightarrow ()
  9 \rightarrow (5, 7)

Exercice 2

Ce graphe est-il sans circuit ?

Exercice 3

Dans quel ordre visite-t-on les sommets si on effectue un parcours en profondeur de ce graphe à partir de 2 (ordre de numérotation).

Exercice 4

Soit G un graphe, que peut-on dire de G si \forall\ p parcours en profondeur de G toutes revisites d’un sommet s a lieu après sa post-visite.

Exercice 5

• Un sommet peut-il être revisité plusieurs fois ?
• Un sommet peut-il être post-visité plusieurs fois ?
• Un sommet peut-il être pré-visité plusieurs fois ?

Exercice 6

Soit G, si :

• \forall\ p parcours de G aucun sommet n’est revisité que peut-on dire de G
• il y a un sommet qui peut attendre tous les autres