Graphe hamiltonien

Une chaîne hamiltonienne est une chaîne qui passe une fois et une seule par chaque sommet du graphe.

Cycle hamiltonien

Un cycle hamiltonien est une chaîne hamiltonienne qui est cyclique.

On peut transformer un cycle hamiltonien en chaîne hamiltonienne, en enlevant une arête quelconque du cycle. En revanche, une chaîne hamiltonienne ne peut être étendue en un cycle hamiltonien que si ses extrémités sont adjacentes.

Un graphe qui contient un cycle hamiltonien est appelé graphe hamiltonien.

Un graphe semi-hamiltonien est un graphe qui contient une chaîne hamiltonienne, mais pas de cycle hamiltonien.

Un graphe est dit hamiltonien-connexe lorsque, pour toute paire de sommets du graphe, il existe une chaîne hamiltonienne entre ces sommets.

Une décomposition hamiltonienne d'un graphe est une partition de l'ensemble de ses arêtes en cycles hamiltoniens.

Un graphe hypohamiltonien est un graphe qui n'est pas hamiltonien, mais qui le devient lorsqu'on lui retire n'importe quel sommet.

• 
  Graphe non-hamiltonien
• 
  Graphe semi-hamiltonien
• 
  Graphe hamiltonien

Ce théorème est dû à Gabriel Andrew Dirac, en 1952[9]. Il s'énonce comme suit[10] :

Démonstration

