Graphe hamiltonien

Un cycle hamiltonien (en rouge) dans le graphe des arêtes du dodécaèdre. Comme tous les solides de Platon, le dodécaèdre est représenté par un graphe hamiltonien.

Exemples de cycles hamiltoniens sur un graphe grille 8x8.

En mathématiques, dans le cadre de la théorie des graphes, un chemin hamiltonien d'un graphe orienté ou non orienté est un chemin qui passe par tous les sommets une fois et une seule. Un cycle hamiltonien est un chemin hamiltonien qui est un cycle. Un graphe hamiltonien est un graphe qui possède un cycle hamiltonien.

Un graphe hamiltonien ne doit pas être confondu avec un graphe eulérien, où l'on passe par toutes les arêtes une fois et une seule : dans un cycle hamiltonien, on peut très bien négliger de passer par certaines arêtes. Un graphe peut être eulérien, hamiltonien, les deux à la fois, ou aucun des deux : le graphe papillon est un exemple de graphe eulérien mais pas hamiltonien.

Un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens : ainsi, le graphe de Chvátal a 12 sommets, 24 arêtes et 370 cycles hamiltoniens distincts.

On a démontré un certain nombre de conditions mathématiques, qui, si elles sont vérifiées, permettent d'assurer qu'un graphe est hamiltonien, ainsi que des conditions qui, si elles ne sont pas vérifiées, assurent qu'il ne l'est pas. On peut par ailleurs confier à des ordinateurs le soin de chercher des cycles hamiltoniens au moyen d'algorithmes que l'on a optimisés petit à petit. Dans les deux cas, le problème algorithmique du chemin hamiltonien est NP-complet, i.e. difficile à résoudre dans un temps raisonnable dans le cas général. Les graphes hamiltoniens sont un domaine de recherche actif à la fois en mathématiques et en informatique.

Histoire

Animation qui montre le déplacement d'un cavalier sur un échiquier. Son déplacement est un chemin hamiltonien.

Au IX^e siècle, le poète indien Rudrata a été le premier à trouver le problème des cycles/chemins hamiltoniens sur un échiquier mais avec un cavalier (c'est-à-dire de parcourir chaque case une et seule fois en n'utilisant que les mouvements d'un cavalier)^{[réf. nécessaire]}. Il s'agit du problème du cavalier.

Les graphes hamiltoniens sont nommés d'après William Rowan Hamilton qui était astronome royal en Irlande, au milieu du XIX^e siècle. Celui-ci a inventé un jeu qu'il a nommé icosian game, qui consiste à trouver un cycle hamiltonien dans le graphe des arêtes du dodécaèdre. Hamilton a résolu ce problème à l'aide d'un nouveau type de calculs qu'il a appelé le icosian calculus (en)^[1]^,^[2], et que l'on décrirait de nos jours par des calculs dans un certain groupe non commutatif. Cette solution ne se généralise malheureusement pas à un graphe arbitraire.

Bien que ces graphes soient nommés d'après Hamilton, les cycles hamiltoniens dans les polyèdres avaient déjà été étudiés un an plus tôt par Thomas Kirkman^[3].

Définitions

Les définitions ci-dessous se rapportent soit à des graphes non orientés, soit à des graphes orientés. Pour être rigoureux, il faudrait parler d'arcs, de chemins et de circuits dans le cas des graphes orientés, et d'arêtes, de chaînes et de cycles dans le cas des graphes non orientés.

Chaîne hamiltonienne

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.

Graphe hamiltonien

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

Graphe semi-hamiltonien

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

Graphe hamiltonien-connexe

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

Décomposition hamiltonienne

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

Graphe hypohamiltonien

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

Exemples

Le plus petit graphe hamiltonien à n sommets est le graphe cycle $C_{n}$ .
Un graphe complet ayant plus de deux sommets est hamiltonien. Le nombre de cycles hamiltoniens différents sur un graphe complet non orienté à $n$ sommets est ${\frac {(n-1)!}{2}}$ et sur un graphe complet orienté à $n$ sommets est $(n-1)!$ .
Un tournoi a un nombre impair de chemins hamiltoniens. Un tournoi à plus de deux arêtes est hamiltonien si (et seulement si) il est fortement connexe^[4].
Le graphe des arêtes d'un solide de Platon est hamiltonien^[5].
Le graphe des arêtes d'un prisme ou d'un antiprisme est hamiltonien^{[réf. souhaitée]}.
Les graphes des arêtes des 13 solides d'Archimède sont hamiltoniens, mais parmi les 13 solides de Catalan, seuls 7 ont leur graphe des arêtes hamiltonien^[6]^,^[7].
Le graphe de Herschel (figure) est le plus petit graphe des arêtes d'un polytope convexe qui n'a pas de cycle hamiltonien^{[réf. nécessaire]}.
Le graphe adjoint d'un graphe hamiltonien est lui-même hamiltonien^{[réf. nécessaire]}.
Le graphe adjoint d'un graphe eulérien est hamiltonien.

Caractérisation d'un graphe hamiltonien

Pour les graphes eulériens, on dispose d'une condition nécessaire et suffisante simple pour déterminer si le graphe est eulérien (le théorème d'Euler). On n'a malheureusement pas trouvé d'équivalent pour les graphes hamiltoniens.

On dispose néanmoins d'un certain nombre de critères, de plus en plus généraux, qui permettent d'assurer que tel ou tel graphe est hamiltonien^[8]. C'est Gabriel Andrew Dirac qui ouvre le bal en 1952, avec l'idée intuitive qu'un graphe est forcément hamiltonien lorsqu'il possède « suffisamment d'arêtes ». La meilleure caractérisation d'après le degré des sommets à laquelle on soit arrivé à ce jour est celle du théorème de Bondy et de Chvátal de 1976.

D'autres théorèmes, comme celui de Ghouila-Houiri, sont des versions dans le cas des graphes orientés.

Théorème de Dirac

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

Théorème — Un graphe simple à $n$ sommets ( $n\geq 3$ ) dont chaque sommet est au moins de degré ${\frac {n}{2}}$ est hamiltonien.

Démonstration

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

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

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

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

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

On construit le cycle $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, $C$ est hamiltonien.

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

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

Théorème de Ore

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

Théorème — Un graphe simple à $n$ sommets ( $n\geq 3$ ) tel que la somme des degrés de toute paire de sommets non adjacents vaut au moins $n$ est hamiltonien.

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 ${\frac {n}{2}}$ , alors la somme des degrés de n'importe quelle paire de sommets, adjacents ou pas, est au moins $n$ .

Démonstration

Notons $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 $G$ ne vérifie pas la propriété $P(n)$ ^[12].

