112
Recherche opérationnelle
Si l'on étudie à présent des graphes non orientés, on peut définir des notions analogues :
Une chaîne est une suite d'arêtes telle que chacune d'elles est rattachée à la précédente
par une extrémité et à la suivante par l'autre extrémité (sauf la dernière).
Une chaîne qui se referme sur elle-même est un cycle.
Une chaîne peut être simple ou élémentaire, ou encore hamiltonienne. On définira les
mêmes termes pour un cycle.
Une chaîne eulérienne est une chaîne qui utilise toutes les arêtes du graphe une fois et
une seule fois; c'est un cycle eulérien si elle revient à son point de départ.
Exemple : si l'on supprime les orientations du graphe précédent, on obtient, en
numérotant les arêtes :
Figure 6
La suite (1, 2, 8, 6 ) constitue une chaîne simple et élémentaire.
(3, 6, 8, 2 ) constitue un cycle élémentaire et simple.
(2,8,7,5,4,1) constitue un cycle hamiltonnien.
6.2.6. Connexité. Forte connexité
Considérons un graphe sans orientation; il est connexe si toute paire de sommets
distincts est reliée par au moins une chaîne.
Soit la relation :
si et sont reliés par au moins une chaîne avec et
; il est clair que est
une relation d'équivalence.
On peut donc décomposer
en classes d'équivalence suivant la relation . Si l'on
considère le sous-graphe correspondant à une classe d'équivalence, ce sous-graphe
constitue une composante connexe de . Si
et
sont deux composantes connexes, il
n'existe aucune arête reliant un sommet de à un sommet de ;