Hamiltonwege und Hamiltonkreise erklärt
Zeichnen Sie fünf Punkte im Kreis, verbinden Sie jeden mit seinen zwei Nachbarn, und Sie können einmal rundherum durch jeden Punkt gehen und heimkehren: ein Hamiltonkreis. Fügen Sie ein paar Kanten hinzu oder nehmen Sie welche weg, und die Frage wird überraschend schwer. Ob ein Graph einen solchen Kreis hat, gehört zu den bekanntesten Problemen, die kein Computer bisher für jeden Graphen schnell beantworten kann.
Jede Ecke einmal
Ein Graph ist eine Menge von Punkten, den Ecken, die durch Linien, die Kanten, verbunden sind. Ein Hamiltonweg läuft über Kanten und besucht jede Ecke genau einmal; ein Hamiltonkreis kehrt außerdem dorthin zurück, wo er begonnen hat, er hat also so viele Kanten wie Ecken. Ein Graph mit einem Hamiltonkreis heißt hamiltonsch. Eine vorgeschlagene Route zu prüfen ist leicht: Ecken zählen und jeden Schritt ansehen. Eine zu finden oder zu zeigen, dass es keine gibt, ist der schwere Teil, denn die Zahl der Reihenfolgen, in denen die Ecken besucht werden könnten, wächst wie n!, bei 20 Ecken bereits 2,4 × 10¹⁸.
Hamiltons Ikosianspiel
William Rowan Hamilton, der irische Mathematiker, der die Quaternionen entdeckte, erfand 1857 das Ikosianspiel. Sein Brett zeigte ein in die Ebene flachgelegtes Dodekaeder mit 20 durch Konsonanten bezeichneten Ecken, und die Hauptaufgabe war, Stifte mit den Nummern 1 bis 20 so auf die Ecken zu setzen, dass aufeinanderfolgende Zahlen, und 20 und 1, durch Kanten verbunden sind. Hamilton verkaufte die Rechte für 25 Pfund an den Londoner Spielzeughersteller John Jaques and Son, der es 1859 herausbrachte; es verkaufte sich schlecht. Das Rätsel hat 30 Lösungen, wenn man einen Kreis unabhängig von Start und Richtung einmal zählt. Die Frage selbst war nicht neu: Thomas Kirkman hatte 1855 in einer an die Royal Society gesandten Arbeit gefragt, welche Polyeder einen Kreis durch alle ihre Ecken haben, und eines gezeigt, das keinen hat.
Springerzüge
Ein Springerzug zieht einen Schachspringer so, dass er auf jedem Feld genau einmal landet: ein Hamiltonweg in dem Graphen, dessen Ecken die Felder und dessen Kanten die Springerzüge sind. Ein geschlossener Zug endet einen Springerzug vom Start entfernt, also ein Hamiltonkreis. Schachspieler stellten solche Aufgaben schon vor mehr als tausend Jahren, und Euler untersuchte sie in einer Arbeit von 1759. 1823 schlug H. C. von Warnsdorff vor, stets auf das Feld mit den wenigsten Weiterzügen zu ziehen; diese einfache Regel vollendet meist einen Zug über ein 8 × 8-Brett ohne Rückschritt. Ein Springer wechselt stets die Feldfarbe, ein geschlossener Zug braucht also gleich viele helle wie dunkle Felder, was Bretter mit einer ungeraden Anzahl von Feldern ausschließt. Allen Schwenk zeigte 1991 genau, welche rechteckigen Bretter einen geschlossenen Zug haben; unter den quadratischen hat ihn jedes mit gerader Seite ab 6. Das übliche Schachbrett hat 13.267.364.410.532 geschlossene Züge, von Brendan McKay 1997 gezählt.
Graphen ohne Hamiltonkreis
Die schnellsten Beweise, dass es keinen Kreis gibt, sind Abzählargumente. Lassen sich die Ecken mit zwei Farben so färben, dass jede Kante verschiedene Farben verbindet, so wechselt ein Kreis ab und braucht von jeder Farbe gleich viele Ecken; ein 5 × 5-Gitter hat 13 der einen und 12 der anderen, es hat also keinen Hamiltonkreis. Eine Schnittecke, deren Entfernen den Graphen zerlegt, müsste zweimal durchlaufen werden, und eine Ecke vom Grad 1 lässt sich gar nicht durchlaufen. Manche Graphen entgehen allen solchen Argumenten. Der Petersen-Graph, 1898 von Julius Petersen veröffentlicht, hat 10 Ecken vom Grad 3 und keinen Hamiltonkreis, doch das Löschen einer beliebigen Ecke lässt einen Graphen zurück, der einen hat; er ist der kleinste solche hypohamiltonsche Graph. Der Herschel-Graph, benannt nach Alexander Stewart Herschel, der 1862 über das Ikosianspiel schrieb, hat 11 Ecken und 18 Kanten und ist der Graph eines Polyeders mit neun viereckigen Flächen. Keinem Polyeder mit weniger Ecken fehlt ein Hamiltonkreis. 1884 vermutete Peter Guthrie Tait, dass jedes Polyeder mit drei Kanten an jeder Ecke einen hat; W. T. Tutte fand 1946 ein Gegenbeispiel mit 46 Ecken.
Bedingungen, die einen zusichern
Hat ein Graph viele Kanten, ist ein Hamiltonkreis sicher. Gabriel Dirac bewies 1952, dass ein Graph mit n ≥ 3 Ecken, in dem jede Ecke mindestens den Grad n/2 hat, einen besitzt, und Øystein Ore schwächte die Bedingung 1960 ab: Es genügt, dass je zwei nicht verbundene Ecken Grade mit Summe mindestens n haben. Beide Bedingungen gelten nur in einer Richtung. Ein schlichter Ring aus 100 Ecken hat überall den Grad 2, weit unter 50, und ist dennoch ein Hamiltonkreis. So sieht es allgemein aus: Es gibt hinreichende Bedingungen und es gibt Gründe für das Scheitern, und dazwischen liegt ein weites Gebiet von Graphen, über die nur eine Suche entscheiden kann.
Warum kein schneller Test bekannt ist
Die Frage, ob ein Graph einen Hamiltonkreis hat, ist NP-vollständig; sie war eines der 21 Probleme auf Richard Karps Liste von 1972. Ein Verfahren, das sie für jeden Graphen schnell löste, löste auch Tausende anderer Probleme schnell und entschiede die Frage P gegen NP. Der Gegensatz zu Eulerwegen, die jede Kante einmal benutzen, ist auffällig: Euler zeigte 1736, dass das Abzählen der Ecken ungeraden Grades jene Frage sofort entscheidet. Die besten exakten Verfahren für Hamiltonkreise brauchen weiterhin exponentielle Zeit. Dynamische Programmierung über alle Teilmengen der Ecken, 1962 von Richard Bellman sowie von Michael Held und Richard Karp gefunden, braucht etwa n² × 2ⁿ Schritte, und Andreas Björklunds randomisiertes Verfahren von 2010 etwa 1,657ⁿ. In der Praxis bewältigt Backtracking mit gutem Abschneiden Graphen mit einigen Dutzend Ecken, und das Problem des Handlungsreisenden, das den kürzesten Hamiltonkreis sucht, ist die gewichtete Fassung derselben Frage.
Gray-Codes und der Hyperwürfel
Schreiben Sie die Zahlen 0 bis 7 als 3-Bit-Codes und verbinden Sie zwei Codes, wenn sie sich in genau einem Bit unterscheiden: Das Ergebnis ist der Graph eines Würfels. Ein Hamiltonkreis darin, etwa 000, 001, 011, 010, 110, 111, 101, 100, listet alle acht Codes so auf, dass sich jeder vom vorigen in einem einzigen Bit unterscheidet. Eine solche Liste ist ein Gray-Code, benannt nach Frank Gray von den Bell Labs, der ihn in einem 1947 eingereichten Patent beschrieb. Jeder Hyperwürfel hat einen: Schreiben Sie die Codes mit einem Bit weniger, dann dieselbe Liste rückwärts, und setzen Sie vor die erste Hälfte eine 0 und vor die zweite eine 1. Drehgeber benutzen Gray-Codes, damit eine zwischen zwei Stellungen abgelesene Angabe nie um mehr als einen Schritt falsch ist. Der Würfel hat 6 Hamiltonkreise und der 4-Bit-Hyperwürfel 1.344.
Probieren Sie es aus
Öffnen Sie den Hamiltonweg-Explorer, um Hamiltons Rätsel selbst zu versuchen, mit gestrichelten Ringen, die zeigen, wohin es weitergeht, oder wechseln Sie zur Suche und sehen Sie dem Backtracking zu: Der Weg wächst, rote Striche markieren die Rückschritte, und die Balken zählen die Knoten je Weglänge. Schalten Sie die Sackgassen-Prüfung, die Zusammenhangs-Prüfung und die Warnsdorff-Reihenfolge ein und aus, vergleichen Sie, wie viele Knoten jede braucht, zählen Sie alle Kreise eines kleinen Graphen, oder zeichnen Sie einen eigenen Graphen und sehen Sie, welche der Schnelltests greifen.
Häufig gestellte Fragen
Ist ein Graph mit einem Eulerkreis auch hamiltonsch, oder umgekehrt?
Weder noch folgt aus dem anderen. Die Fliege, zwei Dreiecke mit einer gemeinsamen Ecke, hat einen Eulerkreis, weil jeder Grad gerade ist, aber keinen Hamiltonkreis, da die gemeinsame Ecke zweimal durchlaufen werden müsste. Der vollständige Graph K₄ hat Hamiltonkreise, doch alle vier Ecken haben den Grad 3, er hat also keinen Eulerkreis.
Kann ein Computer nicht einfach jede Reihenfolge probieren?
Nur bei kleinen Graphen. Es gibt n! Reihenfolgen von n Ecken, bei 20 etwa 2,4 × 10¹⁸. Backtracking schneidet viel besser ab, weil es nur Kanten folgt und einen Teilweg aufgibt, sobald es nicht weitergeht: Es findet alle 30 Kreise des 20-eckigen Dodekaeders in rund 1.400 Schritten. Doch bei manchen Graphen wächst die Zahl der Teilwege dennoch exponentiell, und es ist kein Verfahren bekannt, das dies für jeden Graphen vermeidet.
Ist das Hamiltonweg-Problem leichter als das Kreis-Problem?
Nein, beide sind NP-vollständig. Jedes lässt sich in das andere übersetzen: Fügt man eine neue Ecke hinzu, die mit jeder alten verbunden ist, so hat der alte Graph genau dann einen Hamiltonweg, wenn der neue einen Hamiltonkreis hat. Umgekehrt wird aus einem Kreis-Problem ein Weg-Problem, indem man eine Kopie einer Ecke mit denselben Nachbarn hinzufügt und je eine neue Endecke an die Ecke und an ihre Kopie hängt.
Warum muss ein Springerzug auf einem 5 × 5-Brett auf einer Eckfarbe beginnen?
Von den 25 Feldern haben 13 die Farbe der Ecken und 12 die andere, und ein Springer wechselt mit jedem Zug die Farbe. Ein Zug über 25 Felder wechselt die Farben ab, er beginnt und endet also auf der Farbe mit den meisten Feldern. Die App findet alle 1.728 offenen Züge des 5 × 5-Bretts, 864, wenn ein Zug und seine Umkehrung einmal zählen, und jeder beginnt und endet auf einem Feld in der Eckfarbe.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Hamiltonweg-Explorer öffnen