right|thumb|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. thumb|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 thumb|right|Plateau de jeu pour le . gauche|vignette|Animation qui montre le déplacement d'un cavalier sur un échiquier. Son déplacement est un chemin hamiltonien. Au , 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). Il s'agit du problème du cavalier.
Les graphes hamiltoniens portent le nom de William Rowan Hamilton qui était astronome royal en Irlande, au milieu du . Celui-ci a inventé un jeu qu'il a nommé , 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 ., 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 en l'honneur de Hamilton, les cycles hamiltoniens dans les polyèdres avaient déjà été étudiés un an plus tôt par Thomas Kirkman..
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.
Exemples thumb|Graphe de Herschel. Le plus petit graphe hamiltonien à n sommets est le graphe cycle . Un graphe complet ayant plus de deux sommets est hamiltonien. Le nombre de cycles hamiltoniens différents sur un graphe complet non orienté à sommets est et sur un graphe complet orienté à sommets est . 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.. Le graphe des arêtes d'un solide de Platon est hamiltonien.. Le graphe des arêtes d'un prisme ou d'un antiprisme est hamiltonien. 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... Le graphe de Herschel (figure) est le plus petit graphe des arêtes d'un polytope convexe qui n'a pas de cycle hamiltonien. Le graphe adjoint d'un graphe hamiltonien est lui-même hamiltonien. 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 .. 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. Il s'énonce comme suit. :
Théorème de Ore Ce théorème est dû à Øystein Ore, en 1960.. 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 , alors la somme des degrés de n'importe quelle paire de sommets, adjacents ou pas, est au moins .
Théorème de Pósa On doit à plusieurs théorèmes sur les cycles hamiltoniens. On peut en particulier citer un théorème de 1962.. qui porte sur les sommets faiblement connectés :
On remarque que la condition 2 est comprise dans la condition 1 quand est pair, et n'a donc d'intérêt que lorsque est impair.
thumb|right|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 . 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é , or il y a un sommet de degré . Le théorème de Ore n'est pas plus utile, car les sommets non adjacents et vérifient , or on devrait avoir au moins . En revanche, le théorème de Pósa permet de déterminer que le graphe est hamiltonien, car il y a sommet de degré et sommet de degré : la condition 1 est remplie ( et ).
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. une méthode pour déterminer si un graphe est hamiltonien : tant qu'il reste des sommets et non adjacents tels que , on ajoute l'arête 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 dugraphe de départ100px100px100px 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é . Pas mieux pour le théorème de Ore, car il existe des paires de sommets non adjacents de degré , donc vérifiant . Le théorème de Pósa ne vient pas à la rescousse, car il y a trop de sommets de degré (il y en a ). 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é et les sommets de degré . On ajoute ensuite les arêtes en vert entre le sommet de degré et les sommets qui viennent de passer en degré . On obtient le graphe complet , 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. 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. le théorème suivant :
Henry Meyniel a énoncé en 1973. le théorème voisin suivant :
Pourquoi ce n'est pas satisfaisant thumb|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 , ce qui est moins que le nombre de sommets .
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 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 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.