Ein Hamilton-Pfad (auch Hamiltonweg oder hamiltonscher Weg) ist ein Pfad in einem Graphen, der jeden Knoten genau einmal besucht — ohne am Ende zum Startknoten zurückzukehren. Benannt ist er nach dem irischen Mathematiker William Rowan Hamilton, der 1857 das berühmte Icosian-Spiel entwickelte, bei dem auf einem Dodekaeder-Graphen eine Tour durch alle Ecken gefunden werden musste.
Definition
In einem Graphen mit n Knoten ist ein Hamilton-Pfad eine Folge v1, v2, ..., vn aus n verschiedenen Knoten, bei der aufeinanderfolgende Knoten stets durch eine Kante verbunden sind. Der Pfad nutzt also genau n−1 Kanten und lässt keinen Knoten aus. Der Unterschied zum Hamiltonkreis ist die Rückkehr: Ein Kreis ist ein geschlossener Pfad, der nach dem letzten Knoten wieder beim ersten ankommt.
Eigenschaften
- Jeder Hamiltonkreis enthält einen Hamilton-Pfad: Man entfernt einfach eine beliebige Kante des Kreises.
- Die Umkehrung gilt nicht: Ein einfacher Pfadgraph (eine linienförmige Kette von Knoten) besitzt immer einen Hamilton-Pfad, aber nie einen Hamiltonkreis.
- Ein Graph kann ohne zusätzliche Bedingungen beliebig viele Kanten haben und trotzdem keinen Hamilton-Pfad besitzen — die Struktur entscheidet, nicht die Dichte.
Existenz und Komplexität
Die Frage, ob ein gegebener Graph einen Hamilton-Pfad enthält, ist NP-vollständig — es gibt keinen bekannten effizienten Algorithmus, der sie in Polynomialzeit beantwortet. In der Praxis nutzt man deshalb Backtracking mit geschicktem Pruning oder dynamische Programmierung (Held-Karp-Verfahren, Laufzeit O(2ⁿ·n²)).
Es gibt aber hinreichende Kriterien, die die Existenz garantieren. Eine Pfad-Variante des Ore-Satzes besagt: Sind die Grad-Summen zweier nicht benachbarter Knoten mindestens n−1, dann existiert ein Hamilton-Pfad. In Turniergraphen, also vollständig gerichteten Graphen, gilt der Satz von Rédei: Dort existiert immer ein Hamilton-Pfad.
Anwendungen
- Routenplanung ohne Rückkehr, etwa Touren, die jeden Ort genau einmal ansteuern und nicht zum Ausgangspunkt zurückkehren.
- Gray-Codes: Ein Gray-Code zählt binäre Zahlen so auf, dass sich benachbarte Codes in genau einem Bit unterscheiden — die Aufzählung entspricht einem Hamilton-Pfad im Hyperwürfel-Graphen.
- Kryptografie und Logistik: Das Traveling-Salesman-Problem ist die gewichtete Variante des Hamiltonkreis-Problems und wird in vielen Optimierungsaufgaben angenähert.
Verwandte Grundlagen: Graph-Datenstruktur, Knoten, Kante, ungerichteter Graph sowie der Eulerpfad, der statt der Knoten die Kanten genau einmal besucht.