Hamilton-Pfad-Prüfer

Hamilton-Pfad-Prüfer

Der Hamilton-Pfad-Prüfer entscheidet, ob ein Graph einen Hamiltonpfad (eine Folge, die jeden Knoten exakt einmal besucht) oder einen Hamiltonkreis (der zusätzlich zum Startknoten zurückkehrt) enthält. Er kombiniert schnelle strukturelle Vorabprüfungen (Konnektivität, Gradanforderungen, Dirac-Satz, Ore-Satz) mit einer Backtracking-Suche, die durch die Warnsdorff-Heuristik optimiert ist, und visualisiert den Zeugenpfad mit einer Schritt-für-Schritt-Animation.

Was ist ein Hamiltonpfad?

Gegeben sei ein Graph G = (V, E) mit n Knoten. Ein Hamiltonpfad ist eine geordnete Folge v₁, v₂, …, v_n aller Knoten, sodass jedes aufeinanderfolgende Paar (v_i, v_i+1) eine Kante von G ist und jeder Knoten exakt einmal vorkommt. Wenn zusätzlich (v_n, v₁) eine Kante ist, handelt es sich um einen Hamiltonkreis.

Das Problem ist nach William Rowan Hamilton benannt, der 1857 das Ikosianische Spiel erfand — ein Rätsel, bei dem man einen Kreis finden muss, der jeden Knoten eines regulären Dodekaeders exakt einmal besucht.

Warum es schwierig ist: NP-Vollständigkeit

Sowohl das Entscheidungsproblem für Hamiltonpfade als auch für Hamiltonkreise sind NP-vollständig (Karp, 1972). Sofern nicht P = NP gilt, existiert kein Algorithmus in Polynomialzeit, der jede Instanz löst. Im schlechtesten Fall exploriert Backtracking einen Suchbaum der Größe bis zu (n−1)! für einen Kreis. Aus diesem Grund begrenzt der Rechner die Eingabe auf 20 Knoten — eine kleine polynomielle Steigerung von n führt zu einem explosiven Anstieg der Laufzeit.

In der Praxis macht die Warnsdorff-Heuristik (ursprünglich 1823 von Heinrich Warnsdorff für das Springerproblem entwickelt) die Suche auf strukturierten Graphen drastisch schneller: Bei jedem Schritt erweitert der Algorithmus den aktuellen Pfad zum unbesuchten Nachbarn mit der geringsten Anzahl an verbleibenden unbesuchten Nachbarn. Diese gierige Regel verhindert oft, dass sich die Suche "festläuft".

Notwendige Bedingungen — Schnelle Ablehnung

Bevor eine aufwendige Suche gestartet wird, lehnt der Rechner Graphen ab, die unmöglich einen Hamiltonpfad enthalten können:

• Konnektivität. Ein Hamiltonpfad muss jeden Knoten besuchen, daher muss der Graph exakt eine zusammenhängende Komponente haben. Bei gerichteten Graphen ist schwacher Zusammenhang erforderlich.
• Grad (ungerichtet). Höchstens zwei Knoten dürfen den Grad 1 haben — diese sind die einzigen Kandidaten für die Endpunkte des Pfades. Für einen Hamiltonkreis muss jeder Knoten mindestens den Grad 2 haben.
• Grad (gerichtet). Für einen Hamiltonpfad darf höchstens ein Knoten den Eingangsgrad 0 haben (der Start) und höchstens einer den Ausgangsgrad 0 (das Ende). Für einen Hamiltonkreis muss jeder Knoten sowohl Eingangsgrad ≥ 1 als auch Ausgangsgrad ≥ 1 haben.

Hinreichende Bedingungen — Klassische Sätze

Mehrere klassische Sätze liefern hinreichende (aber nicht notwendige) Bedingungen, die einen Hamiltonkreis in ungerichteten einfachen Graphen garantieren. Falls einer dieser Sätze zutrifft, markiert der Rechner das Ergebnis als "GARANTIERT", ohne die Suche zwingend zu benötigen — zeigt aber dennoch einen Zeugenkreis an.

