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 arêtes, il existe un chemin reliant lesdits nœuds.

contre-exemple

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.

code

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

(voir en ligne)

représentation graphique

../../../_images/non-d-un-seul-tenant.svg

cycles

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

Ici la chaîne b – c – d – b forme un cycle.

code

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

(voir en ligne)

représentation graphique

../../../_images/cycle.svg

graphe acyclique

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

Notes