Connexité des graphes

13.3.1 Connexité des graphes non orientés

Soit {G(S,A)} un graphe non orienté :

  • on dit que deux sommets {s} et {s^{\prime }} sont connectés s’il existe un chemin de {G} reliant {s} et {s^{\prime };}

on définit ainsi une relation d’équivalence sur l’ensemble {S} des sommets de {G.}

  • la composante connexe d’un sommet {\sigma} est le graphe {G_{\sigma }=(S_{\sigma },A_{\sigma })} formé de la classe {S_{\sigma }} des sommets de {G} qui sont connectés à {\sigma} et de l’ensemble {A_{\sigma }} des arêtes {\left\{s^{\prime },s^{\prime \prime }\right\}} avec {s^{\prime }} et {s^{\prime \prime }} dans {S_{\sigma };}

tous les sommets qui sont connectés à un sommet {\sigma} ont bien sûr la même composante connexe que {\sigma .}

  • on dit que le graphe (non orienté{)G=(S,A)} est un graphe connexe s’il possède une seule composante connexe ;
  • a contrario, dire que {G(S,A)} n’est pas connexe, c’est dire qu’il existe au moins deux sommets {s,s^{\prime }} non connectés dans {G.}
  • chacune des composantes connexes d’un graphe non orienté {G} constitue à elle seule un graphe connexe.

On voit à gauche l’exemple d’un graphe {G_{5}} connexe, puis celui d’un graphe {G_{6}} non connexe (il a suffi de retirer une arête au graphe {G_{5}:} le graphe {G_{6}} possède alors deux composantes connexes) :

Figure du chapitre 13, page 4
Figure du chapitre 13, page 4

{G_{5}:} un graphe non orienté connexe {G_{6}:} deux composantes connexes

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :