Graphe connexe

En théorie des graphes, un graphe non orienté est dit connexe s'il est d'un seul tenant.

Graphe connexe.

Graphe non connexe, avec trois composantes connexes.

Définitions

Un graphe non orienté ${\displaystyle G=(V,E)}$ est dit connexe si quels que soient les sommets ${\displaystyle u}$ et ${\displaystyle v}$ de ${\displaystyle V}$, il existe une chaîne reliant ${\displaystyle u}$ à ${\displaystyle v}$.

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

Pour un graphe orienté, on dit qu'il est :

• de faible connexité, si en oubliant l'orientation des arêtes, le graphe est connexe ;
• de connexité unilatérale, si pour toute paire de sommets (u, v), il existe un chemin orienté allant de u à v ou de v à u ;
• de forte connexité s'il existe un chemin orienté depuis tout sommet u vers tout sommet v.

Propriétés

• Une composante connexe d'un graphe est un sous-graphe connexe de ce graphe.
• Un arbre déconnecté est une forêt.
• Un graphe connexe à ${\displaystyle n}$ sommets possède au moins ${\displaystyle n-1}$ arêtes.
• Un graphe connexe à ${\displaystyle n}$ sommets ayant exactement ${\displaystyle n-1}$ arêtes est un arbre.
• Un graphe dont toutes les composantes connexes sont des arbres est une forêt.
• Un graphe à ${\displaystyle n}$ sommets avec ${\displaystyle k}$ composantes connexes possède au moins ${\displaystyle n-k}$ arêtes.
• Si on note ${\displaystyle L}$ la matrice laplacienne d'un graphe ${\displaystyle G}$, alors la multiplicité de la valeur propre 0 de ${\displaystyle L}$ est le nombre de composantes connexes de ${\displaystyle G}$.

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.

Complexité théorique

On s'intéresse à savoir si un graphe non orienté est connexe. Dès 1979, on savait qu'il était dans une classe probabiliste en espace logarithmique^[1]. Reingold, dans un article de 2008, a démontré que le problème d'accessibilité dans un graphe non orienté est dans LOGSPACE^[2], donc savoir si un graphe est connexe est aussi dans LOGSPACE. Quand on présente le graphe comme une union de cycles, le problème est NC¹-complet^[3].