Satz von Dirac (1952)

Wenn G ein einfacher ungerichteter Graph mit n ≥ 3 Knoten ist und jeder Knoten einen Grad von mindestens n / 2 hat, dann besitzt G einen Hamiltonkreis.

Satz von Ore (1960)

Wenn für jedes Paar nicht benachbarter Knoten u und v gilt deg(u) + deg(v) ≥ n, dann hat G einen Hamiltonkreis. Die Ore-Bedingung ist schwächer als die von Dirac, somit impliziert Ore Dirac.

Der interne Suchalgorithmus

Wenn die Vorabprüfungen keine Klärung bringen, führt der Rechner eine Backtracking-Suche auf der Adjazenzdarstellung des Graphen aus. Wichtige Taktiken:

1. Bitmaske für besuchte Knoten. Die besuchten Knoten werden als Bitmaske gespeichert (schneller O(1)-Test für bis zu 20 Knoten).
2. Warnsdorff-Heuristik. Bei jeder Erweiterung werden Nachbarn in der Reihenfolge ihres verbleibenden Grads (kleinste zuerst) ausprobiert.
3. Wurzelauswahl. Für einen Hamiltonkreis wird nur ein Startknoten benötigt (Kreise sind rotationsinvariant). Für einen Hamiltonpfad werden Startknoten in aufsteigender Reihenfolge des Ausgangsgrads probiert.
4. Schritt-Budget. Eine harte Grenze verhindert, dass pathologische Instanzen unendlich laufen; das UI meldet bei Budgetüberschreitung ein "Timeout".

Hamilton vs. Euler

Man verwechselt Hamilton- und Euler-Probleme oft leicht — sie klingen ähnlich, sind aber grundlegend verschieden:

Unterstützte Eingabeformate

Kantenliste

Eine Kante pro Zeile oder durch Komma getrennt. Unterstützte Trenner: A-B, A B, A,B, A--B, A->B, A<-B. Verwenden Sie ->, um eine gerichtete Interpretation zu erzwingen.

Adjazenzmatrix

Quadratische Matrix aus 0/1-Werten, eine Reihe pro Zeile, Leerzeichen- oder Komma-getrennt. Geben Sie optionale Labels im Feld "Matrix-Labels" an; ansonsten wird A, B, C… automatisch verwendet.

Anwendung des Prüfers

1. Eingabeformat wählen — Kantenliste für kleine handgeschriebene Graphen, Adjazenzmatrix für Kopien aus Code oder Lehrbüchern.
2. Graph einfügen im Textbereich. Bei Matrix-Eingabe optional Knoten-Labels angeben.
3. Prüfmodus wählen: Nur Pfad, nur Kreis oder beides in einem Durchlauf.
4. Graphtyp wählen — Die Auto-Erkennung leitet die Gerichtetheit aus dem Pfeilstil (->) oder der Matrix-Symmetrie ab.
5. Hamilton-Eigenschaft prüfen klicken. Die Ergebnisseite zeigt das Urteil, die Vorabprüfung, Dirac-/Ore-Tests, den Zeugenpfad und eine interaktive Visualisierung.
6. Zeugen abspielen mit den Play-/Schritt-Reglern.

Fallbeispiel — Der Petersen-Graph

Der berühmte Petersen-Graph (10 Knoten, 15 Kanten) ist ein klassisches Beispiel für einen Graphen mit Hamiltonpfad, aber ohne Hamiltonkreis. Fügen Sie dies in das Feld für die Kantenliste ein:

Der Prüfer bestätigt: Hamiltonpfad gefunden (z. B. 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3), aber die erschöpfende Suche findet keine Möglichkeit, die Schleife zu schließen.

Häufig gestellte Fragen

Was ist ein Hamiltonpfad?

Ein Hamiltonpfad ist ein Weg durch einen Graphen, der jeden Knoten exakt einmal besucht. Er ist nach William Rowan Hamilton benannt. Da das Problem NP-vollständig ist, gibt es keinen bekannten Algorithmus, der es für alle Graphen in Polynomialzeit löst.

