Cheminements particuliers (hamiltoniens et eulériens)
On considère ici des cheminements particuliers où on refuse de passer plusieurs fois par le même point ou par le même arc tout en visitant une et une seule fois chaque point ou chaque arc.
On s'intéresse bien sûr aux graphes particuliers où ce type de cheminement est possible.
CHEMINS, CIRCUITS, CHAINES HAMILTONIENS ET EULERIENS
Définitions successives des notions de chemins, circuits et chaînes hamiltoniens et eulériens.
CHEMINS
D'abord les chemins.
Définition : Chemin élémentaire (rappel)
Un chemin xo, x1, ..., xp est élémentaire s'il ne passe pas deux fois par le même point (on ne peut avoir xi=xj si i et j sont différents).
Définition : Chemin hamiltonien
Un chemin élémentaire est hamiltonien s'il passe par tous les points du graphe.
Un chemin hamiltonien passe donc une et une seule fois par tout point du graphe ; si le graphe possède n points, un chemin hamiltonien contient exactement n-1 arcs.
Il n'est pas toujours possible de trouver un chemin hamiltonien dans un graphe.
Il est bien sûr toujours possible de trouver un chemin hamiltonien dans un graphe complet au sens des arcs puisque tous les arcs existent.
Dans le graphe ci-dessus, on parcourt un chemin hamiltonien en partant du point 1 et en suivant le numéro des flèches pour terminer au point 2.
Définition : Chemin simple (rappel)
Un chemin U1, U2, ..., Up est simple s'il ne passe pas deux fois par le même arc (on ne peut avoir Ui=Uj si i et j sont différents).
Définition : Chemin eulérien
Un chemin simple est eulérien s'il passe par tous les arcs du graphe.
Exemple le plus connu de chemin eulérien
Le graphe comporte 5 points. L'existence des arcs est indiquée par les flèches blanches.
Le chemin eulérien commence au point 3 et se termine au point 4.
Les numéros sur les arcs indiquent dans quel ordre ils sont visités.
Un chemin eulérien passe donc une et une seule fois par tous les arcs du graphe ; si le graphe possède m arcs, un chemin eulérien contient exactement m arcs.
Il n'est pas toujours possible de trouver un chemin eulérien dans un graphe.
Un graphe est dit eulérien s'il possède un chemin eulérien.
Remarque :
Un chemin hamiltonien n'est en général pas eulérien (c'est le cas pour l'exemple donné ci-dessus où des arcs du graphe ne font pas partie du chemin hamiltonien).
Un chemin eulérien n'est en général pas hamiltonien (c'est le cas pour l'exemple donné ci-dessus où le chemin eulérien passe plusieurs fois par certains points).
Une exception : si le graphe n'est constitué que d'un seul chemin hamiltonien de n-1 arcs, alors ce chemin hamiltonien est également eulérien.
Ce graphe correspond à l'exception signalée ci-dessus où le graphe est constitué du seul chemin hamiltonien qui est en même temps eulérien.
CIRCUITS
Mêmes définitions pour les circuits.
Définition : Circuit élémentaire
Un circuit est élémentaire s'il passe au plus une fois par un point.
Définition : Circuit hamiltonien
Un circuit élémentaire est hamiltonien s'il passe par tous les points du graphe.
Un circuit hamiltonien passe donc une et une seule fois par tout point du graphe ; si le graphe possède n points, un circuit hamiltonien contient exactement n arcs.
Il n'est pas toujours possible de trouver un circuit hamiltonien dans un graphe.
Il est bien sûr toujours possible de trouver un circuit hamiltonien dans un graphe complet au sens des arcs puisque tous les arcs existent.
On part de n'importe quel point et on revient à ce point en passant une fois et une seule par tous les points. De manière arbitraire, nous avons numéroté les arcs du circuit en partant du point 1.
Définition : Circuit pré-hamiltonien
Un circuit est pré-hamiltonien s'il passe par tous les points d'un graphe.
Un circuit pré-hamiltonien n'étant pas obligatoirement élémentaire, il passe par tous les points d'un graphe, mais peut y passer plusieurs fois.
Un circuit pré-hamiltonien peut être eulérien ou ne pas être eulérien s'il ne visite pas certains arcs ou s'il les visite plusieurs fois.
Un circuit hamiltonien est obligatoirement pré-hamiltonien.
Il y a plus de graphes qui contiennent des circuits pré-hamiltoniens que de graphes qui contiennent des circuits hamiltoniens. On peut donc se contenter de circuits pré-hamiltoniens lorsqu'il existe un chemin de tout point x à tout point y, mais qu'il n'existe pas de circuits hamiltoniens et que l'on veut visiter tous les points d'un graphe.
Remarque :
Les circuits hamiltoniens et pré-hamiltoniens sont liés au problème dit du « voyageur de commerce » dans lequel on doit visiter un ensemble de villes (représentées par les sommets d'un graphe) en passant si possible une et une seule fois par chaque ville, de sorte à construire une tournée partant d'une ville de départ et revenant à cette ville.
Définition : Circuit simple
Un circuit est simple s'il ne passe pas deux fois par le même arc.
Définition : Circuit eulérien
Un circuit simple est eulérien s'il passe par tous les arcs du graphe.
Un circuit eulérien passe donc une et une seule fois par tous les arcs du graphe ; si le graphe possède m arcs, un circuit eulérien contient exactement m arcs.
Il n'est pas toujours possible de trouver un circuit eulérien dans un graphe.
Exemple le plus connu de circuit eulérien
Il s'agit d'un graphe de 6 points numérotés de 1 à 6 (inscrits sur des carrés blancs). L'existence des arcs est indiquée par les flèches blanches.
Les numéros à l'intérieur de ces flèches indiquent dans quel ordre il faut visiter les arcs de manière à obtenir un circuit hamiltonien.
Définition : Circuit pré-eulérien
Un circuit est pré-eulérien s'il passe par tous les arcs d'un graphe.
Un circuit pré-eulérien n'étant pas obligatoirement simple, il passe par tous les arcs d'un graphe, mais peut y passer plusieurs fois.
Un circuit eulérien est obligatoirement pré-eulérien.
Il y a plus de graphes qui contiennent des circuits pré-eulériens que de graphes qui contiennent des circuits eulériens.
On peut donc se contenter de circuits pré-eulériens lorsqu'il existe un chemin de tout point x à tout point y, mais qu'il n'existe pas de circuits eulériens et que l'on veut visiter tous les arcs d'un graphe.
Remarque :
Un circuit hamiltonien n'est en général pas eulérien (c'est le cas pour l'exemple de circuit hamiltonien fourni ci-dessus où certains arcs ne sont pas visités).
Un circuit eulérien n'est en général pas hamiltonien (c'est le cas pour l'exemple de circuits eulériens ci-dessous où on visite plusieurs fois certains points).
Une exception : si le graphe n'est constitué que d'un seul circuit hamiltonien de n arcs, alors ce circuit hamiltonien est également eulérien ; il passe une et une seule fois par chaque point et une et une seule fois par chaque arc.
Ce graphe correspond à l'exception signalée ci-dessus où le graphe est constitué du seul circuit hamiltonien qui est en même temps eulérien.
Remarque :
Les circuits eulériens et pré-eulériens sont liés aux problèmes dits du "postier chinois" qui doit distribuer du courrier ou collecter de la marchandise le long de tous les arcs d'un réseau.
CHAINES
On travaille maintenant sur les graphes non orientés ou sur des graphes orientés en oubliant le sens des arcs.
Définition : Graphe symétrisé d'un graphe (rappel)
Le graphe symétrisé d'un graphe G est obtenu par l'union du graphe G et de son graphe inverse (obtenu en changeant le sens de tous ses arcs).
Définition : Chaîne
Une chaîne est un chemin d'un graphe non orienté ou du graphe symétrisé d'un graphe orienté.
C'est une suite de points telle qu'entre deux points successifs xp et xp+1 il existe ou bien un arc de xp à xp+1 ou bien de xp+1 à xP.
Définition : Extension des notions sur les chemins aux chaînes.
Une chaîne du graphe G est élémentaire si le chemin correspondant du graphe symétrisé est élémentaire.
Une chaîne élémentaire ne passe pas deux fois par le même point.
Une chaîne du graphe G est hamiltonienne si le chemin correspondant du graphe symétrisé est hamiltonien.
Une chaîne hamiltonienne passe une et une seule fois par tous les points d'un graphe.
Une chaîne du graphe G est simple si le chemin correspondant du graphe symétrisé est simple (en ne faisant correspondre qu'un seul arc à toute arête).
ATTENTION : Une chaîne simple ne passe pas deux fois par la même arête et non pas par le même arc.
Une chaîne du graphe G est eulérienne si le chemin correspondant du graphe symétrisé est eulérien (en ne faisant correspondre qu'un seul arc à toute arête).
Une chaîne eulérienne passe une fois et une seule par chaque arête.
Remarque :
Dans ce qui précède sur les chaînes et dans ce qui suit sur les cycles, nous ne présentons aucun exemple de représentation graphique de ces notions, car il suffit d'ôter les flèches sur les arcs non visités et de conserver les flèches avec les numéros de l'ordre de visite des arêtes sur les exemples précédemment donnés pour obtenir des exemples pour les chaînes et les cycles.
Cela n'aurait pas été le cas pour les chaînes et les cycles eulériens si dans les chemins et dans les circuits eulériens nous avions mis un arc de x à y et un arc de y à x qui serait parcouru obligatoirement dans les deux sens pour les chemins et les circuits, l'arête est alors parcouru deux fois alors qu'elle ne peut l'être qu'une seule fois pour les chaînes et les cycles.
Définition : Cycle
Une chaîne allant de xo à xo est un cycle si deux arêtes successives ne sont pas identiques.
Selon les problèmes, on peut définir également la chaîne vide (sans arête) allant de xo à xo comme un cycle.
Ce n'est pas le cas lorsque l'on considère qu'un graphe est sans cycle.
Définition : Extension des définitions précédentes aux cycles
Un cycle est élémentaire, hamiltonien, simple ou eulérien si le circuit du graphe symétrisé possède cette propriété (en ne faisant correspondre qu'un seul arc à toute arête).
