Parcours et graphes Hamiltoniens

On appelle chemin Hamiltonien sur un graphe un chemin passant par tous les sommets du graphe une fois et une seule. Un circuit Hamiltonien est un circuit passant par tous les sommets du graphe une fois et une seule.
Un graphe est dit Hamiltonien s'il possède un circuit Hamiltonien.

Cette appellation vient d'un jeu proposé par Sir W. Hamilton en 1859 : un voyageur veut visiter 20 villes aux sommets d'un dodécaèdre en passant une fois et une seule par chaque ville et en revenant à son point de départ.
Le dodécaèdre peut être "aplati" sur le graphe ci-contre.
Il y a de nombreuses solutions mais elles se réduisent toutes à une seule par symétrie : le circuit Hamiltonien découpe le dodécaèdre selon un patron formé de deux morceaux identiques de 6 pentagones accolés. L'un d'eux compose "l'intérieur" du circuit Hamiltonien, l'autre "l'extèrieur" sur l'image planaire du dodécaèdre.
Ils peuvent se raccorder bout à bout, formant un circuit Hamiltonien sur le graphe dual (un icosaèdre).

Tous les graphes ne sont pas Hamiltoniens : un graphe Hamiltonien est nécessairement 2-connexe, c'est à dire qu'il faut supprimer au moins deux sommets pour le séparer en deux morceaux disjoints.
Ce n'est pas suffisant, comme le montre ce plus petit graphe 2-connexe non Hamiltonien :

Notons aussi que seuls les graphes simples (sans boucles et pas plus d'une arête entre deux sommets) nous intéressent. Les boucles peuvent être supprimées car ramènent au sommet que l'on vient de quitter. Les arêtes en double aussi car inutiles. Nous supposerons dans la suite que tous les graphes considérés sont des graphes simples connexes.

Il y a d'autres conditions nécessaires que doivent satisfaire un graphe Hamiltonien.
Il existe aussi des conditions suffisantes. On ne connaît hélas pas de condition générale nécessaire et suffisante.

Conditions nécessaires

Outre la 2-connexité du graphe, citons la formule de Grinberg et le théorème des dissections.

Formule de Grinberg

Soit un graphe simple planaire Hamiltonien. Le circuit Hamiltonien sépare le plan en deux régions : l'intérieur et l'extèrieur du circuit.
Considérons tout d'abord l'intérieur. Les arêtes diagonales (celles ne faisant pas partie du circuit) intérieures le sont entièrement (graphe planaire) et délimitent des régions (faces) intérieures. Si d est le nombre d'arêtes diagonales intérieures, il y a d+1 faces intérieures. Appelons F_k le nombre de faces intérieures ayant k arêtes.
Ceci donne ∑ F_k = d + 1.
D'autre part chaque face F_k ayant k arêtes, le nombre total d'arêtes de ces faces est
∑ k F_k = N + 2d avec N le nombre d'arêtes du circuit Hamiltonien, et 2d car les arêtes diagonales sont alors comptées deux fois.
On en déduit : ∑ (k - 2)F_k = N - 2 en éliminant d entre ces deux égalités.
En considérant maintenant l'extèrieur du circuit, y compris la face infinie extèrieure au graphe, et en appelant G_k le nombre de faces ayant k arêtes extèrieures au circuit, on démontre de même que :
∑ (k - 2)G_k = N - 2 et finalement la formule de Grinberg :

∑ (k - 2)(Fk - Gk) = 0

Théorème des dissections

On appelle "dissection" d'un graphe une collection de chemins et de circuits élémentaires disjoints (sans sommets communs) recouvrant tout le graphe (tout sommet du graphe appartient à un chemin ou circuit de la collection).
On appelle "valeur" de la dissection le nombre de chemins (ouverts) de la dissection.
Alors bien évidemment une condition nécessaire pour qu'un graphe possède un chemin Hamiltonien est que la valeur minimale d'une dissection soit au plus 1, et pour qu'un graphe posède un circuit Hamiltonien, il faut que la valeur minimale d'une dissection soit 0.

Reste à chercher une dissection de valeur minimale dans un graphe G d'ordre N.
Il existe une méthode systématique permettant de trouver cette dissection. On construit tout d'abord un graphe biparti H d'ordre 2N dérivé du graphe G, on cherche alors un couplage maximum sur H et on en déduit une dissection de valeur minimale de G. Nous n'entrerons pas plus dans les détails (voir Berge - Graphes et Hypergraphes). L'algorithme est trop compliqué pour être exploité manuellement.

Conditions suffisantes

En dehors des cas particuliers, on connaît plusieurs conditions suffisantes pour qu'un graphe soit Hamiltonien, en considérant les degrés de chaque sommet, c'est à dire le nombre d'arêtes pour chaque sommet, noté d(i).

Graphes particuliers

Citons comme graphes Hamiltoniens connus :

• Le graphe de Hamilton, bien sûr
• Les graphes complets K_n
• Les graphes planaires 4-connexes

Critère de Ore

Si pour tout couple de sommets (i,j) du graphe G non reliés par une arête, d(i)+d(j)≥N, alors G est Hamiltonien.

Critère de Dirac

Si pour tout sommet d(i)≥N/2, alors G est Hamiltonien.

Graphes orientés

Dans le cas orienté (les arcs ont un sens de parcours), il y a aussi des conditions suffisantes pour qu'un graphe soit Hamiltonien.
Nous appellerons d⁺(i) le nombre d'arcs quittant le sommet i, d^-(i) le nombre d'arcs arrivant au sommet i,
et d(i)=d⁺(i)+d^-(i) le nombre d'arcs ayant une extrémité au sommet i.
Une condition nécessaire à l'existence d'un circuit Hamiltonien est qu'il soit "fortement connexe", c'est à dire qu'il existe entre deux sommets quelconques un chemin (composé d'arcs orientés tous dans le même sens) entre ces deux sommets.
Comme pour le cas non orienté, les boucles ne servent à rien et les arcs doublés non plus.
Nous ne considèrons donc que les 1-graphes fortement connexes sans boucles.

Théorème de Meyniel

Si dans un graphe fortement connexe sans boucles toute paire de sommets i et j non reliés par un arc satisfait :
d(i)+d(j)≥2N-1, alors ce graphe contient un circuit Hamiltonien.

Corollaires

• Un 1-graphe complet fortement connexe est Hamiltonien.
• Un 1-graphe fortement connexe avec tous ses sommets d(i)≥N est Hamiltonien
• Si un 1-graphe G fortement connexe est tel que pour tout couple de sommets (i,j) :
  si l'arc i->j n'existe pas d⁺(i)+d^-(j)≥2N-1, alors G est Hamiltonien.