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) :


{G_{5}:} un graphe non orienté connexe {G_{6}:} deux composantes connexes
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres