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 <https://dreampuf.github.io/GraphvizOnline/#graph%20mon_graphe%20%7B%0A%20%20%20a%20--%20b%3B%0A%20%20%20b%20--%20d%3B%0A%20%20%20b%20--%20c%3B%0A%20%20%20e%20--%20f%0A%7D%0A>`_)

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 <https://dreampuf.github.io/GraphvizOnline/#graph%20mon_graphe%20%7B%0A%20%20%20a%20--%20b%3B%0A%20%20%20b%20--%20d%20%5Bcolor%3Dred%5D%3B%0A%20%20%20b%20--%20c%20%5Bcolor%3Dred%5D%3B%0A%20%20%20c%20--%20d%20%5Bcolor%3Dred%5D%3B%0A%0A%20%20%20b%2C%20c%2C%20d%20%5Bcolor%3Dred%5D%3B%0A%7D%0A>`_)

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 <http://fr.wikipedia.org/w/index.php?title=Cycle_(th%C3%A9orie_des_graphes)&oldid=171423046>.