Chaînes et cycles
Chaînes et cycles
Une chaîne dans G, est une suite de la forme (v0, e1, v1, e2, ..., vk-1, ek, vk) ayant pour éléments alternativement des sommets (vi) et des arêtes (ei), commençant et se terminant par un sommet, et telle que les extrémités de ei soient vi-1 et vi, i = 1, ..., k.
Si v0 = a et vk = b, on dira que la chaîne relie a et b. En plus, on dira que la chaîne a longueur k (c'est le nombre d'arêtes de la chaîne). Une chaîne doit comporter au moins une arête.
Le graphe ci-contre contient par exemple les chaînes (v1, e3, v3, e4 ,v4) et (v4, e4, v3, e2, v2, e1, v1).
On ne change pas une chaîne en inversant l'ordre des éléments dans la suite correspondante, ainsi les chaînes (v1, e3, v3, e4, v4) et (v4, e4, v3, e3, v1) sont identiques.
On appelle distance entre deux sommets la longueur de la plus petite chaîne les reliant.
On appelle diamètre d'un graphe la plus longue des distances entre deux sommets.
Une chaîne est élémentaire si chaque sommet y apparaît au plus une fois.
Une chaîne est simple si chaque arête apparaît au plus une fois. Dans le graphe ci-dessus, (v1, e1, v2, e2, v3) est une chaîne simple et élémentaire.
Une chaîne telle que v0 = vk est appelée chaîne fermée. Dans le graphe ci-dessus, (v2, e2, v3, e4, v4, e4, v3, e2, v2) est une chaîne fermée.
Une chaîne fermée simple est appelée cycle si seul le sommet de départ apparaît deux fois dans la chaîne. Dans le graphe ci-dessus, (v2, e2, v3, e4, v4, e5, v2) est un cycle.
Théorème 1Pour tout graphe ayant m arêtes, n sommets et p composantes connexes, on a :
de plus, n(G) = 0 si et seulement si G est sans cycles. |
Dans certains livres, on définit une chaîne comme une suite de sommets. Dites pourquoi cette définition n'est pas tout à fait correcte.
Quel est le diamètre du graphe ci-contre ?
Combien d'arêtes (et lesquelles) faut-il enlever pour que son diamètre soit de 3 ?
Quels sont les graphes de diamètre 1 ?
| Les corrigés sont disponibles, mais seulement pour les visiteurs autorisés! |
   |
 Didier
Müller, 14.9.06 |