Im mathematischen Feld der Graph-Theorie sind das Pfad-Problem von Hamiltonian und das Zyklus-Problem von Hamiltonian Probleme der Bestimmung, ob ein Pfad von Hamiltonian oder ein Zyklus von Hamiltonian in einem gegebenen Graphen (entweder geleitet oder ungeleitet) bestehen. Beide Probleme sind NP-complete.

Beziehung zwischen Problemen

Es gibt eine einfache Beziehung zwischen den Problemen, einen Pfad von Hamiltonian und einen Zyklus von Hamiltonian zu finden. In einer Richtung ist das Pfad-Problem von Hamiltonian für den Graphen G zum Zyklus-Problem von Hamiltonian in einem Graphen H erhalten bei G durch das Hinzufügen eines neuen Scheitelpunkts und das Anschließen davon mit allen Scheitelpunkten von G gleichwertig. So kann die Entdeckung eines Pfads von Hamiltonian nicht (im Grenzfall, als eine Funktion der Zahl von Scheitelpunkten) bedeutsam langsamer sein als Entdeckung eines Zyklus von Hamiltonian.

In der anderen Richtung hat ein Graph G einen Zyklus von Hamiltonian mit dem Rand uv, wenn, und nur wenn der Graph H erhalten bei G durch das Ersetzen des Randes durch ein Paar des Grads 1 Scheitelpunkte, ein verbundener zu u und ein verbundener zu v, einen Pfad von Hamiltonian hat. Deshalb, durch das Versuchen dieses Ersatzes für das ganze Rand-Ereignis zu einem gewählten Scheitelpunkt von G, kann das Zyklus-Problem von Hamiltonian durch beim grössten Teil der n Pfad-Berechnung von Hamiltonian behoben werden, wo n die Zahl von Scheitelpunkten im Graphen ist.

Das Hamiltonian Zyklus-Problem ist auch ein spezieller Fall des Handlungsreisender-Problems, das durch das Setzen der Entfernung zwischen zwei Städten zu derjenigen erhalten ist, wenn sie angrenzend sind und zwei sonst.

Algorithmen

Es gibt n! verschiedene Folgen von Scheitelpunkten, die Pfade von Hamiltonian in einem gegebenen N-Scheitelpunkt-Graphen sein könnten (und, sind in einem ganzen Graphen), so würde ein Suchalgorithmus der rohen Gewalt, der alle möglichen Folgen prüft, sehr langsam sein. Statt dessen kann ein dynamischer Programmieralgorithmus des Öffentlichen Ausrufers, Gehalten, und Karp verwendet werden, um das Problem rechtzeitig O (n 2) zu beheben. In dieser Methode bestimmt man, für jeden Satz S Scheitelpunkte und jedes Scheitelpunkts v in S, ob es einen Pfad gibt, der genau die Scheitelpunkte in S und Enden an v bedeckt. Für jede Wahl von S und v besteht ein Pfad dafür (S, v), wenn, und nur wenn v einen solchen Nachbarw hat, dass ein Pfad dafür besteht (S − v, w), der von der bereits geschätzten Information im dynamischen Programm nachgeschlagen werden kann.

Andreas Björklund hat eine alternative Annäherung mit dem Einschließungsausschluss-Grundsatz zur Verfügung gestellt, um das Problem zu reduzieren, die Zahl von Zyklen von Hamiltonian zu einem einfacheren zählenden Problem, vom Zählen von Zyklus-Deckel aufzuzählen, die durch die Computerwissenschaft bestimmter Matrixdeterminanten gelöst werden können. Mit dieser Methode hat er gezeigt, wie man das Zyklus-Problem von Hamiltonian in willkürlichen N-Scheitelpunkt-Graphen durch einen Algorithmus von Monte Carlo rechtzeitig O (1.657) behebt; für zweiteilige Graphen kann dieser Algorithmus weiter zur Zeit O (1.414) verbessert werden.

Für Graphen des maximalen Grads drei kann eine sorgfältige denselben Weg zurückverfolgende Suche einen Zyklus von Hamiltonian finden (wenn man besteht) rechtzeitig O (1.251).

Wegen der Schwierigkeit, den Pfad von Hamiltonian und die Zyklus-Probleme auf herkömmlichen Computern zu lösen, sind sie auch in unkonventionellen Modellen der Computerwissenschaft studiert worden. Zum Beispiel,

Leonard Adleman hat gezeigt, dass das Pfad-Problem von Hamiltonian mit einem DNA-Computer behoben werden kann. Den chemischen Reaktionen innewohnenden Parallelismus ausnutzend, kann das Problem mit mehreren chemischen Reaktionsschritten behoben werden, die in der Zahl von Scheitelpunkten des Graphen geradlinig sind; jedoch verlangt es, dass eine factorial Zahl von verschiedenen Typen des DNA-Moleküls an der Reaktion teilnimmt.

Kompliziertheit

Das Problem, einen Zyklus von Hamiltonian oder Pfad zu finden, ist in FNP; das analoge Entscheidungsproblem ist zu prüfen, ob ein Zyklus von Hamiltonian oder Pfad bestehen. Die geleiteten und ungeleiteten Zyklus-Probleme von Hamiltonian waren zwei von 21 NP-complete Problemen von Karp. Sie bleiben NP-complete sogar für ungeleitete planare Graphen des maximalen Grads drei, für geleitete planare Graphen mit indegree und outdegree höchstens zwei, für bridgeless ungeleitete planare 3-regelmäßige zweiteilige Graphen, und für 3-verbundene 3-regelmäßige zweiteilige Graphen. Jedoch, alle diese Bedingungen zusammenstellend, bleibt es offen, ob 3-verbundene 3-regelmäßige zweiteilige planare Graphen immer einen Zyklus von Hamiltonian enthalten müssen, in welchem Fall das auf jene Graphen eingeschränkte Problem NP-complete nicht sein konnte; sieh die Vermutung von Barnette.

In Graphen, in denen alle Scheitelpunkte sonderbaren Grad haben, zeigt ein mit dem handshaking Lemma verbundenes Argument, dass die Zahl von Zyklen von Hamiltonian durch jeden festen Rand immer sogar so ist, wenn ein Zyklus von Hamiltonian gegeben wird, dann muss ein zweiter auch bestehen. Jedoch scheint die Entdeckung dieses zweiten Zyklus nicht, eine leichte rechenbetonte Aufgabe zu sein. Papadimitriou hat die Kompliziertheitsklasse PPA definiert, um Probleme wie dieser kurz zusammenzufassen.