| Suche | Knoten | Ergebnis |
|---|---|---|
| Reines Backtracking | – | – |
| Warnsdorff-Reihenfolge | – | – |
| Sackgassen- und Zusammenhangs-Prüfung | – | – |
| Alle drei | – | – |
Hamiltonweg-Explorer
1857 erfand William Rowan Hamilton ein Rätsel: Wandern Sie über die Kanten eines Dodekaeders so, dass Sie jede seiner 20 Ecken genau einmal berühren und dort enden, wo Sie begonnen haben. Eine solche Route heißt heute Hamiltonkreis. Sie ist leicht zu prüfen und im Allgemeinen schwer zu finden. Zeichnen Sie selbst eine auf Hamiltons Dodekaeder, einem Schachbrett oder einem Graphen, den Sie zeichnen, oder sehen Sie einer Backtracking-Suche zu, zählen Sie die Sackgassen, in die sie läuft, und sehen Sie, wie stark ein paar einfache Prüfungen die Suche kürzen. Wählen Sie einen Graphen und ein Ziel: einen Kreis, der zum Start zurückkehrt, oder einen Weg. Nachzeichnen: Klicken Sie auf eine Ecke, dann jeweils auf einen Nachbarn; gestrichelte Ringe zeigen, wohin es weitergeht. Ein Klick auf die letzte Ecke, Zurück oder Rückgängig nimmt einen Schritt zurück, Tipp nennt einen nächsten Schritt, der noch zum Ziel führt. Suche: Mit Start oder Schritt läuft eine Backtracking-Suche, die Ecken anhängt, bis es nicht weitergeht, und dann zurückgeht; rote Striche zeigen die Rückschritte, die Balken zählen die Knoten je Weglänge. Vor dem Start wählt ein Klick auf eine Ecke, wo die Suche beginnt. Die Kästchen schalten das Abschneiden ein und aus, Vergleichen lässt dieselbe Suche mit und ohne laufen, und Alle zählen zählt jeden Kreis oder Weg eines kleinen Graphen. Bearbeiten: Klicken fügt eine Ecke hinzu, ein Klick auf zwei Ecken verbindet oder trennt sie, Ziehen verschiebt eine, und Löschen entfernt die gewählte Ecke.
Wie es funktioniert
- Wählen Sie einen Graphen, etwa Hamiltons Dodekaeder, den Petersen-Graphen oder einen Springerzug, oder zeichnen Sie unter Bearbeiten einen eigenen, und wählen Sie als Ziel einen Kreis oder einen Weg.
- Klicken Sie beim Nachzeichnen auf eine Ecke und dann auf einen Nachbarn nach dem anderen. Zurück und Rückgängig nehmen einen Schritt zurück, und Tipp zeigt einen nächsten Schritt, der noch zum Ziel führt.
- Lassen Sie in der Suche mit Start oder Schritt das Backtracking nach einer Route suchen, schalten Sie das Abschneiden ein und aus, und sehen Sie mit Vergleichen, wie viele Knoten jede Variante braucht.
Hamilton gegen Euler
Ein Eulerweg benutzt jede Kante einmal; ein Hamiltonweg besucht jede Ecke einmal. Das klingt ähnlich, verhält sich aber ganz anders. Ob ein zusammenhängender Graph einen Eulerweg hat, entscheidet das Abzählen der Ecken ungeraden Grades, wie Euler 1736 zeigte: Er hat einen, wenn es keine oder zwei gibt. Für Hamiltonwege ist keine solche Regel bekannt. Die Frage, ob ein Graph einen Hamiltonkreis hat, ist NP-vollständig, eines der 21 Probleme auf Richard Karps Liste von 1972; ein schnelles Verfahren dafür lieferte also schnelle Verfahren für Tausende anderer schwerer Probleme. Es gibt Bedingungen, die manche Graphen entscheiden. Der Satz von Dirac aus dem Jahr 1952 sichert einen Hamiltonkreis zu, wenn jede Ecke mindestens den Grad n/2 hat, der von Ore aus dem Jahr 1960, wenn je zwei nicht verbundene Ecken Grade mit Summe mindestens n haben; eine Ecke vom Grad 1, eine Schnittecke oder zwei Farbklassen verschiedener Größe schließen einen aus.
Wie die Suche arbeitet
Backtracking baut den Weg Ecke für Ecke auf und nimmt, wenn es nicht weitergeht, den letzten Schritt zurück und probiert den nächsten Nachbarn. Es findet immer einen Hamiltonkreis, wenn es einen gibt, doch die Zahl der Teilwege kann exponentiell wachsen. Auf dem 5 × 5-Gitter, das keinen Hamiltonkreis hat, besucht reines Backtracking 153.745 Knoten, bevor es sicher ist. Zwei Prüfungen stoppen aussichtslose Wege früh: Eine unbesuchte Ecke mit weniger als zwei freien Nachbarn lässt sich nicht mehr in einen Kreis einfügen, und wenn die unbesuchten Ecken in getrennte Teile zerfallen, kann kein einzelner Weg sie abdecken. Mit beiden braucht derselbe Beweis 1.761 Knoten. Die Warnsdorff-Regel von 1823, die den Nachbarn mit den wenigsten Weiterzügen zuerst probiert, findet einen Springerzug auf dem 8 × 8-Brett von einer Ecke aus in 64 Zügen ohne eine einzige Sackgasse.
Häufig gestellte Fragen
Was ist der Unterschied zwischen einem Hamiltonweg und einem Hamiltonkreis?
Ein Hamiltonweg besucht jede Ecke eines Graphen genau einmal. Ein Hamiltonkreis tut dasselbe und kehrt dann über eine weitere Kante dorthin zurück, wo er begonnen hat, er kann also an jeder seiner Ecken beginnen. Jeder Graph mit einem Hamiltonkreis hat auch einen Hamiltonweg (lassen Sie eine Kante des Kreises weg), aber nicht umgekehrt: Der Petersen-Graph hat Hamiltonwege und keinen Hamiltonkreis.
Hat das Dodekaeder einen Hamiltonkreis?
Ja, 30 davon, wenn man jeden Kreis unabhängig von Start und Richtung einmal zählt. Hamilton machte daraus 1857 das Ikosianspiel, ein Brett mit den 20 Ecken eines flachgelegten Dodekaeders, die mit Konsonanten beschriftet waren, und verkaufte die Rechte für 25 Pfund an den Londoner Spielzeughersteller John Jaques and Son. Alle zählen findet die 30 Kreise in rund 1.400 Knoten.
Warum hat ein 5 × 5-Gitter keinen Hamiltonkreis?
Färben Sie die 25 Punkte wie ein Schachbrett: 13 bekommen die eine Farbe und 12 die andere, und jeder Schritt führt zur anderen Farbe. Ein Kreis wechselt die Farben rundherum, er braucht also von beiden gleich viele, was 13 und 12 nicht hergeben. Dasselbe Argument gilt für jedes Gitter mit einer ungeraden Anzahl von Punkten, für einen Springer auf einem 5 × 5- oder 7 × 7-Brett (ein Springer wechselt stets die Feldfarbe) und für den Herschel-Graphen, dessen zwei Klassen 6 und 5 Ecken haben. Ein Hamiltonweg bleibt möglich: Er beginnt und endet auf der größeren Farbe.
Wie findet die Warnsdorff-Regel einen Springerzug?
H. C. von Warnsdorff schlug 1823 vor, den Springer stets auf das Feld zu ziehen, von dem aus er die wenigsten Weiterzüge hat. Felder nahe den Rändern und Ecken, die leicht abgeschnitten werden, kommen so früh an die Reihe, solange der Springer noch hineinkommt. Die Regel ist eine Faustregel, keine Garantie, und Gleichstände müssen irgendwie gebrochen werden, doch auf einem 8 × 8-Brett vollendet sie meist einen Zug ohne Rückschritt. Mit Backtracking verbunden, wie in dieser App, findet sie offene Züge ab 5 × 5 und geschlossene auf dem 6 × 6- und dem 8 × 8-Brett.
Wie viele Hamiltonkreise hat ein vollständiger Graph?
(n − 1)!/2 für n ≥ 3. Halten Sie die Startecke fest; die übrigen n − 1 können in beliebiger Reihenfolge folgen, und jeder Kreis wird zweimal gezählt, einmal je Richtung. K₆ hat 5!/2 = 60 und K₁₀ hat 181.440. Das sind die Rundreisen, unter denen ein Handlungsreisender wählen muss, und darum hört das Ausprobieren aller so schnell auf, möglich zu sein.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor