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

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?

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.)

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.

"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 que$\mathrm{HamPath}$ n'est pas dans $\mathsf{P}$! Quelqu'un pourrait un jour trouver une caractérisation très intelligente de$\mathrm{HamPath}$ (similaire à la caractérisation de $\mathrm{EulerPath}$ comme ayant des degrés pairs) qui le mettraient à l'intérieur $\mathsf{P}$.

La plupart des gens croient que ce n’est pas$\mathsf{P}$mais ce n'est pas prouvé. Les arguments (pas la preuve!) Pour expliquer pourquoi il est peu probable$\mathsf{P}$ est le même que les arguments pour $\mathsf{P} \neq \mathsf{NP}$ et la plupart d'entre eux ne disent pas grand-chose $\mathrm{HamPath}$ lui-même autre que le fait qu'il est $\mathsf{NP\text{-}complete}$.

Maintenant, vous pouvez vous demander pourquoi $\mathrm{HamPath}$ est $\mathsf{NP\text{-}complete}$ mais on ne peut pas le montrer $\mathsf{EulerPath}$ est $\mathsf{NP\text{-}complete}$? Parce que quelqu'un a trouvé une caractérisation de celui-ci qui est en$\mathsf{P}$ puis la réponse serait similaire à la raison pour laquelle nous pensons que $\mathsf{P} \neq \mathsf{NP}$ il est donc peu probable (mais pas prouvé!) que $\mathsf{EulerPath}$ est $\mathsf{NP\text{-}complete}$.

Voici une façon rapide de voir les choses. Le problème HAM-PATH est$\mathsf{NP}$-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, est$\mathsf{P}$car nous avons des algorithmes polynomiaux de temps pour cela. Une$\mathsf{NP}$-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 $\mathsf{P}$, disons trouver un chemin eulérien.