composante connexe d'un graphe

Imaginez des points reliés par des traits. En partant d’un point et en suivant autant de traits que nécessaire, vous atteignez certains points, mais peut-être pas tous. Le groupe entier ainsi accessible forme une composante connexe.

Deux groupes séparés appartiennent à deux composantes différentes. Un point sans aucun trait constitue à lui seul une composante : il est déjà relié à lui-même par un chemin sans arête.

Dans un graphe non orienté nommé G, une composante connexe est le sous-graphe induit par un ensemble de sommets qui sont tous reliés deux à deux par des chemins, et qui est maximal pour cette propriété. « Induit » signifie que l’on conserve toutes les arêtes de G dont les deux extrémités appartiennent à cet ensemble. « Maximal » signifie qu’aucun autre sommet de G ne peut être ajouté tout en gardant le sous-graphe connexe ; cela ne signifie pas que la composante est la plus grande du graphe.

La relation « être relié par un chemin » regroupe chaque sommet avec tous ceux qu’il peut atteindre. Ces groupes sont disjoints et couvrent tous les sommets : ils forment une partition de l’ensemble des sommets. Ainsi, un graphe connexe possède exactement une composante connexe.

Dans un graphe orienté, la variante faible ignore le sens des arcs. La variante forte exige, pour deux sommets quelconques de la composante, un chemin orienté du premier vers le second et un autre en sens inverse. Les deux découpages peuvent donc être différents.

Une composante repose sur quatre éléments. Les sommets sont les objets regroupés. Les arêtes permettent de passer d’un sommet au suivant. Un chemin est une suite d’arêtes qui rend deux sommets accessibles l’un depuis l’autre. Enfin, le sous-graphe induit conserve tous les sommets du groupe et toutes les arêtes du graphe qui les relient entre eux.

Les chemins dépendent des arêtes, et l’ensemble des sommets accessibles détermine à son tour le sous-graphe induit. La maximalité ferme le groupe : toute arête vers un sommet extérieur ferait entrer ce sommet dans la même composante. La position des points, la longueur des traits et leurs croisements sur un dessin ne changent pas ce découpage. Ces données suffisent à construire toutes les composantes du graphe.

Considérons les sept sommets A, B, C, D, E, F et G. Les arêtes sont A–B, A–C, B–C, C–D et E–F. Le sommet G n’a aucune arête. Le dessin correspondant permet de contrôler chaque liaison sans dépendre de la position des points.

1. Partons de A. Les arêtes mènent directement à B et C, puis C mène à D. Le premier groupe accessible est donc {A, B, C, D}.

2. Prenons ensuite E, qui n’appartient pas au premier groupe. Il rejoint F et aucun autre sommet : le deuxième groupe est {E, F}.

3. Il reste G. Le chemin de longueur nulle relie G à lui-même, donc {G} est la troisième composante.

Le graphe possède exactement trois composantes connexes. Pour contrôler le résultat, chaque sommet apparaît une seule fois dans les trois groupes et aucune arête ne relie deux groupes distincts.

Pour inventorier les composantes d’un graphe, on choisit un sommet encore non visité et on lance un parcours en largeur ou en profondeur. Tous les sommets atteints reçoivent le même numéro de composante. On recommence avec un sommet non visité jusqu’à épuisement.

Dans un réseau de transport non orienté, ce découpage repère les groupes de stations entre lesquelles un trajet reste possible. Si le sens de circulation compte, il faut préférer les composantes fortement connexes ; le critère observable est la possibilité d’effectuer aussi le trajet retour.

Dans un réseau informatique, les composantes révèlent des îlots séparés après la suppression de liaisons. Si l’objectif est seulement de tester si tout le réseau reste d’un seul tenant, un unique parcours depuis un sommet suffit : le graphe est connexe exactement lorsque tous les sommets sont visités.

Une composante connexe est l’un des blocs maximaux d’un graphe ; un graphe connexe est un graphe réduit à un seul de ces blocs. Dans l’exemple, {A, B, C, D} est une composante, mais le graphe entier ne l’est pas puisqu’il en possède trois.

Une arête relie directement deux sommets, tandis qu’un chemin peut en enchaîner plusieurs. A et D appartiennent à la même composante sans arête A–D, car A–C–D est un chemin. Exiger une liaison directe entre chaque paire décrirait une propriété plus forte que la connexité.

Un sommet isolé n’est pas oublié : il forme une composante à un sommet. Le symptôme du piège est qu’il reste hors de tous les groupes après le parcours des arêtes ; il faut alors l’ajouter comme composante singleton.

« Maximal » ne veut pas dire « de taille maximale ». Dans l’exemple, {G} est maximalement connexe même si {A, B, C, D} contient davantage de sommets. Il faut vérifier l’impossibilité d’ajouter un sommet, et non comparer les tailles.

Dans un graphe orienté, annoncer seulement des « composantes connexes » laisse le critère ambigu. Si l’on efface les flèches, on calcule les composantes faibles. Si chaque paire doit rester accessible dans les deux sens en suivant les flèches, on calcule les composantes fortement connexes.

Un graphe sans sommet possède zéro composante, puisque la partition de son ensemble de sommets est vide. Selon les conventions, ce graphe vide peut être exclu de la classe des graphes connexes ; il faut donc annoncer la convention avant d’utiliser ce cas charnière.

La fiche graphe connexe approfondit le cas où tous les sommets appartiennent à une seule composante.

La notion de Sous-graphe précise comment sélectionner des sommets et des arêtes, notamment dans le cas induit utilisé ici.

La partition d’un ensemble formalise le découpage des sommets en groupes disjoints qui couvrent tout le graphe.