Hamiltonsches Wegproblem - Hamiltonian path problem

In diesem Artikel geht es um das spezifische Problem der Bestimmung, ob ein Hamiltonscher Pfad oder Kreis in einem gegebenen Graphen existiert. Für die allgemeinen Konzepte der Graphentheorie siehe Hamilton-Pfad .

Auf dem mathematischen Gebiet der Graphentheorie sind das Hamiltonsche Pfadproblem und das Hamiltonsche Kreisproblem Probleme der Bestimmung, ob ein Hamiltonscher Weg (ein Weg in einem ungerichteten oder gerichteten Graphen, der jeden Knoten genau einmal besucht) oder ein Hamiltonkreis in einem gegebenen Graphen existiert ( ob gerichtet oder ungerichtet ). Beide Probleme sind NP-vollständig .

Das Hamilton-Zyklus-Problem ist ein Spezialfall des Travelling-Salesman-Problems , das man erhält, indem man die Entfernung zwischen zwei Städten auf eins setzt, wenn sie benachbart sind, und zwei andernfalls, und verifiziert, dass die zurückgelegte Gesamtentfernung gleich n ist (wenn ja, ist die Route ein Hamilton-Kreis; wenn kein Hamilton-Kreis vorhanden ist, ist der kürzeste Weg länger).

Reduktion zwischen dem Wegproblem und dem Kreisproblem

Die Probleme beim Auffinden eines Hamilton-Pfads und eines Hamilton-Kreises können wie folgt zusammenhängen:

  • In einer Richtung kann das Hamiltonsche Wegproblem für den Graphen G mit dem Hamiltonkreisproblem in einem aus G erhaltenen Graphen H in Beziehung gesetzt werden, indem ein neuer universeller Knoten x hinzugefügt wird , der x mit allen Knoten von G verbindet . Daher kann das Auffinden eines Hamilton-Pfads nicht wesentlich langsamer sein (im schlimmsten Fall als Funktion der Anzahl der Knoten) als das Auffinden eines Hamilton-Zyklus.
  • In der anderen Richtung ist das Hamiltonsche Kreisproblem für einen Graphen G äquivalent zum Hamiltonschen Wegproblem im Graphen H, das durch Hinzufügen von terminalen ( Grad- eins) Knoten s und t an einem Knoten v von G bzw. an v' erhalten wird, eine gespaltene Kopie von v, die v' dieselbe Umgebung wie v gibt . Der Hamilton-Weg in H , der durch die Knoten svx-...-y-v'-t verläuft, entspricht dem Hamilton-Kreis in G , der durch vx-...-y(-v) verläuft .

Algorithmen

Es gibt n ! verschiedene Folgen von Scheitelpunkten, die Hamiltonsche Pfade in einem gegebenen n- Scheitelpunktgraphen sein könnten (und in einem vollständigen Graphen sind ), so dass ein Brute-Force- Suchalgorithmus, der alle möglichen Folgen testet, sehr langsam wäre. Ein früher exakter Algorithmus zum Auffinden eines Hamiltonschen Kreises auf einem gerichteten Graphen war der Aufzählungsalgorithmus von Martello. Ein Suchverfahren von Frank Rubin teilt die Kanten des Graphen in drei Klassen ein: solche, die im Pfad liegen müssen, solche, die nicht im Pfad liegen können, und unentschieden. Während die Suche fortschreitet, klassifiziert ein Satz von Entscheidungsregeln die unentschiedenen Kanten und bestimmt, ob die Suche angehalten oder fortgesetzt werden soll. Der Algorithmus unterteilt den Graphen in Komponenten, die separat gelöst werden können. Außerdem kann ein dynamischer Programmieralgorithmus von Bellman, Held und Karp verwendet werden, um das Problem in der Zeit O( n 2  2 n ) zu lösen . Bei diesem Verfahren bestimmt man für jede Menge S von Ecken und jede Ecke v in S , ob es einen Pfad gibt, der genau die Ecken in S abdeckt und bei v endet . Für jede Wahl von S und v existiert ein Pfad für ( S , v ) genau dann, wenn v einen Nachbarn w hat, so dass ein Pfad für ( S  −  v , w ) existiert, der aus bereits berechneten Informationen nachgeschlagen werden kann im dynamischen Programm.