Soit $G$ un graphe non-hamiltonien à $n$ sommets ( $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 $G'$ à partir de $G$ en ajoutant des arêtes sans former de cycle hamiltonien, jusqu'à ce que ce ne soit plus possible.

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

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

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

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

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

Théorème de Pósa

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 :

Théorème — Un graphe simple à $n$ sommets ( $n\geq 3$ ) tel que :

pour tout entier $k$ tel que $1\leq k<{\frac {n-1}{2}}$ le nombre de sommets de degré inférieur ou égal à $k$ est inférieur à $k$
le nombre de sommets de degré inférieur ou égal à ${\frac {n-1}{2}}$ est inférieur ou égal à ${\frac {n-1}{2}}$

est hamiltonien.

On remarque que la condition 2 est comprise dans la condition 1 quand $n$ est pair, et n'a donc d'intérêt que lorsque $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 $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é $3$ , or il y a un sommet de degré $2$ .
Le théorème de Ore n'est pas plus utile, car les sommets non adjacents $a$ et $b$ vérifient $\mathrm {deg} (a)+\mathrm {deg} (b)=3+2=5$ , or on devrait avoir au moins $6$ .
En revanche, le théorème de Pósa permet de déterminer que le graphe est hamiltonien, car il y a $0$ sommet de degré $1$ et $1$ sommet de degré $2$ : la condition 1 est remplie ( $0<1$ et $0+1<2$ ).

Théorème de Bondy et Chvátal

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 $u$ et $v$ non adjacents tels que $\mathrm {deg} (u)+\mathrm {deg} (v)\geq n$ , on ajoute l'arête $\{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 :

Théorème — Un graphe est hamiltonien si et seulement si sa fermeture est hamiltonienne.

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é $2<{\frac {5}{2}}$ .
Pas mieux pour le théorème de Ore, car il existe des paires de sommets non adjacents de degré $2$ , donc vérifiant $2+2<5$ .
Le théorème de Pósa ne vient pas à la rescousse, car il y a trop de sommets de degré $2$ (il y en a $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é $2$ et les sommets de degré $3$ . On ajoute ensuite les arêtes en vert entre le sommet de degré $2$ et les sommets qui viennent de passer en degré $3$ . On obtient le graphe complet $K_{5}$ , qui est hamiltonien, ce qui prouve que le graphe de départ l'était aussi.

Cas des graphes orientés

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 :

Théorème — Un graphe orienté simple fortement connexe à $n$ sommets dont chaque sommet est au moins de degré entrant ${\frac {n}{2}}$ et de degré sortant ${\frac {n}{2}}$ est hamiltonien.

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 :

Théorème — Un graphe orienté simple à $n$ sommets tel que, pour toute paire $u$ et $v$ de sommets, soit il y a un arc de $u$ en $v$ , soit $d^{-}(u)+d^{+}(v)\geq n$ , est hamiltonien.

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

Théorème — Un graphe orienté simple fortement connexe à $n$ sommets tel que la somme des degrés de toute paire de sommets non adjacents vaut au moins $2n-1$ est hamiltonien.

Pourquoi ce n'est pas satisfaisant

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 $6$ , ce qui est moins que le nombre de sommets $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.

Problème du chemin hamiltonien

Complexité

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 $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.

Relation entre les problèmes

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 $G$ , on peut créer un graphe $H$ à partir de $G$ en lui ajoutant un nouveau sommet que l'on relie à tous les sommets existants de $G$ , puis chercher un cycle hamiltonien de $H$ .

D'autre part, au lieu de chercher un cycle hamiltonien dans un graphe $G$ , on peut choisir un de ses sommets $u$ , puis, pour chacune des arêtes qui le relient à un voisin $v$ , construire un graphe $H$ à partir de $G$ en remplaçant cette arête par une paire de nouveaux sommets de degré 1, l'un relié à $u$ et l'autre relié à $v$ , et enfin chercher une chaîne hamiltonienne de $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 $n-1$ recherches de chaînes hamiltoniennes, $n$ étant le nombre de sommets du graphe.

Algorithmes

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 $n$ sommets, puis à considérer les éventuelles arêtes vers les $n-1$ sommets restants, et ainsi de suite. Cela donne $n!$ chaînes possibles à tester : la factorielle de $n$ augmentant très rapidement quand $n$ augmente, on assiste à une explosion combinatoire et la recherche peut devenir très longue à partir d'un certain nombre $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 $O(n^{2}2^{n})$ . Dans cette méthode, on détermine, pour chaque sous-ensemble $S$ de sommets et chaque sommet $v$ de $S$ , s'il existe une chaîne couvrant exactement les sommets de $S$ et se terminant en $v$ . Pour chaque choix de $S$ et de $v$ , une chaîne existe pour $(S,v)$ si et seulement si $v$ a un sommet voisin $w$ tel qu'une chaîne existe pour $(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 à $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].

Recherche d'un chemin hamiltonien par ordinateur à ADN

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 :

Générer un grand nombre de séquences, correspondant à des chemins aléatoires ;
Filtrer (par exemple par la masse) pour ne garder que les chemins avec n sommets (où n est la taille du graphe) ;
Filtrer pour ne garder que les chemins qui contiennent une fois chaque sommet ;
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.

Démonstration que le problème est NP-complet

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.

Plus de détails sur la complexité

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].

Notes et références

(en)/(en) Cet article est partiellement ou en totalité issu des articles intitulés en anglais « Hamiltonian path » (voir la liste des auteurs), « Ore's theorem » (voir la liste des auteurs) et en anglais « Hamiltonian path problem » (voir la liste des auteurs).

↑ (en) William Rowan Hamilton, « Account of the Icosian Calculus », Proceedings of the Royal Irish Academy, n^o 6,‎ 1858
↑ (en) William Rowan Hamilton, « Memorandum respecting a new system of roots of unity », Philosophical Magazine, n^o 12,‎ 1856.
↑ (en) N. L. Biggs, « T. P. Kirkman, mathematician », The Bulletin of the London Mathematical Society, vol. 13, n^o 2,‎ 1981, p. 104 (DOI 10.1112/blms/13.2.97, MR 608093, lire en ligne).
↑ Graham 1995, p. 31.
↑ (en) Eric W. Weisstein, « Hamiltonian Cycle », sur MathWorld.
↑ (en) Eric W. Weisstein, « Archimedean Graph », sur MathWorld.
↑ (en) Eric W. Weisstein, « Archimedean Dual Graph », sur MathWorld.
↑ (en) Melissa DeLeon, « A Study of Sufficient Conditions for Hamiltonian Cycles », Department of Mathematics and Computer Science, Seton Hall University.
↑ (en) Gabriel Andrew Dirac, « Some theorems on abstract graphs », Proc. London Math. Soc., 3^e série, vol. 2,‎ 1952, p. 69-81 (DOI 10.1112/plms/s3-2.1.69, MR 0047308)
↑ (en) Ronald Graham, Handbook of Combinatorics, MIT Press, 1995 (ISBN 978-0-262-57170-8, lire en ligne).
↑ (en) Øystein Ore, « A Note on Hamiltonian Circuits », American Mathematical Monthly, n^o 67,‎ 1960, p. 55.
↑ Cette adaptation de la démonstration classique du théorème d'Ore est due à David Eppstein en 2013.
↑ (en) Lajos Pósa, « A theorem concerning hamilton lines », Magyar Tud. Akad. Mat. Kutató ́Int. Közl., n^o 7,‎ 1962, p. 225-226.
↑ (en) Crispin Nash-Williams, « On Hamiltonian circuits in finite graphs », Proc. Amer. Math. Soc., n^o 17,‎ 1966, p. 466-467 (lire en ligne).
↑ (en) John Adrian Bondy et Václav Chvátal, « A method in graph theory », Discrete Math., n^o 15,‎ 1976, p. 111-135.
↑ Alain Ghouila-Houri, « Une condition suffisante d'existence d'un circuit hamiltonien », C. R. Acad. Sci. Paris, n^o 251,‎ 1960, p. 495−497.
↑ (en) Douglas R. Woodall, « Sufficient conditions for circuits in graphs », Proc. London Math. Soc., 3^e série, vol. 24,‎ 1972, p. 739-755 (MR 0318000).
↑ M. Meyniel, « Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté », Journal of Combinatorial Theory, Ser. B, vol. 14, n^o 2,‎ 1973, p. 137-147 (DOI 10.1016/0095-8956(73)90057-9).
↑ Schéma adapté de Nanoinformatique et intelligence ambiante - Inventer l'ordinateur du XXI^e siècle Jean-Baptiste Waldner, Hermès Science, London, 2007 (avec la permission de l'auteur).
↑ (en) Frank Rubin, « A Search Procedure for Hamilton Paths and Circuits », Journal of the ACM, vol. 21,‎ 1974, p. 576-580.
↑ (en) Richard Bellman, « Dynamic programming treatment of the travelling salesman problem », Journal of the ACM, vol. 9,‎ 1962, p. 61-63 (DOI 10.1145/321105.321111).
↑ (en) M. Held et R. M. Karp, « A dynamic programming approach to sequencing problems », J. SIAM, vol. 10, n^o 1,‎ 1962, p. 196-210 (DOI 10.1137/0110015).
↑ (en) Andreas Björklund, « Determinant sums for undirected Hamiltonicity », dans Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10), 2010 (DOI 10.1109/FOCS.2010.24, arXiv 1008.0541), p. 173-182.
↑ (en) Kazuo Iwama et Takuya Nakashima, « An improved exact algorithm for cubic graph TSP », dans Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007), coll. « Lecture Notes in Computer Science » (n^o 4598), 2007 (DOI 10.1007/978-3-540-73545-8_13), p. 108-117.
↑ (en) Leonard Adleman, An Abstract Theory of Computer Viruses, New York, Springer-Verlag, 1990 (ISBN 0-387-97196-3).
↑ (en) Leonard Adleman, Towards a (MATH)ematical theory of self-assembly. Technical Report 00-722, Department of Computer Science, University of Southern California, 2000 (ISBN 2-7011-4032-3).
↑ (en) « Complexity & computabiliy »
↑ (en) Leonard Adleman, « Molecular computation of solutions to combinatorial problems », Science, vol. 266, n^o 5187,‎ novembre 1994, p. 1021-1024 (PMID 7973651, DOI 10.1126/science.7973651, JSTOR 2885489).
↑ (en) Michael Garey, David S. Johnson et Larry Stockmeyer, « Some simplified NP-complete problems », dans Proc. 6th ACM Symposium on Theory of Computing (STOC '74), 1974 (DOI 10.1145/800119.803884), p. 47-63.
↑ (en) J. Plesńik, « The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two », Information Processing Letters, vol. 8, n^o 4,‎ 1979, p. 199-201 (lire en ligne).
↑ Alon Itai, Christos Papadimitriou et Jayme Szwarcfiter, Hamilton Paths in Grid Graphs, vol. 4, 1982, 676–686 p. (DOI 10.1137/0211056, CiteSeer^x 10.1.1.383.1078, lire en ligne).
↑ (en) Takanori Akiyama, Takao Nishizeki et Nobuji Saito, « NP-completeness of the Hamiltonian cycle problem for bipartite graphs », Journal of Information Processing, vol. 3, n^o 2,‎ 1980−1981, p. 73-76 (MR 596313, lire en ligne).
↑ (en) A. G. Thomason, « Hamiltonian cycles and uniquely edge colourable graphs », dans Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), coll. « Annals of Discrete Mathematics » (n^o 3), 1978 (DOI 10.1016/S0167-5060(08)70511-9, MR 499124), p. 259-268.
↑ (en) Christos H. Papadimitriou, « On the complexity of the parity argument and other inefficient proofs of existence », Journal of Computer and System Sciences, vol. 48, n^o 3,‎ 1994, p. 498-532 (DOI 10.1016/S0022-0000(05)80063-7, MR 1279412).
↑ (en) La classe PPA sur le Complexity Zoo.

