Hamiltonscher-Pfad-Prüfer

Was ist ein Hamiltonscher Pfad?

A Hamiltonscher Pfad is a path through a graph that visits every vertex exactly once. The concept is named after the Irish mathematician Sir William Rowan Hamilton, who in 1857 devised the Icosian game — a puzzle asking players to find a cycle that traverses all 20 vertices of a dodecahedron graph. Unlike an Eulerian path, which traverses every edge exactly once, a Hamiltonscher Pfad is concerned exclusively with vertices: each must be visited once and only once.

Hamiltonscher Pfad vs. Eulerscher Pfad

These two classical problems look similar but differ fundamentally in complexity. An Eulerian path (visiting every edge once) has a clean, efficient solution: Hierholzer's algorithm runs in O(E) time, and a simple rule — at most two vertices of odd degree — decides whether one exists. By contrast, deciding whether a Hamiltonscher Pfad exists is NP-complete. This means no polynomial-time algorithm is known, and the problem is believed to require exponential time in the worst case for general graphs.

Hamiltonscher Kreis

A Hamiltonian cycle (also called a Hamiltonian circuit) is a Hamiltonscher Pfad that returns to its starting vertex, forming a closed loop. Every graph that has a Hamiltonian cycle also has a Hamiltonscher Pfad (just delete one edge), but the reverse is not true. For example, a simple path graph 1–2–3–4 has a Hamiltonscher Pfad but no Hamiltonian cycle, since vertex 4 cannot return to vertex 1 without revisiting 2 or 3.

Satz von Dirac (1952)

Der Satz von Dirac, 1952 bewiesen, liefert die am häufigsten zitierte hinreichende Bedingung: Wenn in einem Graphen mit n ≥ 3 Knoten jeder Knoten einen Grad von mindestens n/2 hat, enthält der Graph einen Hamiltonschen Kreis.

Satz von Ore (1960)

Der Satz von Ore (1960) verallgemeinert das Ergebnis von Dirac. Er besagt: Wenn für jedes Paar nicht-benachbarter Knoten u und v die Summe ihrer Grade deg(u) + deg(v) ≥ n erfüllt, existiert ein Hamiltonscher Kreis.

Backtracking-Algorithmus

This checker uses a backtracking depth-first search to find Hamiltonscher Pfads. Starting from a chosen vertex, the algorithm tries to extend the current path by appending an unvisited adjacent vertex. If no valid extension exists and the path does not yet span all vertices, it backtracks — removing the last vertex and trying the next candidate. When the path reaches all n vertices, a Hamiltonscher Pfad is recorded. If the last vertex is also adjacent to the start, a Hamiltonian cycle is found. To protect browser performance, the search stops after 100,000 recursive calls.

Anwendungen Hamiltonscher Pfade

• Problem des Handlungsreisenden (TSP): Finden des kürzesten Hamiltonschen Kreises in einem gewichteten Graphen.
• DNA Fragment Assembly: Sequencing short DNA reads can be modeled as finding a Hamiltonscher Pfad through an overlap graph.
• Scheduling and Sequencing: Job scheduling where each job must be done once and job-to-job transitions are constrained maps to Hamiltonscher Pfad existence.
• Knight's Tour: The chess knight's tour problem — visiting every square of a chessboard exactly once — is a Hamiltonscher Pfad problem on the knight-move graph.
• Gray-Codes: Ein binärer Gray-Code entspricht einem Hamiltonschen Kreis auf einem hyperkubischen Graphen.
• Network Routing: Certain routing protocols require visiting every node once; the existence question is exactly the Hamiltonscher Pfad problem.

NP-Vollständigkeit

Richard Karps Arbeit von 1972 führte das Hamilton-Kreis-Problem als eines der 21 NP-vollständigen Probleme auf. Für Graphen mit bis zu etwa 15 Knoten ist Backtracking in der Praxis machbar, für größere Instanzen sind Heuristiken erforderlich.

Referenz: Hamiltonsche Eigenschaften klassischer Graphen