Problème de chemin hamiltonien - Hamiltonian path problem

Cet article porte sur le problème spécifique de déterminer si un chemin ou un cycle hamiltonien existe dans un graphe donné. Pour les concepts généraux de la théorie des graphes, voir le chemin hamiltonien .

Dans le domaine mathématique de la théorie des graphes, le problème du chemin hamiltonien et le problème du cycle hamiltonien sont des problèmes pour déterminer si un chemin hamiltonien (un chemin dans un graphe orienté ou non orienté qui visite chaque sommet exactement une fois) ou un cycle hamiltonien existe dans un graphe donné ( qu'elles soient dirigées ou non ). Les deux problèmes sont NP-complets .

Le problème du cycle hamiltonien est un cas particulier du problème du voyageur de commerce , obtenu en fixant la distance entre deux villes à un si elles sont adjacentes et à deux sinon, et en vérifiant que la distance totale parcourue est égale à n (si c'est le cas, l'itinéraire est un circuit hamiltonien ; s'il n'y a pas de circuit hamiltonien, le chemin le plus court sera plus long).

Réduction entre le problème du chemin et le problème du cycle

Les problèmes de recherche d'un chemin hamiltonien et d'un cycle hamiltonien peuvent être liés comme suit :

  • Dans un sens, le problème du chemin hamiltonien pour le graphe G peut être lié au problème du cycle hamiltonien dans un graphe H obtenu à partir de G en ajoutant un nouveau sommet universel x , reliant x à tous les sommets de G . Ainsi, trouver un chemin hamiltonien ne peut pas être significativement plus lent (dans le pire des cas, en fonction du nombre de sommets) que trouver un cycle hamiltonien.
  • Dans l'autre sens, le problème de cycle hamiltonien pour un graphe G est équivalent au problème de chemin hamiltonien dans le graphe H obtenu en ajoutant les sommets terminaux ( degré -un) s et t attachés respectivement à un sommet v de G et à v', une copie clivée de v qui donne à v' le même voisinage que v . Le chemin hamiltonien dans H passant par les sommets svx-...-y-v'-t correspond au cycle hamiltonien dans G passant par vx-...-y(-v) .

Algorithmes

Il y a n ! différentes séquences de sommets qui pourraient être des chemins hamiltoniens dans un graphe n- vertex donné (et le sont, dans un graphe complet ), donc un algorithme de recherche par force brute qui teste toutes les séquences possibles serait très lent. Un premier algorithme exact pour trouver un cycle hamiltonien sur un graphe orienté était l'algorithme énumératif de Martello. Une procédure de recherche de Frank Rubin divise les bords du graphe en trois classes : ceux qui doivent être dans le chemin, ceux qui ne peuvent pas être dans le chemin et indécis. Au fur et à mesure que la recherche progresse, un ensemble de règles de décision classe les bords indécis et détermine s'il faut arrêter ou continuer la recherche. L'algorithme divise le graphique en composants qui peuvent être résolus séparément. De plus, un algorithme de programmation dynamique de Bellman, Held et Karp peut être utilisé pour résoudre le problème en temps O( n 2  2 n ). Dans cette méthode, on détermine, pour chaque ensemble S de sommets et chaque sommet v de S , s'il existe un chemin qui couvre exactement les sommets de S et se termine en v . Pour chaque choix de S et v , un chemin existe pour ( S , v ) si et seulement si v a un voisin w tel qu'il existe un chemin pour ( S  −  v , w ), qui peut être recherché à partir d'informations déjà calculées dans le programme dynamique.

Andreas Björklund a proposé une approche alternative utilisant le principe d'inclusion-exclusion pour réduire le problème de comptage du nombre de cycles hamiltoniens à un problème de comptage plus simple, de comptage de couvertures de cycles, qui peut être résolu en calculant certains déterminants matriciels. En utilisant cette méthode, il a montré comment résoudre le problème du cycle hamiltonien dans des graphes arbitraires à n sommets par un algorithme de Monte Carlo en temps O(1.657 n ); pour les graphes bipartites, cet algorithme peut être encore amélioré au temps o (1,415 n ).

Pour les graphes de degré trois maximum, une recherche minutieuse de retour en arrière peut trouver un cycle hamiltonien (s'il existe) dans le temps O(1.251 n ).

Les chemins et cycles hamiltoniens peuvent être trouvés à l'aide d'un solveur SAT .

En raison de la difficulté de résoudre les problèmes de chemin et de cycle hamiltoniens sur des ordinateurs conventionnels, ils ont également été étudiés dans des modèles informatiques non conventionnels. Par exemple, Leonard Adleman a montré que le problème du chemin hamiltonien peut être résolu à l'aide d'un ordinateur à ADN . En exploitant le parallélisme inhérent aux réactions chimiques, le problème peut être résolu en utilisant un certain nombre d'étapes de réaction chimique linéaires en nombre de sommets du graphe ; cependant, il faut un nombre factoriel de molécules d'ADN pour participer à la réaction.

Une solution optique au problème hamiltonien a également été proposée. L'idée est de créer une structure de type graphique faite de câbles optiques et de séparateurs de faisceaux traversés par la lumière afin de construire une solution au problème. Le point faible de cette approche est la quantité d'énergie requise qui est exponentielle en nombre de nœuds.

Complexité

Le problème de trouver un cycle ou un chemin hamiltonien est en FNP ; le problème de décision analogue consiste à tester s'il existe un cycle ou un chemin hamiltonien. Les problèmes du cycle hamiltonien dirigé et non dirigé étaient deux des 21 problèmes NP-complets de Karp . Ils restent NP-complets même pour des types de graphes particuliers, tels que :

Cependant, pour certaines classes spéciales de graphes, le problème peut être résolu en temps polynomial :

  • Les graphes planaires 4-connectés sont toujours hamiltoniens par un résultat dû à Tutte , et la tâche de calcul consistant à trouver un cycle hamiltonien dans ces graphes peut être effectuée en temps linéaire en calculant un chemin dit de Tutte .
  • Tutte a prouvé ce résultat en montrant que chaque graphe planaire 2-connexe contient un chemin de Tutte. Les chemins de Tutte à leur tour peuvent être calculés en temps quadratique même pour des graphes planaires 2-connexes, qui peuvent être utilisés pour trouver des cycles hamiltoniens et des cycles longs dans des généralisations de graphes planaires.

En mettant toutes ces conditions ensemble, il reste ouvert si les graphes planaires bipartis réguliers 3-connexes doivent toujours contenir un cycle hamiltonien, auquel cas le problème limité à ces graphes ne pourrait pas être NP-complet ; voir la conjecture de Barnette .

Dans les graphes dans lesquels tous les sommets ont un degré impair, un argument lié au lemme de prise de contact montre que le nombre de cycles hamiltoniens passant par une arête fixe est toujours pair, donc si un cycle hamiltonien est donné, un deuxième doit également exister. Cependant, trouver ce deuxième cycle ne semble pas être une tâche de calcul facile. Papadimitriou a défini la classe de complexité PPA pour encapsuler des problèmes tels que celui-ci.

Les références

Médias liés au problème de chemin hamiltonien sur Wikimedia Commons