Voir aussi

Articles connexes

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

Lien externe

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

[1] (en) William Rowan Hamilton, « Account of the Icosian Calculus », Proceedings of the Royal Irish Academy, n^o 6,‎ 1858

[2] (en) William Rowan Hamilton, « Memorandum respecting a new system of roots of unity », Philosophical Magazine, n^o 12,‎ 1856.

[3] (en) N. L. Biggs, « T. P. Kirkman, mathematician », The Bulletin of the London Mathematical Society, vol. 13, n^o 2,‎ 1981, p. 104 (DOI 10.1112/blms/13.2.97, MR 608093, lire en ligne).

[4] Graham 1995, p. 31.

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

[6] (en) Eric W. Weisstein, « Archimedean Graph », sur MathWorld.

[7] (en) Eric W. Weisstein, « Archimedean Dual Graph », sur MathWorld.

[8] (en) Melissa DeLeon, « A Study of Sufficient Conditions for Hamiltonian Cycles », Department of Mathematics and Computer Science, Seton Hall University.

[9] (en) Gabriel Andrew Dirac, « Some theorems on abstract graphs », Proc. London Math. Soc., 3^e série, vol. 2,‎ 1952, p. 69-81 (DOI 10.1112/plms/s3-2.1.69, MR 0047308)

