Qu’est-ce qu’un graphe connexe ?

Réponse courte

Un graphe non orienté est connexe si, pour toute paire de sommets, il existe une chaîne qui relie ces deux sommets. Autrement dit, on peut aller de n’importe quel sommet à n’importe quel autre en suivant les arêtes.

Comprendre

La définition par les chaînes

Une chaîne est une succession de sommets consécutifs reliés par une arête. Le graphe est connexe lorsque chaque paire de sommets peut être reliée par au moins une chaîne. La forme ou la disposition du dessin ne compte pas : seules les arêtes effectivement présentes déterminent les liaisons possibles.

Exemple et contre-exemple

Les arêtes AB, BC et CD forment un graphe connexe : de A à D, on suit A, B, C, D. En revanche, si les arêtes sont AB, BC, DE et EF, les sommets A, B, C forment une partie séparée de D, E, F. Ce second graphe n’est pas connexe, même si chacun de ses sommets a un voisin.

Tester la connexité

Pars d’un sommet, marque-le, puis marque ses voisins et les voisins nouvellement atteints. Répète jusqu’à ce qu’aucun sommet nouveau ne s’ajoute. Si tous les sommets ont été marqués, le graphe est connexe ; sinon, il ne l’est pas. Les groupes isolés ainsi repérés sont ses composantes connexes.

Exemples

  • Avec AB, BC et CD, la chaîne A, B, C, D relie A à D ; les quatre sommets sont dans un même graphe connexe.
  • Avec AB, BC, DE et EF, aucune chaîne ne relie A à F : le graphe a deux composantes et n’est pas connexe.

Pièges fréquents

  • Croire qu’un graphe est connexe parce que chaque sommet a au moins un voisin : deux groupes peuvent rester séparés.
  • Prendre un croisement de traits pour une liaison : un croisement ne crée un sommet que s’il est explicitement représenté comme tel.

Et maintenant ?

Questions proches

← Toutes les questions-réponses