Ist es intuitiv zu sehen, dass das Finden eines Hamilton-Pfades nicht in P ist, während das Finden eines Euler-Pfades ist?

Ich bin mir nicht sicher, ob ich es sehe. Soweit ich weiß, ergänzen sich Kanten und Eckpunkte, und es ist ziemlich überraschend, dass dieser Unterschied besteht.

Gibt es eine gute / schnelle / einfache Möglichkeit zu erkennen, dass es viel schwieriger sein sollte, einen Hamilton-Pfad zu finden, als einen Euler-Pfad?

Vielleicht hilft folgende Perspektive:

Wenn Sie versuchen, einen Eulerschen Pfad zu konstruieren, können Sie fast gierig vorgehen. Sie beginnen den Weg einfach irgendwo und versuchen, so lange wie möglich zu gehen. Wenn Sie einen Kreis erkennen, löschen Sie seine Kanten (zeichnen Sie jedoch auf, dass dieser Kreis erstellt wurde). Auf diese Weise zerlegen Sie das Diagramm in Kreise, die leicht zu einer Eulerschen Tour kombiniert werden können. Der Punkt ist, dass keine Ihrer Entscheidungen "wie man über das Diagramm geht" tatsächlich falsch sein kann. Sie werden immer erfolgreich sein und nie stecken bleiben.

Die Situation mit Hamilton-Pfaden ist anders. Auch hier möchten Sie möglicherweise einen Pfad erstellen, indem Sie entlang der Kanten des Diagramms gehen. Aber diesmal können Sie wirklich schlechte Entscheidungen treffen. Dies bedeutet, dass Sie den Pfad nicht fortsetzen können, aber nicht alle Scheitelpunkte besucht wurden. Was Sie tun können, ist Back-Track. Das bedeutet, dass Sie einige Ihrer alten Entscheidungen rückgängig machen und einen anderen Weg einschlagen. Im Wesentlichen stützen sich alle Algorithmen, die für das allgemeine Problem bekannt sind, auf die eine oder andere Weise auf das Zurückverfolgen oder das Ausprobieren einer Vielzahl von Lösungen. Dies ist jedoch charakteristisch für NP-vollständige Probleme.

Fazit: Der Eulersche Pfad erfordert keine Rückverfolgung, der Hamiltonsche Pfad jedoch.

(Beachten Sie, dass möglicherweise P = NP und in diesem Fall ein cleverer Hamilton-Pfadalgorithmus vorhanden ist.)

Ein weiteres Detail, das Ihrer Intuition helfen kann, ist, dass ein Euler-Zyklus genau dann existiert, wenn jeder Scheitelpunkt einen geraden Grad hat. Ein ähnlicher Satz existiert für Euler-Pfade. Dies folgt aus einem ziemlich einfachen Beweis: Grundsätzlich müssen Sie jedes Mal, wenn Sie einen Scheitelpunkt besuchen, diesen verlassen, sodass jeder "Besuch" zwei vom Grad des Scheitelpunkts nimmt. Dies erklärt nicht, warum der Hamilton-Pfad schwierig ist (was wir natürlich nicht einmal wissen), aber es hilft zu erklären, warum es einfach ist, einen Euler-Pfad zu finden.

Victor Adamchik gibt eine OK-Erklärung für den Beweis. Die meisten Graphentheorie- / diskreten Mathematikbücher haben wahrscheinlich auch einen Beweis, den Sie möglicherweise leichter finden.

Die anderen Antworten geben eine gute Vorstellung davon, warum ein so einfacher Beweis für Hamilton-Zyklen nicht zu funktionieren scheint.

"Ist es intuitiv zu sehen, dass das Finden eines Hamilton-Pfades nicht in P ist, während das Finden eines Euler-Pfades ist?"

Die Annahmen in Ihrer Frage sind nicht korrekt.

$\mathrm{HamPath}$$\mathsf{P}$$\mathrm{HamPath}$$\mathrm{EulerPath}$$\mathsf{P}$

$\mathsf{P}$$\mathsf{P}$$\mathsf{P} \neq \mathsf{NP}$$\mathrm{HamPath}$$\mathsf{NP\text{-}complete}$

$\mathrm{HamPath}$$\mathsf{NP\text{-}complete}$$\mathsf{EulerPath}$$\mathsf{NP\text{-}complete}$$\mathsf{P}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{EulerPath}$$\mathsf{NP\text{-}complete}$

$\mathsf{NP}$$\mathsf{P}$$\mathsf{NP}$$\mathsf{P}$