chemin hamiltonien

Imaginez six villes reliées par des routes. Vous cherchez un itinéraire qui entre dans chaque ville une seule fois, sans obligation d'utiliser toutes les routes. Une route disponible peut donc rester de côté.

En remplaçant les villes par des sommets et les routes par des arêtes, cet itinéraire devient un chemin hamiltonien. Ses deux extrémités peuvent être différentes. Si elles sont reliées par une arête, le trajet peut se refermer en cycle hamiltonien.

Dans un graphe fini, un chemin hamiltonien est une suite ordonnée de sommets distincts qui contient tous les sommets. Si le graphe possède n sommets, notés v₁ à v_n, cette suite s'écrit $(v_1,v_2,\dots ,v_n)\backslash left(v\_1,v\_2,\backslash ldots,v\_n\backslash right)$. Pour chaque indice i compris entre 1 et n − 1, les sommets v_i et v_i+1 doivent être reliés par une arête.

La condition porte sur les sommets : chacun apparaît exactement une fois. Avec la convention usuelle du chemin sans répétition de sommets, une arête du trajet ne peut donc pas être parcourue plusieurs fois. En revanche, de nombreuses arêtes du graphe peuvent ne pas servir. Le tracé géométrique, la longueur visuelle des arêtes et l'ordre alphabétique des noms ne jouent aucun rôle.

Lorsque v_n est aussi relié à v₁, l'arête de fermeture forme un cycle hamiltonien. Le sommet initial est alors répété seulement pour noter le retour, tandis que tous les autres sont visités une fois. Décider si un graphe quelconque admet un chemin hamiltonien est un problème NP-complet : une solution proposée se vérifie rapidement, mais aucune méthode rapide n'est connue pour tous les graphes.

Considérons les six sommets A, B, C, D, E et F. Les huit arêtes disponibles sont A–B, A–C, B–C, B–D, C–E, D–E, D–F et E–F. Nous cherchons un ordre qui emploie chaque sommet une fois et dont deux termes consécutifs sont toujours voisins.

1. Partons de A et suivons A–B.
2. Depuis B, choisissons B–D.
3. Poursuivons par D–F, puis F–E.
4. Terminons par E–C.

La suite A–B–D–F–E–C contient bien six noms distincts et chacune de ses cinq transitions figure dans la liste des arêtes. Elle est donc hamiltonienne. Les arêtes B–C et D–E restent inutilisées. Comme C–A existe aussi, ajouter cette dernière arête ferme le cycle A–B–D–F–E–C–A. Le contrôle consiste à cocher les six sommets une fois, puis les six arêtes du cycle dans la liste initiale.

Dans un casse-tête de parcours, chaque case ou point devient un sommet et chaque déplacement autorisé une arête. On cherche un chemin hamiltonien lorsque la règle exige de visiter chaque position une fois ; on cherche plutôt un parcours eulérien lorsque ce sont les liaisons qu'il faut toutes emprunter.

Pour un petit graphe, une recherche par essais peut prolonger un chemin sommet après sommet, puis revenir au dernier choix lorsqu'une impasse apparaît. Un sommet non visité devenu inaccessible signale immédiatement qu'il faut revenir en arrière.

Dans une tournée, la question hamiltonienne teste d'abord l'existence d'un ordre de visite. Si les liaisons portent des distances et que l'on cherche en plus la tournée la plus courte, le problème du voyageur de commerce est le modèle approprié.

Chemin eulérien. Il utilise chaque arête exactement une fois, alors qu'un chemin hamiltonien visite chaque sommet exactement une fois. Dans le graphe de l'exemple, A–B–D–F–E–C est hamiltonien tout en laissant trois arêtes inutilisées : il n'est donc pas eulérien.

Cycle hamiltonien. Il revient au sommet initial par une arête supplémentaire. A–B–D–F–E–C est un chemin ouvert ; A–B–D–F–E–C–A est un cycle, car C et A sont voisins.

Problème du voyageur de commerce. Parmi les cycles qui visitent chaque sommet exactement une fois avant de revenir au départ, il cherche celui de poids total minimal dans un graphe pondé. Le problème hamiltonien d'existence demande seulement si un parcours admissible existe ; deux cycles de longueurs différentes donnent le même verdict d'existence.

Connexité insuffisante. Un graphe hamiltonien doit être connexe, mais un graphe connexe n'admet pas forcément un tel chemin. Dans une étoile à quatre feuilles, revenir du centre serait nécessaire pour atteindre plus de deux feuilles ; la répétition du centre l'interdit.

Test local trompeur. Des degrés élevés peuvent faciliter un parcours sans prouver son existence. Inversement, un sommet de degré 1 peut être une extrémité d'un chemin hamiltonien, mais deux tels sommets en occupent déjà les deux extrémités.

Convention sur les petits graphes. Le graphe réduit à un sommet admet naturellement un chemin hamiltonien de longueur nulle. En revanche, l'existence d'un cycle sur un ou deux sommets dépend des conventions sur les boucles et les arêtes multiples ; il faut annoncer le type de graphe retenu.

Difficulté algorithmique. Le caractère NP-complet concerne le problème de décision sur les graphes généraux. Il n'affirme ni que chaque instance est difficile, ni qu'une solution proposée est longue à contrôler. Les petits graphes et certaines familles structurées peuvent se traiter efficacement.

Sous-graphe — Isoler une partie d'un graphe aide à repérer les zones qu'un chemin devrait relier sans revisiter un sommet.

Balades dans le graphe divisoriel — Un terrain concret pour comparer libre parcours dans un graphe et contrainte de visite hamiltonienne.