Composante connexe (théorie des graphes)

Un graphe à trois composantes connexes

En théorie des graphes, une composante connexe d'un graphe non orienté est un sous-graphe connexe qui ne fait partie d'aucun sous-graphe connexe plus grand. Les composantes connexes de tout graphe divisent ses sommets en ensembles disjoints et sont les sous-graphes induits de ces ensembles. Un graphe connexe a exactement une composante connexe, constituée du graphe entier.

Le nombre de composantes connexes dans un graphe donné est un invariant important du graphe et est étroitement lié aux invariants des matroïdes, des espaces topologiques et des matrices. Dans les graphes aléatoires, un phénomène fréquent est l'existence d'une composante connexe géante, nettement plus grande que les autres, et d'un seuil de percolation, une densité d'arêtes limite au-dessus de laquelle une composante géante apparaît et en dessous de laquelle elle n'existe pas.

Les composantes connexes d'un graphe peuvent être construites en temps linéaire.

Définitions et exemples

Une composante connexe d'un graphe non-orienté peut être définie comme un sous-graphe connecté qui n'est inclus dans aucun sous-graphe connecté plus grand. Par exemple, le graphe représenté sur l'illustration ci-dessus contient trois composantes connexes. Chaque sommet d'un graphe appartient à l'une de ses composantes connexes, qui est le sous-graphe induit de l'ensemble des sommets atteignables à partir de ce sommet. Tout graphe est constitué de l'union disjointe de ses composantes connexes.

Les exemples suivants illustrent différents cas particuliers de composantes connexes :

• Dans un graphe nul, chaque sommet constitue une composante connexe comportant un seul sommet et zéro arête. Plus généralement, une composante connexe de ce type est présente pour chaque sommet isolé dans un graphe.
• Dans un graphe connexe, il y a une seule composante connexe composée du graphe entier.

• Dans une forêt, chaque composante connexe est un arbre.

Algorithmes

La recherche des composantes connexes d'un graphe est un problème classique qui peut être résolu en temps linéaire (en fonction du nombre de sommets et d'arêtes du graphe). On peut utiliser pour cela soit un algorithme de parcours en profondeur, soit un algorithme de parcours en largeur. Dans un cas comme dans l'autre, la recherche démarre sur un sommet quelconque du graphe et va identifier toute la composante connexe qui le contient une fois le parcours terminé. Il suffit alors de réitérer une recherche en profondeur ou en largeur à partir d'un sommet qui n'a pas encore été parcouru pour identifier progressivement toutes les composantes connexes.