Composante connexe (théorie des graphes)

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.

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^[1].

• Portail des mathématiques