4 – graphes d’un seul tenant, cycles¶

graphe d’un seul tenant¶

graphe d’un seul tenant: Un graphe sera dit d’un seul tenant si pour n’importe quel couple de nœud, et faisant abstraction de l’orientation des arrêtes, il existe un chemin reliant lesdits nœuds.

Dans l’exemple ci-dessous, il n’existe par exemple pas de chemin reliant a et e. Le graphe n’est pas d’un seul tenant.

graph mon_graphe {
   a -- b;
   b -- d;
   b -- c;
   e -- f
}

cycle: Une suite d’arrêtes consécutives dont les sommets extrémités sont identiques est appelé un cycle. [1]

Ici la suite b – c – d – b forme un cycle.

graph mon_graphe {
   a -- b;
   b -- d [color=red];
   b -- c [color=red];
   c -- d [color=red];
   b, c, d [color=red];
}

graphe acyclique: Une graphe dépourvu de cycle est appelé un graphe acyclique.

Notes

[1]	« Cycle (théorie des graphes). » Wikipédia, l’encyclopédie libre. 29 mai 2020, 07:18 UTC. 29 mai 2020, 07:18 <http://fr.wikipedia.org/w/index.php?title=Cycle_(th%C3%A9orie_des_graphes)&oldid=171423046>.