Ein Hamiltonkreis ist ein geschlossener Kantenzug, der jeden Knoten eines Graphen genau einmal besucht und zum Startknoten zurückkehrt. Benannt ist er nach dem Mathematiker William Rowan Hamilton (1805–1865), dessen Icosian-Spiel eine Rundreise über die Ecken eines Dodekaeders verlangte. Anders als der verwandte Eulerkreis (jede Kante genau einmal) ist der Hamiltonkreis überraschend schwer zu finden: Das Entscheidungsproblem ist NP-vollständig — es gibt kein einfaches Kriterium, das Existenz oder Nichtexistenz zuverlässig beantwortet.
Hinreichende Kriterien
Zwei klassische Sätze geben Bedingungen, die einen Hamiltonkreis garantieren (aber nicht notwendig sind): Der Satz von Dirac verlangt, dass jeder Knoten Grad ≥ n/2 hat (n = Knotenzahl). Der Satz von Ore verallgemeinert ihn: Für jedes Paar nicht benachbarter Knoten u, v muss grad(u) + grad(v) ≥ n gelten. Erfüllt ein Graph keines der Kriterien, kann er trotzdem einen Hamiltonkreis besitzen — die Sätze helfen nur beim Beweis, nicht bei der Suche.
Algorithmen und Komplexität
Praktische Verfahren sind Backtracking (systematisches Probieren mit Rücksetzen) und die dynamische Programmierung nach Held–Karp mit O(n² · 2ⁿ) — für kleine n die schnellste exakte Methode. Das Traveling-Salesman-Problem (TSP) ist die gewichtete Variante: Statt nur zu fragen, ob ein Kreis existiert, sucht es den kürzesten gewichteten Rundweg — ebenfalls NP-vollständig, aber mit großartigen Näherungsalgorithmen.
Anwendungen
- Rundreisen- und Tourenplanung in Logistik und Pendlerverkehr.
- Schaltkreis-Design: Jede Komponente genau einmal ansteuern.
- Krypto- und Codierungstheorie: De-Bruijn-Folgen als Hamiltonkreise im De-Bruijn-Graph.
Abgrenzung und Beispiele
In einem bipartiten Graphen kann ein Hamiltonkreis nur existieren, wenn beide Teilmengen gleich groß sind (jede Kante wechselt die Seite). In gerichteten Graphen spricht man analog vom gerichteten Hamiltonkreis. Der Hamiltonkreis nutzt Knoten und Kanten der Graph-Datenstruktur; er liegt stets innerhalb einer Zusammenhangskomponente und ist selbst ein Zyklus, der alle Knoten einsammelt. Kontrast-Beispiel: Ein einzelner Stern mit vielen Blättern hat keinen Hamiltonkreis, weil das Zentrum mehrfach passiert werden müsste.