Soit ${\displaystyle G=(V,E)}$ un graphe à ${\displaystyle n}$ sommets dont chaque sommet est au moins de degré ${\displaystyle {\frac {n}{2}}}$. On remarque d'abord qu'il est connexe. En effet, remarquons déjà que par hypothèse ${\displaystyle G}$ admet une composante connexe ${\displaystyle H}$ d'ordre supérieur à ${\displaystyle {\frac {n}{2}}+1}$ (un sommet choisi arbitrairement et ses sommets voisins). Supposons maintenant que ${\displaystyle G}$ ne soit pas connexe. Il admet une autre composante connexe ${\displaystyle H'=(V',E')}$ d'ordre inférieur à ${\displaystyle {\frac {n}{2}}-1}$ (les deux composantes étant disjointes, la somme des deux ordres des deux composantes ${\displaystyle H}$ et ${\displaystyle H'}$ est égale à ${\displaystyle n}$). Le degré des sommets de ${\displaystyle V'}$ est alors au maximum ${\displaystyle {\frac {n}{2}}-2}$, ce qui contredit les hypothèses de départ.

Considérons la plus longue chaîne ${\displaystyle P=(x_{0},x_{1},...,x_{k})}$ à sommets distincts de ${\displaystyle G}$, ou une des plus longues chaînes s'il y en a plusieurs.

Si ${\displaystyle x_{0}}$ et ${\displaystyle x_{k}}$ sont voisins, on construit le cycle ${\displaystyle C=(x_{0},x_{1},...,x_{k},x_{0})}$.

Si ${\displaystyle x_{0}}$ et ${\displaystyle x_{k}}$ ne sont pas voisins, comme la chaîne ne peut pas être étendue, tous les sommets voisins de son extrémité ${\displaystyle x_{0}}$ appartiennent eux aussi aux sommets de la chaîne ${\displaystyle P'=(x_{1},x_{2},...,x_{k-1})}$. Il y a donc au moins ${\displaystyle {\frac {n}{2}}}$ sommets voisins de ${\displaystyle x_{0}}$ qui appartiennent aux sommets de ${\displaystyle P'}$. De la même façon, il y a au moins ${\displaystyle {\frac {n}{2}}}$ sommets voisins de ${\displaystyle x_{k}}$ qui appartiennent aux sommets de la chaîne ${\displaystyle P'}$. ${\displaystyle P'}$ ayant au plus ${\displaystyle n-2}$ sommets, le principe des tiroirs permet d'en déduire qu'il existe ${\displaystyle i}$ entre ${\displaystyle 1}$ et ${\displaystyle k-2}$ tel que ${\displaystyle x_{i+1}}$ est le voisin de ${\displaystyle x_{0}}$ et ${\displaystyle x_{i}}$ est le voisin de ${\displaystyle x_{k}}$ (figure). D'un point de vue intuitif, il n'y a pas assez de place dans ${\displaystyle P'}$ pour que les voisins de ${\displaystyle x_{0}}$ restent éloignés des voisins de ${\displaystyle x_{k}}$.

Construction d'un cycle ${\displaystyle C}$ à partir de la plus longue chaîne ${\displaystyle P}$.

On construit le cycle ${\displaystyle C=(x_{0},x_{i+1},x_{i+2},...,x_{k},x_{i},x_{i-1},...,x_{1},x_{0})}$ (en rouge sur la figure).

Dans tous les cas, ${\displaystyle C}$ est hamiltonien.

En effet, supposons que ${\displaystyle C}$ ne soit pas hamiltonien. Il ne couvre donc pas tous les sommets de ${\displaystyle G}$. Soit ${\displaystyle K}$ l'ensemble (non vide) des sommets de ${\displaystyle G}$ qui ne figurent pas dans ${\displaystyle C}$. Comme ${\displaystyle G}$ est connexe, il existe ${\displaystyle x_{j}}$ dans ${\displaystyle C}$ et ${\displaystyle y}$ dans ${\displaystyle K}$ tels que ${\displaystyle \{x_{j},y\}}$ soit une arête du graphe. On peut alors ajouter ${\displaystyle y}$ à ${\displaystyle C}$ pour construire une chaîne plus longue que ${\displaystyle P}$ (illustration), ce qui contredit l'hypothèse selon laquelle ${\displaystyle P}$ était de longueur maximale.

Figure absurde : si ${\displaystyle C}$ n'était pas hamiltonien, on pourrait construire une chaîne plus longue que ${\displaystyle P}$.

Ce théorème est dû à Øystein Ore, en 1960[11]. Il s'énonce comme suit :

Le théorème de Dirac est un cas particulier du théorème de Ore : en effet, si chaque sommet est de degré au moins ${\displaystyle {\frac {n}{2}}}$, alors la somme des degrés de n'importe quelle paire de sommets, adjacents ou pas, est au moins ${\displaystyle n}$.

Démonstration

Notons ${\displaystyle P(n)}$ la propriété « la somme des degrés de n'importe quelle paire de sommets non adjacents vaut au moins n ».

Démontrer le théorème d'Ore revient au même de démontrer que tout graphe non-hamiltonien ${\displaystyle G}$ ne vérifie pas la propriété ${\displaystyle P(n)}$[12].

Soit ${\displaystyle G}$ un graphe non-hamiltonien à ${\displaystyle n}$ sommets (${\displaystyle n\geq 3}$). On remarque qu'en ajoutant des arêtes, on finit forcément par rendre n'importe quel graphe hamiltonien, puisque dans le cas extrême on arrive au graphe complet, qui est hamiltonien. On décide de construire un graphe ${\displaystyle G'}$ à partir de ${\displaystyle G}$ en ajoutant des arêtes sans former de cycle hamiltonien, jusqu'à ce que ce ne soit plus possible.

Soient ${\displaystyle u}$ et ${\displaystyle v}$ deux sommets non adjacents quelconques de ${\displaystyle G'}$. Comme l'ajout de ${\displaystyle \{u,v\}}$ à ${\displaystyle G'}$ formerait un cycle hamiltonien, les autres arêtes de ${\displaystyle G'}$ forment une chaîne hamiltonienne. Notons ${\displaystyle P=(x_{0},...,x_{k})}$ cette chaîne de ${\displaystyle n}$ sommets, avec ${\displaystyle k=n-1}$.

Soit ${\displaystyle i}$ un entier tel que ${\displaystyle 0\leq i\leq k-1}$. On s'intéresse aux éventuelles arêtes ${\displaystyle \{x_{0},x_{i+1}\}}$ et ${\displaystyle \{x_{k},x_{i}\}}$. ${\displaystyle G'}$ peut contenir au maximum une seule de ces deux arêtes, car sinon on pourrait construire le cycle hamiltonien ${\displaystyle C=(x_{0},x_{1},...,x_{i},x_{k},x_{k-1},...,x_{i+1},x_{0})}$ dans ${\displaystyle G'}$ (figure).

Construction d'un cycle ${\displaystyle C}$ à partir de la chaîne hamiltonienne ${\displaystyle P}$.

Le nombre total d'arêtes d'extrémité ${\displaystyle x_{0}}$ ou ${\displaystyle x_{k}}$ est donc au maximum égal au nombre de choix pour ${\displaystyle i}$, qui est ${\displaystyle n-1}$. En d'autres termes, ${\displaystyle deg(x_{0})+deg(x_{n})<n}$. ${\displaystyle G'}$ ne respecte donc pas la propriété ${\displaystyle P(n)}$.

On est passé de ${\displaystyle G}$ à ${\displaystyle G'}$ en ajoutant des arêtes : le degré des sommets de ${\displaystyle G}$ est donc inférieur ou égal au degré des sommets de ${\displaystyle G'}$. ${\displaystyle G}$ ne respecte donc pas non plus ${\displaystyle P(n)}$.

On doit à Lajos Pósa (en) plusieurs théorèmes sur les cycles hamiltoniens. On peut en particulier citer un théorème de 1962[13] - [14] qui porte sur les sommets faiblement connectés :

On remarque que la condition 2 est comprise dans la condition 1 quand ${\displaystyle n}$ est pair, et n'a donc d'intérêt que lorsque ${\displaystyle n}$ est impair.

Exemple d'application du théorème de Pósa.

Exemple d'application : le graphe ci-contre possède 6 sommets. Il est hamiltonien : les sommets ont été ordonnés de manière à mettre en évidence un cycle hamiltonien, c'est le cycle extérieur rouge ${\displaystyle H}$.

• Le théorème de Dirac ne permet pas de prouver qu'il est hamiltonien. Pour cela, tous les sommets devraient au moins être de degré ${\displaystyle 3}$, or il y a un sommet de degré ${\displaystyle 2}$.
• Le théorème de Ore n'est pas plus utile, car les sommets non adjacents ${\displaystyle a}$ et ${\displaystyle b}$ vérifient ${\displaystyle \mathrm {deg} (a)+\mathrm {deg} (b)=3+2=5}$, or on devrait avoir au moins ${\displaystyle 6}$.
• En revanche, le théorème de Pósa permet de déterminer que le graphe est hamiltonien, car il y a ${\displaystyle 0}$ sommet de degré ${\displaystyle 1}$ et ${\displaystyle 1}$ sommet de degré ${\displaystyle 2}$ : la condition 1 est remplie (${\displaystyle 0<1}$ et ${\displaystyle 0+1<2}$).

S'inspirant du théorème de Ore, John Adrian Bondy et Václav Chvátal ont trouvé en 1976[15] une méthode pour déterminer si un graphe est hamiltonien : tant qu'il reste des sommets ${\displaystyle u}$ et ${\displaystyle v}$ non adjacents tels que ${\displaystyle \mathrm {deg} (u)+\mathrm {deg} (v)\geq n}$, on ajoute l'arête ${\displaystyle \{u,v\}}$ au graphe. Quand on ne peut plus en ajouter, on a obtenu ce qu'on appelle la fermeture du graphe. On applique alors le théorème suivant :

En particulier, si la fermeture d'un graphe est le graphe complet, qui est hamiltonien, on est sûr que le graphe de départ est hamiltonien.

Graphe de départ	Étape intermédiaire	Fermeture du graphe de départ

Exemple d'application : considérons le graphe maison de la figure ci-contre. Il comprend 5 sommets.

• Le théorème de Dirac ne peut pas être utilisé, car le graphe maison comprend des sommets de degré ${\displaystyle 2<{\frac {5}{2}}}$.
• Pas mieux pour le théorème de Ore, car il existe des paires de sommets non adjacents de degré ${\displaystyle 2}$, donc vérifiant ${\displaystyle 2+2<5}$.
• Le théorème ne Pósa ne vient pas à la rescousse, car il y a trop de sommets de degré ${\displaystyle 2}$ (il y en a ${\displaystyle 3}$).
• En revanche, le théorème de Bondy et Chvátal permet de montrer que le graphe maison est hamiltonien.

Pour s'en assurer, on ajoute d'abord les arêtes en rouge entre les sommets de degré ${\displaystyle 2}$ et les sommets de degré ${\displaystyle 3}$. On ajoute ensuite les arêtes en vert entre le sommet de degré ${\displaystyle 2}$ et les sommets qui viennent de passer en degré ${\displaystyle 3}$. On obtient le graphe complet ${\displaystyle K_{5}}$, qui est hamiltonien, ce qui prouve que le graphe de départ l'était aussi.

Alain Ghouila-Houri a énoncé en 1960[16] le théorème suivant, qui est l'équivalent du théorème de Dirac pour les graphes orientés :

Il y a deux théorèmes équivalents au théorème de Ore dans le cas des graphes orientés.

Douglas R. Woodall a énoncé en 1972[17] le théorème suivant :

Henry Meyniel a énoncé en 1973[18] le théorème voisin suivant :

Le graphe de Wagner ne permet pas d'utiliser les théorèmes précédents.

Dans certains cas, on sait aussi démontrer qu'un graphe n'est pas hamiltonien. Ainsi, le théorème de Grindberg donne une caractéristique respectée par tous les graphes planaires hamiltoniens. Si cette condition n'est pas respectée dans un graphe planaire, on sait qu'il n'est pas hamiltonien.

Malgré ces nombreux résultats partiels, dans de nombreux cas, on ne dispose pas d'outil mathématique efficace permettant de voir si un graphe donné est hamiltonien ou ne l'est pas. Ainsi, aucun des théorèmes précédents ne fournit de critère qui permettrait de déterminer automatiquement que le graphe de la figure ci-contre est hamiltonien, la somme des degrés de n'importe quelle paire de sommets valant toujours ${\displaystyle 6}$, ce qui est moins que le nombre de sommets ${\displaystyle 8}$.

Les résultats précédents s'axent tous sur des considérations liées aux degrés des sommets. Un autre axe de recherche est de chercher à savoir si certaines catégories de graphes sont hamiltoniennes ou non :

• la conjecture de Lovász (en) affirme que les graphes sommet-transitifs seraient semi-hamiltoniens ;
• la conjecture de Tait (que l'on sait à présent fausse) affirmait que les graphes cubiques polyédriques étaient hamiltoniens ;
• la conjecture de Barnette affirme que les graphes cubiques bipartis polyédriques seraient hamiltoniens.

Le problème du chemin hamiltonien est le problème de décision qui consiste, étant donné un graphe, à décider s'il admet un chemin hamiltonien. Ce problème est NP-complet, c'est-à-dire qu'on sait vérifier une éventuelle solution dans un temps polynomial en fonction du nombre ${\displaystyle n}$ de sommets, mais que ce problème est au moins aussi difficile que d'autres problèmes NP-complets, ce qui est une forte indication que l'on ne saura probablement pas trouver cette solution dans un temps polynomial dans le cas général. Le problème associé est de tester si un chemin hamiltonien existe.

Les deux versions — graphe orienté et graphe non orienté — du problème du cycle hamiltonien font partie des 21 problèmes de Karp et sont NP-complets.

Le problème du voyageur de commerce revient à chercher un cycle hamiltonien dans un graphe complet dont les arêtes sont pondérées, en ajoutant une contrainte : le poids de ce cycle doit être minimal.

La recherche de solutions est en général confiée à un ordinateur qui pourra par exemple tester toutes les chaînes jusqu'à trouver un cycle hamiltonien (dans le cas d'un algorithme très naïf). Cette technique n'est pas vraiment satisfaisante non plus, car les calculs peuvent être très longs dans le pire des cas. De plus, une fois trouvées ces chaînes, on ne comprend pas mieux ce qui rend un graphe hamiltonien ou non. Cette méthode permet néanmoins de résoudre des problèmes pratiques.

À cause de la difficulté à résoudre les problèmes de chaînes et de cycles hamiltoniens avec des ordinateurs conventionnels, on s'est également penché sur des modèles de calcul non conventionnels. Par exemple, Leonard Adleman a montré que le problème du chemin hamiltonien pouvait être résolu à l'aide d'un ordinateur à ADN.

On peut passer simplement du problème consistant à trouver une chaîne hamiltonienne à celui consistant à trouver un cycle hamiltonien et vice-versa.

D'une part, au lieu de chercher une chaîne hamiltonienne dans un graphe ${\displaystyle G}$, on peut créer un graphe ${\displaystyle H}$ à partir de ${\displaystyle G}$ en lui ajoutant un nouveau sommet que l'on relie à tous les sommets existants de ${\displaystyle G}$, puis chercher un cycle hamiltonien de ${\displaystyle H}$.

D'autre part, au lieu de chercher un cycle hamiltonien dans un graphe ${\displaystyle G}$, on peut choisir un de ses sommets ${\displaystyle u}$, puis, pour chacune des arêtes qui le relient à un voisin ${\displaystyle v}$, construire un graphe ${\displaystyle H}$ à partir de ${\displaystyle G}$ en remplaçant cette arête par une paire de nouveaux sommets de degré 1, l'un relié à ${\displaystyle u}$ et l'autre relié à ${\displaystyle v}$, et enfin chercher une chaîne hamiltonienne de ${\displaystyle H}$.

On peut donc :

• remplacer une recherche de chaîne hamiltonienne par une seule recherche de cycle hamiltonien ;
• remplacer une recherche de cycle hamiltonien par au maximum ${\displaystyle n-1}$ recherches de chaînes hamiltoniennes, ${\displaystyle n}$ étant le nombre de sommets du graphe.

Recherche d'un chemin hamiltonien dans un graphe orienté en explorant les différentes possibilités[19].

Le pire algorithme de résolution du problème de recherche de chaîne hamiltonienne auquel on puisse penser consiste à prendre un des ${\displaystyle n}$ sommets, puis à considérer les éventuelles arêtes vers les ${\displaystyle n-1}$ sommets restants, et ainsi de suite. Cela donne ${\displaystyle n!}$ chaînes possibles à tester : la factorielle de ${\displaystyle n}$ augmentant très rapidement quand ${\displaystyle n}$ augmente, on assiste à une explosion combinatoire et la recherche peut devenir très longue à partir d'un certain nombre ${\displaystyle n}$ de sommets.

Un tel algorithme de recherche exhaustive exploitant la force de calcul de l'ordinateur peut être optimisé de plusieurs façons.

Ainsi, Frank Rubin met en avant une méthode de recherche[20] où l'on classe les arêtes du graphe en trois groupes : celles qui doivent être dans la chaîne, celles qui ne peuvent pas être dans la chaîne, et celles pour lesquelles on ne sait pas. Au fur et à mesure que la recherche avance, un ensemble de règles de décision classe les arêtes pour lesquelles on ne sait pas encore, et détermine si la recherche doit continuer ou doit s'arrêter. L'algorithme divise le graphe en composants qui peuvent être traités séparément.

Un algorithme qui est un cas de programmation dynamique et que l'on doit à Bellman, Held et Karp peut être utilisé pour résoudre le problème en une durée d'ordre ${\displaystyle O(n^{2}2^{n})}$. Dans cette méthode, on détermine, pour chaque sous-ensemble ${\displaystyle S}$ de sommets et chaque sommet ${\displaystyle v}$ de ${\displaystyle S}$, s'il existe une chaîne couvrant exactement les sommets de ${\displaystyle S}$ et se terminant en ${\displaystyle v}$. Pour chaque choix de ${\displaystyle S}$ et de ${\displaystyle v}$, une chaîne existe pour ${\displaystyle (S,v)}$ si et seulement si ${\displaystyle v}$ a un sommet voisin ${\displaystyle w}$ tel qu'une chaîne existe pour ${\displaystyle (S-\{v\},w)}$, ce que l'on peut vérifier dans les informations déjà calculées par le programme[21] - [22].

Andreas Björklund a adopté une autre approche en exploitant le principe d'inclusion-exclusion pour ramener le problème du comptage des cycles hamiltoniens à un comptage des cycles recouvrants, lequel peut être résolu en calculant certains déterminants de matrices. Avec cette méthode, il a montré comment résoudre le problème du cycle hamiltonien dans un graphe à ${\displaystyle n}$ sommets quelconque à l'aide d'une méthode de Monte-Carlo dans un délai d'ordre O(1,657ⁿ) ; dans le cas de graphes bipartis cet algorithme peut être amélioré pour répondre dans un délai d'ordre O(1,414ⁿ)[23].

Pour les graphes de degré maximal trois, une recherche avec retour sur trace soigneuse peut trouver un cycle hamiltonien (s'il existe) en une durée O(1,251ⁿ)[24].

Leonard Adleman[25] - [26] a conçu et expérimenté avec succès en laboratoire une méthode de résolution de ce problème en partant d'ADN, ouvrant ainsi la voie à des recherches concernant un ordinateur à ADN.

L'idée est de représenter les arcs du graphe par des séquences d'ADN qui peuvent s'assembler linéairement quand elles ont une extrémité commune. Un polymère formé par ces séquences correspond donc à un chemin.

L'algorithme proposé par Adleman est le suivant :

1. Générer un grand nombre de séquences, correspondant à des chemins aléatoires ;
2. Filtrer (par exemple par la masse) pour ne garder que les chemins avec n sommets (où n est la taille du graphe) ;
3. Filtrer pour ne garder que les chemins qui contiennent une fois chaque sommet ;
4. S'il reste des séquences qui passent les deux filtres, le graphe a un chemin hamiltonien.

L'intérêt de cette méthode en comparaison avec les méthodes de résolution par un ordinateur classique est qu'elle est beaucoup moins coûteuse en temps. Cet algorithme exploite le parallélisme intrinsèque aux réactions chimiques, et le problème pourrait être résolu en un nombre d'étapes de réaction chimiques linéaire en fonction du nombre de sommets du graphe.

Ce résultat est important en informatique théorique : il s'agit d'une méthode de résolution en temps polynomial d'un problème NP-complet, et fournit donc une méthode en temps polynomial pour résoudre n’importe quel problème NP-complet, ce que les ordinateurs actuels ne sont pas capables de faire.

Néanmoins ce faible coût en temps se paye d'une autre manière : la quantité d'ADN nécessaire dépend de la taille du problème, ce qui se répercute entre autres sur le poids de la machine nécessaire. Un chercheur[27] a calculé qu'une machine permettant la résolution du problème pour un graphe de 200 sommets pourrait peser 3 × 10²⁵ kg. L'algorithme suppose aussi que l'on dispose d'un nombre factoriel de types distincts de la molécule d'ADN qui participeront à la réaction[28]. Ces problèmes, ainsi que d'autres problèmes liés à la réalisation de machine à ADN utilisables n’ont pas permis à l’heure actuelle un réel développement des ordinateurs à ADN pour la résolution concrète de ce type de problèmes.

Les problèmes du cycle ou du circuit hamiltonien dans les graphes orientés ou non sont deux des problèmes parmi les 21 problèmes NP-complets de Karp. Le problème dans le graphe non orienté se ramène au problème dans le graphe orienté. Le cas dans le graphe orienté se ramène au problème de couverture par sommets.

Le problème de la recherche d'un cycle hamiltonien est dans la classe FNP (en).

Les problèmes du cycle et du circuit hamiltonien restent NP-complets même :

• dans le cas des graphes planaires de degré maximum trois[29] ;
• dans le cas des graphes planaires orientés avec degré entrant et sortant inférieurs ou égaux à 2[30] ;
• dans le cas des graphes qui sont des sous-graphes d'une grille d'un carré[31] ;
• dans le cas des graphes non orientés sans isthme, planaires, cubiques et bipartis et des graphes cubiques 3-connexes bipartis[32].

Néanmoins, si l'on assemble toutes ces conditions, le problème de savoir si les graphes planaires cubiques bipartis 3-connexes contiennent toujours un cycle hamiltonien reste ouvert (conjecture de Barnette), et si c'était le cas le problème restreint à ces graphes ne pourrait pas être NP-complet.

Dans un graphe où tous les sommets sont de degré impair, une démonstration liée au lemme des poignées de main prouve que le nombre de cycles hamiltoniens passant par n'importe quelle arête est toujours pair. Ainsi, si un cycle hamiltonien est connu, alors un second doit aussi exister[33]. Néanmoins, trouver ce second cycle ne semble pas être un travail de calcul facile. Papadimitriou a défini la classe de complexité PPA pour regrouper les problèmes comme celui-ci[34] - [35].

• Snake-in-the-box (en), la recherche du plus long chemin induit (en) dans un hypercube
• Problème du cavalier, la recherche d'un cycle hamiltonien dans le graphe du cavalier (en)
• Notation LCF pour les graphes cubiques hamiltoniens
• Graphe pancyclique, type de graphes ayant des cycles de toutes les longueurs, y compris un cycle hamiltonien
• Graphe de Barnette-Bosák-Lederberg

(en) Eric W. Weisstein, « Hamiltonian Cycle », sur MathWorld