Graphe connexe

Cet article est une ébauche concernant les mathématiques. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Graphe connexe.

Graphe non connexe, avec trois composantes connexes.

En théorie des graphes, un graphe non orienté $G=(S,A)$ est dit connexe si quels que soient les sommets $u$ et $v$ de $S$, il existe une chaîne de $u$ vers $v$. C'est-à-dire, s'il existe une suite d'arêtes permettant d'atteindre $v$ à partir de $u$.

Un sous-graphe connexe maximal d'un graphe non orienté quelconque est une composante connexe de ce graphe.

Propriétés

Un graphe connexe à n sommets possède au moins n-1 arêtes. S'il en a exactement n-1, c'est un arbre.

Plus généralement, un graphe à n sommets avec k composantes connexes possède au moins n-k arêtes.

Algorithmes

L’algorithme de parcours en profondeur permet de déterminer si un graphe est connexe ou non. Dans le cas d'un graphe construit de façon incrémentale, on peut utiliser des algorithmes de connexité basés sur des pointeurs pour déterminer si deux sommets sont dans la même composante connexe.

Voir aussi

• Connexité 
• Composante connexe 
• Graphe fortement connexe, la notion équivalente pour les graphes orientés.
• Graphe arête-connexe
• Graphe sommet-connexe