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 ---- .. code-block:: dot graph mon_graphe { a -- b; b -- d; b -- c; e -- f } (`voir en ligne `_) représentation graphique ------------------------ .. image:: 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**. [#wikipedia-cycle]_ Ici la chaîne b -- c -- d -- b forme un cycle. code ==== .. code-block:: dot 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 ======================== .. image:: images/cycle.svg graphe acyclique **************** graphe acyclique Une graphe dépourvu de **cycle** est appelé un graphe acyclique. ---- .. rubric:: Notes .. [#wikipedia-cycle] "Cycle (théorie des graphes)." Wikipédia, l'encyclopédie libre. 29 mai 2020, 07:18 UTC. 29 mai 2020, 07:18 .