[10] (en) Ronald Graham, Handbook of Combinatorics, MIT Press, 1995 (ISBN 978-0-262-57170-8, lire en ligne).

[11] (en) Øystein Ore, « A Note on Hamiltonian Circuits », American Mathematical Monthly, n^o 67,‎ 1960, p. 55.

[12] Cette adaptation de la démonstration classique du théorème d'Ore est due à David Eppstein en 2013.

[13] (en) Lajos Pósa, « A theorem concerning hamilton lines », Magyar Tud. Akad. Mat. Kutató ́Int. Közl., n^o 7,‎ 1962, p. 225-226.

[14] (en) Crispin Nash-Williams, « On Hamiltonian circuits in finite graphs », Proc. Amer. Math. Soc., n^o 17,‎ 1966, p. 466-467 (lire en ligne).

[15] (en) John Adrian Bondy et Václav Chvátal, « A method in graph theory », Discrete Math., n^o 15,‎ 1976, p. 111-135.

[16] Alain Ghouila-Houri, « Une condition suffisante d'existence d'un circuit hamiltonien », C. R. Acad. Sci. Paris, n^o 251,‎ 1960, p. 495−497.

[17] (en) Douglas R. Woodall, « Sufficient conditions for circuits in graphs », Proc. London Math. Soc., 3^e série, vol. 24,‎ 1972, p. 739-755 (MR 0318000).

