graphe connexe

Imaginez cinq villes reliées par des routes. Si un voyage reste possible entre deux villes quelconques, quitte à traverser plusieurs étapes, le réseau forme un graphe connexe. Une route directe entre chaque paire n'est pas nécessaire.

Si certaines villes restent coupées des autres, le graphe se partage en composantes connexes. Chacune est un îlot dans lequel tous les sommets communiquent, sans arête vers les autres îlots.

Un graphe non orienté est connexe si, pour toute paire de sommets, une chaîne relie le premier au second. Une chaîne est une succession d'arêtes consécutives : son existence compte, et non la forme du dessin ni la présence d'une arête directe.

Dans un graphe non connexe, une composante connexe est un sous-graphe connexe maximal : on ne peut lui ajouter aucun sommet du graphe tout en conservant sa connexité. Les composantes sont disjointes par leurs sommets, ne sont reliées par aucune arête et forment une décomposition unique du graphe.

Pour un graphe orienté, la connexité faible s'obtient en oubliant le sens des arcs, puis en testant la connexité du graphe non orienté obtenu. La forte connexité exige davantage : pour toute paire ordonnée de sommets, un chemin orienté doit mener du premier au second en respectant le sens de chaque arc.

Un graphe comporte des sommets, qui représentent les objets, et des arêtes, qui relient certaines paires de sommets. Des arêtes consécutives composent une chaîne. La connexité dépend de l'existence de telles chaînes entre toutes les paires, pas de la longueur des chaînes.

Les sommets accessibles les uns depuis les autres se regroupent en composantes connexes. Ajouter une arête entre deux composantes les réunit ; supprimer une arête peut au contraire séparer une composante. La position, la couleur ou la taille des sommets dans un dessin ne changent rien : seules les relations d'adjacence, et le sens des arcs dans un graphe orienté, interviennent. Ces données suffisent à rechercher les composantes et à décider si le graphe est connexe.

Considérons cinq sommets A, B, C, D et E. Les arêtes sont AB, AC, BC, CD et DE. La figure matérialise exactement ces cinq relations.

1. Partons de A. Les arêtes AB et AC donnent directement accès à B et C.
2. Depuis C, l'arête CD permet d'atteindre D.
3. Depuis D, l'arête DE permet enfin d'atteindre E.

Les cinq sommets sont donc accessibles depuis A. Comme les arêtes ne sont pas orientées, chaque trajet peut être parcouru en sens inverse : deux sommets quelconques sont reliés en passant au besoin par A. Le graphe est connexe. Pour contrôler le verdict, supprimons mentalement CD : le triangle A-B-C et la paire D-E deviennent alors deux composantes connexes.

Pour tester un graphe non orienté, choisissez un sommet et parcourez toutes les arêtes accessibles, sans oublier les nouveaux sommets rencontrés. Si chaque sommet a été visité, le graphe est connexe ; sinon, recommencez depuis un sommet non visité pour obtenir une autre composante.

Dans un réseau, ce test repère les groupes isolés. Une simple inspection du dessin est moins fiable lorsque des arêtes se croisent sans créer de sommet : il faut suivre les extrémités effectivement déclarées.

Pour un graphe orienté, choisissez d'abord le bon critère. Oubliez les flèches si seule la connexité faible importe ; conservez leur sens et contrôlez les trajets dans les deux directions si la forte connexité est recherchée.

Graphe connexe et graphe complet. Dans un graphe complet, chaque paire de sommets est reliée par une arête directe. Un graphe connexe demande seulement une chaîne. L'exemple A-B-C-D-E est connexe, mais A et E ne sont pas adjacents : il n'est donc pas complet.

Connexité et chaîne eulérienne. La connexité demande si tous les sommets peuvent se rejoindre. Une chaîne eulérienne impose de parcourir chaque arête exactement une fois. L'exemple admet le parcours E-D-C-A-B-C, mais cette réussite vient de la répartition des degrés, pas de la seule connexité. Si l'on ajoute l'arête AD, le graphe reste connexe mais possède quatre sommets de degré impair ; il n'admet plus de chaîne eulérienne.

Un sommet seul. Un graphe réduit à un sommet est connexe : la condition est satisfaite sans arête, grâce à la chaîne de longueur nulle reliant ce sommet à lui-même. Pour le graphe vide, sans sommet, les conventions peuvent varier ; il faut annoncer celle qui est retenue.

Une arête dessinée qui croise une autre. Un croisement n'est pas un sommet s'il n'est pas explicitement marqué. Il ne crée alors aucune nouvelle chaîne ; le verdict doit suivre la liste des extrémités, non l'apparence du tracé.

Un graphe orienté accessible dans un seul sens. Un trajet de A vers B ne fournit pas automatiquement un trajet de B vers A. Pour conclure à la forte connexité, il faut tester l'accessibilité pour chaque paire ordonnée ; oublier les flèches ne prouve que la connexité faible.

Une arête décisive. Dans l'exemple, CD est l'unique liaison entre le triangle A-B-C et la paire D-E. Sa suppression suffit à rendre le graphe non connexe, tandis que supprimer AB laisse encore la chaîne A-C-B. Il faut donc refaire le parcours après toute modification.

La notion de sous-graphe précise la structure dans laquelle se forme chaque composante connexe.

La chaîne eulérienne ajoute une autre contrainte : parcourir chaque arête exactement une fois, et pas seulement relier les sommets.

L'article Balades dans le graphe divisoriel prolonge l'idée de parcours sur un graphe construit à partir de relations arithmétiques.