Est-il intuitif de voir que trouver un chemin hamiltonien n'est pas dans P alors que trouver un chemin Euler l'est?

8

Je ne suis pas sûr de le voir. D'après ce que je comprends, les arêtes et les sommets sont des compléments l'un pour l'autre et il est assez surprenant que cette différence existe.

Existe-t-il un bon moyen / rapide / facile de voir qu'en fait, trouver un chemin hamiltonien devrait être beaucoup plus difficile que de trouver un chemin d'Euler?

Lazer
la source
1
Nous ne savons pas si le chemin hamiltonien est en P ou non.
Raphael

Réponses:

12

Peut-être que la perspective suivante aide:

Lorsque vous essayez de construire un chemin eulérien, vous pouvez procéder presque goulûment. Vous commencez simplement le chemin quelque part et essayez de marcher le plus longtemps possible. Si vous détectez un cercle, vous supprimerez ses bords (mais notez que ce cercle a été construit). Par cela, vous décomposez le graphique en cercles, qui peuvent être facilement combinés à une tournée eulérienne. Le fait est qu'aucune de vos décisions «comment parcourir le graphique» ne peut être fausse. Vous réussirez toujours et ne resterez jamais coincé.

La situation avec les chemins hamiltoniens est différente. Encore une fois, vous souhaiterez peut-être construire un chemin en parcourant les bords du graphique. Mais cette fois, vous pouvez vraiment prendre de mauvaises décisions. Cela signifie que vous ne pouvez pas continuer le chemin, mais tous les sommets n'ont pas été visités. Ce que vous pouvez faire, c'est revenir en arrière. Cela signifie que vous revenez sur certaines de vos anciennes décisions et continuez sur une voie différente. Essentiellement, tous les algorithmes connus pour le problème général reposent d'une manière ou d'une autre sur le back-tracking ou sur l'essai d'un large éventail de solutions. Ceci, cependant, est caractéristique des problèmes NP-complets.

Donc, en résumé (simplifié): le chemin eulérien ne nécessite aucun retour en arrière, mais le chemin hamiltonien en a besoin.

(Notez que cela pourrait être que P = NP et dans ce cas, un algorithme de chemin hamiltonien intelligent existerait.)

A.Schulz
la source
1
Ma réponse est plus une réponse brusque. Celui-ci est probablement plus quelque chose que le PO recherche.
Juho
1
non, nous ne savons pas si HamPath nécessite un retour en arrière!
Kaveh
2
@Kaveh: Je sais. C'est pourquoi j'ai écrit "... tous les algorithmes connus pour le problème général ...". Et j'ai aussi dit une ligne de fond simplifiée . Quoi qu'il en soit, j'ai reformulé légèrement la dernière déclaration.
A.Schulz
5

Un autre détail qui peut aider votre intuition est qu'un cycle d'Euler existe si et seulement si chaque sommet a un degré pair. Un théorème similaire existe pour les chemins d'Euler. Cela découle d'une preuve assez simple - fondamentalement, chaque fois que vous visitez un sommet, vous devez alors le quitter, de sorte que chaque "visite" prend deux fois le degré du sommet. Cela n'explique pas pourquoi le chemin hamiltonien est difficile (ce que, bien sûr, nous ne savons même pas réellement), mais cela aide à expliquer pourquoi trouver un chemin d'Euler est facile.

Victor Adamchik donne une explication OK de la preuve. La plupart des livres de théorie des graphes / mathématiques discrètes auront également une preuve que vous trouverez peut-être plus facile.

Les autres réponses donnent une bonne intuition pourquoi une preuve aussi simple ne semble pas fonctionner pour les cycles de Hamilton.

SamM
la source
2

"Est-il intuitif de voir que trouver un chemin hamiltonien n'est pas dans P alors que trouver le chemin Euler l'est?"

Les hypothèses de votre question ne sont pas correctes.

Notez que nous ne savons pas queHunemPuneth n'est pas dans P! Quelqu'un pourrait un jour trouver une caractérisation très intelligente deHunemPuneth (similaire à la caractérisation de EulerPuneth comme ayant des degrés pairs) qui le mettraient à l'intérieur P.

La plupart des gens croient que ce n’est pasPmais ce n'est pas prouvé. Les arguments (pas la preuve!) Pour expliquer pourquoi il est peu probableP est le même que les arguments pour PNP et la plupart d'entre eux ne disent pas grand-chose HunemPuneth lui-même autre que le fait qu'il est NP-complete.

Maintenant, vous pouvez vous demander pourquoi HunemPuneth est NP-complete mais on ne peut pas le montrer EulerPuneth est NP-complete? Parce que quelqu'un a trouvé une caractérisation de celui-ci qui est enP puis la réponse serait similaire à la raison pour laquelle nous pensons que PNP il est donc peu probable (mais pas prouvé!) que EulerPuneth est NP-complete.

Kaveh
la source
0

Voici une façon rapide de voir les choses. Le problème HAM-PATH estNP-complet, donc actuellement nous ne le faisons pas si cela peut être résolu en temps polynomial ou non. Au moins, personne n'a conçu un tel algorithme. Le problème du chemin eulérien, d'autre part, estPcar nous avons des algorithmes polynomiaux de temps pour cela. UneNP-un problème complet tel que HAM-PATH a jusqu'ici résisté aux attaques, c'est donc une façon immédiate de voir ou de croire qu'il est plus difficile qu'un problème dans P, disons trouver un chemin eulérien.

Juho
la source