[18] M. Meyniel, « Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté », Journal of Combinatorial Theory, Ser. B, vol. 14, n^o 2,‎ 1973, p. 137-147 (DOI 10.1016/0095-8956(73)90057-9).

[19] Schéma adapté de Nanoinformatique et intelligence ambiante - Inventer l'ordinateur du XXI^e siècle Jean-Baptiste Waldner, Hermès Science, London, 2007 (avec la permission de l'auteur).

[20] (en) Frank Rubin, « A Search Procedure for Hamilton Paths and Circuits », Journal of the ACM, vol. 21,‎ 1974, p. 576-580.

[21] (en) Richard Bellman, « Dynamic programming treatment of the travelling salesman problem », Journal of the ACM, vol. 9,‎ 1962, p. 61-63 (DOI 10.1145/321105.321111).

[22] (en) M. Held et R. M. Karp, « A dynamic programming approach to sequencing problems », J. SIAM, vol. 10, n^o 1,‎ 1962, p. 196-210 (DOI 10.1137/0110015).

[23] (en) Andreas Björklund, « Determinant sums for undirected Hamiltonicity », dans Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10), 2010 (DOI 10.1109/FOCS.2010.24, arXiv 1008.0541), p. 173-182.

[24] (en) Kazuo Iwama et Takuya Nakashima, « An improved exact algorithm for cubic graph TSP », dans Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007), coll. « Lecture Notes in Computer Science » (n^o 4598), 2007 (DOI 10.1007/978-3-540-73545-8_13), p. 108-117.

[25] (en) Leonard Adleman, An Abstract Theory of Computer Viruses, New York, Springer-Verlag, 1990 (ISBN 0-387-97196-3).

[26] (en) Leonard Adleman, Towards a (MATH)ematical theory of self-assembly. Technical Report 00-722, Department of Computer Science, University of Southern California, 2000 (ISBN 2-7011-4032-3).

[27] (en) « Complexity & computabiliy »

[28] (en) Leonard Adleman, « Molecular computation of solutions to combinatorial problems », Science, vol. 266, n^o 5187,‎ novembre 1994, p. 1021-1024 (PMID 7973651, DOI 10.1126/science.7973651, JSTOR 2885489).

[29] (en) Michael Garey, David S. Johnson et Larry Stockmeyer, « Some simplified NP-complete problems », dans Proc. 6th ACM Symposium on Theory of Computing (STOC '74), 1974 (DOI 10.1145/800119.803884), p. 47-63.

[30] (en) J. Plesńik, « The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two », Information Processing Letters, vol. 8, n^o 4,‎ 1979, p. 199-201 (lire en ligne).

[31] Alon Itai, Christos Papadimitriou et Jayme Szwarcfiter, Hamilton Paths in Grid Graphs, vol. 4, 1982, 676–686 p. (DOI 10.1137/0211056, CiteSeer^x 10.1.1.383.1078, lire en ligne).

[32] (en) Takanori Akiyama, Takao Nishizeki et Nobuji Saito, « NP-completeness of the Hamiltonian cycle problem for bipartite graphs », Journal of Information Processing, vol. 3, n^o 2,‎ 1980−1981, p. 73-76 (MR 596313, lire en ligne).

[33] (en) A. G. Thomason, « Hamiltonian cycles and uniquely edge colourable graphs », dans Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), coll. « Annals of Discrete Mathematics » (n^o 3), 1978 (DOI 10.1016/S0167-5060(08)70511-9, MR 499124), p. 259-268.

[34] (en) Christos H. Papadimitriou, « On the complexity of the parity argument and other inefficient proofs of existence », Journal of Computer and System Sciences, vol. 48, n^o 3,‎ 1994, p. 498-532 (DOI 10.1016/S0022-0000(05)80063-7, MR 1279412).

[35] (en) La classe PPA sur le Complexity Zoo.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]