Wie unterscheidet sich ein Hamiltonkreis von einem Hamiltonpfad?

Ein Hamiltonkreis kehrt zu seinem Startknoten zurück. Jeder Hamiltonkreis enthält einen Hamiltonpfad (wenn man die schließende Kante weglässt), aber viele Graphen haben zwar einen Pfad, aber keinen Kreis.

Warum ist die Suche auf 20 Knoten begrenzt?

Hamiltonpfad-Probleme sind NP-vollständig. Die Laufzeit skaliert exponentiell. Über 20 Knoten hinaus sollten spezialisierte Solver wie Concorde oder Integer-Programming-Formulierungen verwendet werden.

Weiterführende Literatur

• Hamiltonweg — Wikipedia
• Satz von Dirac — Wikipedia
• Satz von Ore — Wikipedia

Erweiterte Rechenoperationen:

• Antilogarithmus Rechner
• Betafunktion-Rechner
• Binomialkoeffizient-Rechner
• Binomialverteilungsrechner
• Binär-Rechner
• Zentraler Grenzwertsatz Rechner
• Kombinatorik-Rechner
• Rechner für komplementäre Fehlerfunktion
• Komplexe Zahlen Rechner Empfohlen
• Entropie-Rechner
• Fehlerfunktion berechnen
• Rechner für exponentiellen Zerfall
• Exponentielle Zunahme Rechner
• Exponentielles Integral Rechner
• exponenten-rechner-hohe-präzision
• Fakultätsrechner
• Gammafunktion-Rechner
• Goldener Schnitt Rechner
• Halbwertszeit berechnen
• Prozentuale Wachstumsrate Rechner Empfohlen
• permutationsrechner
• Poisson-Verteilungsrechner
• Polynom Wurzeln Rechner mit detaillierten Schritten
• Wahrscheinlichkeitsrechner
• Wahrscheinlichkeitsverteilung Rechner
• Anteil-Rechner
• Mitternachtsformel Rechner
• Wissenschaftlicher Taschenrechner
• Wissenschaftliche Schreibweise Rechner
• Signifikante Stellen Rechner Neu
• Summe von Kuben Rechner
• Summe von positiven Ganzzahlen Rechner
• Summe von Quadratzahlen Rechner
• Wahrheitstabellen-Generator
• Mengenlehre-Rechner
• Venn-Diagramm-Generator (3 Mengen)
• Chinesischer Restsatz Rechner
• Euler Totient Funktion Rechner
• Erweiterter Euklidischer Algorithmus Rechner
• Modularer Multiplikativer Inverser Rechner
• Kettenbruch-Rechner
• Dijkstra Kürzester Weg Rechner
• Minimaler Spannbaum Rechner
• Graph Gradfolgen-Validator
• Derangement Subfaktorielle Rechner
• Stirling-Zahlen-Rechner
• Schubfachprinzip-Rechner
• Markov-Ketten Stationäre Verteilung Rechner
• rundungsrechner Neu
• Negativer Binomialverteilungsrechner Neu
• Permutationen mit Wiederholung Rechner Neu
• Modulare Exponentiationsrechner Neu
• Primitivwurzel-Rechner
• Boolesche Algebra Vereinfacher Neu
• Karnaugh-Diagramm (K-Map) Löser Neu
• Graphfärbung Rechner Neu
• Topologische Sortierung Rechner Neu
• Adjazenzmatrix-Rechner Neu
• Inklusions-Exklusions-Rechner Neu
• Solver für lineare Programmierung Neu
• Traveling Salesman Solver (TSP) Neu
• Hamilton-Pfad-Prüfer Neu
• Planarer Graph Prüfer Neu
• Netzwerkfluss-Rechner (Maximaler Fluss) Neu
• Stable Marriage Problem Löser Neu
• Gruppentheorie-Ordnungsrechner Neu
• Ring und Körperrechner Neu