Andreas Björklund stellte einen alternativen Ansatz vor, der das Inklusions-Ausschluss-Prinzip verwendet , um das Problem des Zählens der Anzahl von Hamilton-Zyklen auf ein einfacheres Zählproblem, des Zählens von Zyklusüberdeckungen, zu reduzieren, das durch Berechnung bestimmter Matrixdeterminanten gelöst werden kann. Mit dieser Methode zeigte er, wie das Problem des Hamilton-Zyklus in beliebigen n- Eckpunkt-Graphen durch einen Monte-Carlo-Algorithmus in der Zeit O(1.657 n ) gelöst werden kann ; für bipartite Graphen kann dieser Algorithmus bis zum Zeitpunkt o (1.415 n ) weiter verbessert werden .

Für Graphen maximalen Grades drei kann eine sorgfältige Backtracking-Suche einen Hamilton-Zyklus (falls vorhanden) in der Zeit O(1.251 n ) finden.

Hamiltonsche Pfade und Zyklen können mit einem SAT-Löser gefunden werden .

Wegen der Schwierigkeit, die Hamiltonschen Pfad- und Zyklusprobleme auf herkömmlichen Computern zu lösen, wurden sie auch in unkonventionellen Computermodellen untersucht. Leonard Adleman zeigte zum Beispiel, dass das Hamiltonsche Pfadproblem mit einem DNA-Computer gelöst werden kann . Unter Ausnutzung der den chemischen Reaktionen inhärenten Parallelität kann das Problem gelöst werden, indem eine Anzahl chemischer Reaktionsschritte verwendet wird, die in der Anzahl der Ecken des Graphen linear sind; es erfordert jedoch eine faktorielle Anzahl von DNA-Molekülen, um an der Reaktion teilzunehmen.

Eine optische Lösung des Hamilton-Problems wurde ebenfalls vorgeschlagen. Die Idee ist, eine graphische Struktur aus optischen Kabeln und Strahlteilern zu schaffen, die von Licht durchquert werden, um eine Lösung für das Problem zu konstruieren. Der Schwachpunkt dieses Ansatzes ist die erforderliche Energiemenge, die in der Anzahl der Knoten exponentiell ist.

Komplexität

Das Problem, einen Hamiltonschen Kreis oder Weg zu finden, liegt in FNP ; das analoge Entscheidungsproblem besteht darin, zu testen, ob ein Hamilton-Kreis oder -Weg existiert. Die gerichteten und ungerichteten Hamilton-Kreisprobleme waren zwei von Karps 21 NP-vollständigen Problemen . Sie bleiben auch für spezielle Arten von Graphen NP-vollständig, wie zum Beispiel:

Für einige spezielle Klassen von Graphen kann das Problem jedoch in polynomieller Zeit gelöst werden:

  • 4-zusammenhängende planare Graphen sind immer Hamiltonsch durch ein Tutte- Ergebnis , und die Rechenaufgabe, einen Hamiltonschen Kreis in diesen Graphen zu finden, kann in linearer Zeit durch Berechnung eines sogenannten Tutte-Pfads durchgeführt werden .
  • Tutte bewies dieses Ergebnis, indem er zeigte, dass jeder 2-zusammenhängende planare Graph einen Tutte-Pfad enthält. Tutte-Pfade wiederum können in quadratischer Zeit sogar für 2-zusammenhängende planare Graphen berechnet werden, was verwendet werden kann, um Hamiltonsche Kreise und lange Kreise in Verallgemeinerungen planarer Graphen zu finden.

Nimmt man all diese Bedingungen zusammen, bleibt offen, ob 3-zusammenhängende 3-reguläre bipartite planare Graphen immer einen Hamilton-Kreis enthalten müssen, in welchem ​​Fall das auf diese Graphen beschränkte Problem nicht NP-vollständig sein könnte; siehe Barnettes Vermutung .

In Graphen, in denen alle Ecken einen ungeraden Grad haben, zeigt ein Argument im Zusammenhang mit dem Handshaking-Lemma , dass die Anzahl der Hamilton-Zyklen durch jede feste Kante immer gerade ist. Wenn also ein Hamilton-Zyklus gegeben ist, muss auch ein zweiter existieren. Das Auffinden dieses zweiten Zyklus scheint jedoch keine einfache Rechenaufgabe zu sein. Papadimitriou hat die Komplexitätsklasse PPA definiert , um Probleme wie dieses zu kapseln.

Verweise

Medien zum Hamilton-Pfadproblem bei Wikimedia Commons