Hamiltonwege und Hamiltonkreise

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Jeder Knoten, genau einmal

Ein Hamiltonweg ist ein Weg, der jeden Knoten eines Graphen genau einmal besucht. Ein Hamiltonkreis tut dasselbe und kehrt dann über eine weitere Kante zu seinem Startknoten zurück. Ein Graph mit einem Hamiltonkreis heißt hamiltonsch, und ein Graph mit einem Hamiltonweg wird manchmal durchlaufbar (traceable) genannt. Jeder hamiltonsche Graph ist durchlaufbar, denn das Löschen einer Kante eines Hamiltonkreises hinterlässt einen Hamiltonweg, aber die Umkehrung gilt nicht, wie die Beispiele unten zeigen.

Die Frage klingt wie eine nahe Verwandte derjenigen, die Euler 1736 beantwortete, und der Leitfaden zu Eulerwegen erzählt diese Geschichte. Ein Eulerweg benutzt jede Kante einmal; ein Hamiltonweg besucht jeden Knoten einmal. Der Unterschied in der Schwierigkeit ist enorm. Eulers Frage wird durch das Zählen ungerader Grade entschieden, was lineare Zeit braucht. Für Hamiltons Frage ist kein vergleichbarer Test bekannt, und man erwartet auch nicht, dass es einen gibt.

Im hausförmigen Graphen oben hat Knoten A den Grad 2, B und C haben den Grad 4, und D und E haben den Grad 3. Genau zwei Grade sind ungerade, also verläuft ein Eulerweg von D nach E, und die Grade allein beweisen das. Der Hamiltonkreis A, B, D, E, C existiert ebenfalls, aber der einzige allgemeine Weg, das zu wissen, ist, ihn zu finden.

2. Vom Icosian-Spiel zum Petersen-Graphen

Der Name stammt von William Rowan Hamilton, der 1857 das Icosian-Spiel vorstellte: ein als Dodekaeder gezeichnetes Spielbrett (der Körper mit 12 Fünfecksflächen und 20 Eckpunkten), auf dem der Spieler entlang der Kanten alle 20 Eckpunkte besuchen und zum Start zurückkehren musste. Hamilton verkaufte die Rechte für 25 Pfund an die Londoner Firma John Jaques and Son, die das Spiel 1859 in den Handel brachte. Die Frage selbst ist älter: Thomas Kirkman hatte in einem 1856 veröffentlichten Aufsatz gefragt, welche Polyeder einen Rundweg durch alle ihre Eckpunkte besitzen.

Das Dodekaeder hat genau 30 Hamiltonkreise, wobei jeder Kreis unabhängig von Richtung und Starteckpunkt nur einmal gezählt wird. Der Petersen-Graph, den Julius Petersen 1898 beschrieb, ist das klassische Gegenstück. Er hat 10 Knoten und 15 Kanten, jeder Knoten hat den Grad 3, er ist zusammenhängend und hat keinen Schnittknoten, und dennoch hat er keinen Hamiltonkreis. Einen Hamiltonweg hat er sehr wohl. Noch seltsamer: Löscht man einen beliebigen seiner Knoten, bleibt ein Graph übrig, der einen Hamiltonkreis hat, eine Eigenschaft, die hypohamiltonsch heißt. Jeder einfache Test, der nahelegt, dass ein Graph hamiltonsch sein sollte, wird vom Petersen-Graphen erfüllt, weshalb er in der gesamten Graphentheorie als Gegenbeispiel auftaucht.

3. Beweisen, dass kein Kreis existiert

Das durchgehende Beispiel ist ein Museum mit 9 Räumen, A bis I, und 14 Türen dazwischen. Ein Besucher möchte jeden Raum genau einmal sehen und am liebsten dort enden, wo er begonnen hat:

doors = {AB, AC, BC, FG, FH, GH, AD, BD, DF, DI, CE, EH, EI, EG}      9 Räume, 14 Türen

deg:   A 3   B 3   C 3   D 4   E 4   F 3   G 3   H 3   I 2

Ein Hamiltonweg existiert: A, B, C, E, G, H, F, D, I besucht jeden Raum einmal. Ein Hamiltonkreis existiert nicht, und den Grund sieht man auf einem Bild. Schließen Sie die Räume D und E, und der Rest des Museums zerfällt in drei getrennte Teile: {A, B, C}, {F, G, H} und der einzelne Raum I.

Das Argument funktioniert für jeden Graphen. Löschen Sie k Knoten aus einem Kreis, und er zerfällt in höchstens k Bögen; hat ein Graph also einen Hamiltonkreis, so hinterlässt das Löschen beliebiger k seiner Knoten höchstens k zusammenhängende Teile. Ein Weg zerfällt in höchstens k + 1 Teile, also hinterlässt ein durchlaufbarer Graph höchstens k + 1. Das Museum hat eine Menge von 2 Räumen, deren Entfernung 3 Teile hinterlässt, was für einen Kreis zu viele sind, für einen Weg aber erlaubt. Chvátal untersuchte dieses Maß 1973 unter dem Namen Zähigkeit.

from itertools import combinations

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def pieces(adj, removed):
    """Anzahl der zusammenhängenden Teile, die nach dem Löschen der Knoten in removed übrig bleiben."""
    seen, count = set(removed), 0
    for s in adj:
        if s in seen:
            continue
        count += 1
        stack = [s]
        seen.add(s)
        while stack:
            for w in adj[stack.pop()] - seen:
                seen.add(w)
                stack.append(w)
    return count

def cycle_obstruction(adj):
    """Eine Menge S, deren Entfernung mehr als |S| Teile hinterlässt: Beweis, dass kein Hamiltonkreis existiert."""
    for k in range(1, len(adj)):
        for S in combinations(sorted(adj), k):
            if pieces(adj, S) > k:
                return list(S), pieces(adj, S)
    return None

museum = graph(['AB', 'AC', 'BC', 'FG', 'FH', 'GH', 'AD', 'BD', 'DF', 'DI', 'CE', 'EH', 'EI', 'EG'])
print(cycle_obstruction(museum))
# (['D', 'E'], 3)
outer = [(i, (i + 1) % 5) for i in range(5)]
spokes = [(i, i + 5) for i in range(5)]
star = [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
petersen = graph(outer + spokes + star)
print(cycle_obstruction(petersen))            # kein Zertifikat, und trotzdem auch kein Hamiltonkreis
# None

Die Funktion probiert jede Knotenmenge aus, die kleinsten zuerst, und gibt die erste zurück, die zu viele Teile hinterlässt. Im Museum findet sie {D, E}, die einzige solche Menge. Im Petersen-Graphen findet sie nichts, obwohl der Petersen-Graph keinen Hamiltonkreis hat. Das ist die Grenze jeder Bedingung dieser Art: Sie kann beweisen, dass ein Kreis unmöglich ist, aber ihr Schweigen beweist nichts.

Mehrere Spezialfälle derselben Idee sollte man beim Namen kennen:

• Schnittknoten. Ein Graph mit einem Schnittknoten, also einem Knoten, dessen Entfernung ihn unzusammenhängend macht, hat keinen Hamiltonkreis. Das ist der Fall k = 1.
• Knoten vom Grad 1 oder 2. Ein Knoten vom Grad 1 kann nur ein Ende eines Hamiltonwegs sein, nie Teil eines Kreises. Ein Knoten vom Grad 2 zwingt beide seiner Kanten in jeden Hamiltonkreis: Im Museum müssten beide Türen von Raum I benutzt werden.
• Unausgeglichene bipartite Graphen. Ein Kreis in einem bipartiten Graphen wechselt zwischen den beiden Seiten hin und her, also braucht ein Hamiltonkreis gleich große Seiten und ein Hamiltonweg Größen, die sich um höchstens eins unterscheiden. Der vollständige bipartite Graph K2,3 hat aus diesem Grund einen Hamiltonweg, aber keinen Hamiltonkreis.

4. Gradbedingungen, die einen Kreis garantieren

Die umgekehrte Richtung fragt, was die Existenz eines Hamiltonkreises erzwingt. Die berühmtesten Antworten verwenden Grade, und der Leitfaden zum Knotengrad behandelt die erste davon ausführlich.

• Satz von Dirac (1952). Ein einfacher Graph mit n ≥ 3 Knoten, in dem jeder Knoten mindestens Grad n / 2 hat, besitzt einen Hamiltonkreis.
• Satz von Ore (1960). Es genügt, dass deg(u) + deg(v) ≥ n für jedes Paar von Knoten u und v gilt, die nicht benachbart sind. Diracs Bedingung ist der Spezialfall, in dem alle Grade mindestens n / 2 betragen.
• Der Abschluss nach Bondy und Chvátal (1976). Verbinden Sie wiederholt je zwei nicht benachbarte Knoten, deren Grade sich zu mindestens n addieren. Der ursprüngliche Graph ist genau dann hamiltonsch, wenn der Endgraph, sein Abschluss, hamiltonsch ist; ist der Abschluss vollständig, lautet die Antwort ja.
• Der Satz von Chvátal–Erdős (1972). Wenn die Zusammenhangszahl eines Graphen (die kleinste Anzahl von Knoten, deren Entfernung ihn unzusammenhängend macht) mindestens so groß ist wie seine Unabhängigkeitszahl (die Größe seiner größten unabhängigen Menge), dann ist der Graph hamiltonsch. Der Leitfaden zu Cliquen und unabhängigen Mengen erklärt die zweite Größe.

All dies sind hinreichende, keine notwendigen Bedingungen. Ein Kreis auf 100 Knoten ist hamiltonsch, und doch hat jeder Knoten den Grad 2, weit unter 50. Das Museum zeigt die andere Seite: Sein größter Grad ist 4, also kleiner als 9 / 2, daher greift keine der Gradbedingungen, was damit vereinbar ist, dass es keinen Kreis hat. Wird eine weitere Tür geöffnet, zwischen G und I, so wird das Museum hamiltonsch, und die Gradbedingungen sagen weiterhin nichts. Sie beschreiben Graphen, die dicht genug sind, um aus einfachen Gründen hamiltonsch zu sein; dünne Graphen brauchen andere Werkzeuge.

5. Planare Graphen: Taits Vermutung und Tuttes Antwort

Hamiltonkreise schienen einst ein Weg zum Vierfarbensatz zu sein. 1884 vermutete Peter Guthrie Tait, dass jeder 3-fach zusammenhängende, 3-reguläre planare Graph einen Hamiltonkreis hat, was einen einfachen Beweis dafür geliefert hätte, dass vier Farben für Landkarten genügen, an deren Eckpunkten jeweils drei Gebiete zusammentreffen. Die Vermutung war falsch. William Tutte veröffentlichte 1946 ein Gegenbeispiel mit 46 Knoten, und Holton und McKay zeigten 1988, dass die kleinsten Gegenbeispiele 38 Knoten haben.

Ein Grad mehr an Zusammenhang genügt. Whitney bewies 1931, dass jede 4-fach zusammenhängende planare Triangulierung hamiltonsch ist, und Tutte erweiterte dies 1956 auf jeden 4-fach zusammenhängenden planaren Graphen. Diese Ergebnisse gehören zu den wenigen, die Hamiltonkreise in dünnen Graphen garantieren, in denen die Gradbedingungen aus Abschnitt 4 nicht greifen können.

6. Einen Hamiltonweg durch Suche finden

Die direkte Methode verlängert einen Weg Knoten für Knoten. In jedem Schritt probiert sie der Reihe nach die unbesuchten Nachbarn des letzten Knotens; lässt sich der Weg nicht verlängern und ist noch ein Knoten unbesucht, geht sie zurück und probiert die nächste Möglichkeit. Deckt der Weg irgendwann jeden Knoten ab, ist er ein Hamiltonweg, und sind seine beiden Enden benachbart, schließt er sich auch zu einem Kreis.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def hamiltonian(adj, cycle=False):
    """Backtracking: einen Weg Knoten für Knoten verlängern und in einer Sackgasse rückgängig machen."""
    n = len(adj)
    def extend(path, seen):
        if len(path) == n:
            return path if not cycle or path[0] in adj[path[-1]] else None
        for w in sorted(adj[path[-1]] - seen):
            found = extend(path + [w], seen | {w})
            if found:
                return found
        return None                           # jede Fortsetzung ist gescheitert: zurückgehen
    starts = [min(adj)] if cycle else sorted(adj)   # ein Kreis darf überall beginnen
    for s in starts:
        found = extend([s], {s})
        if found:
            return found
    return None

museum = graph(['AB', 'AC', 'BC', 'FG', 'FH', 'GH', 'AD', 'BD', 'DF', 'DI', 'CE', 'EH', 'EI', 'EG'])
print(hamiltonian(museum))                    # jeden Raum einmal besuchen
# ['A', 'B', 'C', 'E', 'G', 'H', 'F', 'D', 'I']
print(hamiltonian(museum, cycle=True))        # ... und zum Start zurückkehren
# None
museum['G'].add('I'); museum['I'].add('G')    # eine weitere Tür öffnen
print(hamiltonian(museum, cycle=True))
# ['A', 'B', 'C', 'E', 'H', 'F', 'G', 'I', 'D']

Die erste Zeile ist die Tour aus Abschnitt 3. Die zweite bestätigt, dass keine Tour zu ihrem Start zurückkehren kann, wie das Hindernis bewiesen hat. Die dritte zeigt, dass das Öffnen einer weiteren Tür, zwischen G und I, einen Hamiltonkreis möglich macht. Bei der Suche nach einem Kreis startet die Funktion von einem einzigen Knoten, weil ein Kreis durch jeden Knoten geht und von jedem aus gelesen werden kann. Die Funktion wurde an 1.136 Zufallsgraphen mit bis zu 8 Knoten gegen Brute Force geprüft.

Reines Backtracking ist exponentiell: Im schlimmsten Fall durchsucht es einen großen Teil der n! Anordnungen der Knoten, und 20! beträgt etwa 2,4 × 1018. Praktische Löser ergänzen ein Beschneiden des Suchbaums (Pruning). Sie geben einen Zweig auf, sobald die unbesuchten Knoten nicht mehr zusammenhängen, ein Knoten zu wenige unbesuchte Nachbarn übrig hat, um noch durchlaufen zu werden, oder bei einem Knoten vom Grad 2 die erzwungenen Kanten blockiert sind. Außerdem probieren sie den am stärksten eingeschränkten Nachbarn zuerst, dieselbe Idee wie die Warnsdorff-Regel für Springertouren in Abschnitt 9.

7. Dynamische Programmierung über Teilmengen

Einen besseren schlimmsten Fall liefert ein dynamisches Programm, das 1962 unabhängig von Bellman sowie von Held und Karp gefunden wurde, ursprünglich für das Problem des Handlungsreisenden. Legen Sie einen Startknoten fest. Für jede Teilmenge S der Knoten, die ihn enthält, und jeden Knoten v in S halten Sie fest, wie viele Wege am festen Knoten beginnen, genau die Knoten von S besuchen und bei v enden. Jeder Eintrag wird aus kleineren Teilmengen aufgebaut, und die volle Menge liefert die Hamiltonwege, die sich zu Kreisen schließen, wenn ihr letzter Knoten zum Start benachbart ist.

from itertools import combinations

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def count_hamiltonian_cycles(adj):
    """Dynamische Programmierung über Teilmengen (Bellman; Held und Karp), Laufzeit O(2^n * n^2)."""
    V = sorted(adj)
    n, index = len(V), {v: i for i, v in enumerate(V)}
    ways = [[0] * n for _ in range(1 << n)]   # ways[S][v]: Wege von V[0] durch genau S, die bei v enden
    ways[1][0] = 1
    for S in range(1 << n):
        for v in range(n):
            if ways[S][v]:
                for w in adj[V[v]]:
                    j = index[w]
                    if not S >> j & 1:
                        ways[S | 1 << j][j] += ways[S][v]
    full = (1 << n) - 1
    closing = sum(ways[full][index[w]] for w in adj[V[0]])
    return closing // 2                       # jeder Kreis wird in jeder Richtung einmal gefunden

museum = graph(['AB', 'AC', 'BC', 'FG', 'FH', 'GH', 'AD', 'BD', 'DF', 'DI', 'CE', 'EH', 'EI', 'EG'])
print(count_hamiltonian_cycles(museum))
# 0
museum['G'].add('I'); museum['I'].add('G')    # die zusätzliche Tür von vorhin
print(count_hamiltonian_cycles(museum))
# 4
print(count_hamiltonian_cycles(graph(combinations(range(6), 2))))   # K6: (6 - 1)! / 2
# 60

Das Museum hat keinen Hamiltonkreis, das Museum mit der zusätzlichen Tür hat genau 4, und der vollständige Graph K6 hat (6 − 1)! / 2 = 60, passend zur Formel für vollständige Graphen. Das Programm prüft 2n Teilmengen mit je n Endknoten und probiert für jeden Eintrag bis zu n Nachbarn aus, läuft also in O(2n n2) Zeit. Für 20 Knoten sind das 20.971.520 Tabelleneinträge, viel, aber durchaus machbar, während das Auflisten der Hamiltonkreise von K20 einzeln 60.822.550.204.416.000 Kreise bedeuten würde. Der schnellste bekannte Algorithmus für ungerichtete Graphen, ein randomisiertes Verfahren von Björklund, 2014 veröffentlicht, läuft in O*(1,657n) Zeit, wobei der Stern polynomielle Faktoren verbirgt.

8. Wie schwer ist das Problem?

Zu entscheiden, ob ein Graph einen Hamiltonkreis hat, ist NP-vollständig, für ungerichtete wie für gerichtete Graphen; beide Varianten standen auf Karps Liste von 21 NP-vollständigen Problemen aus dem Jahr 1972. Auch das Hamiltonwegproblem ist NP-vollständig. Die Schwere übersteht starke Einschränkungen: Garey, Johnson und Tarjan bewiesen 1976, dass das Problem für planare Graphen, die 3-fach zusammenhängend und 3-regulär sind, NP-vollständig bleibt, also genau für die Klasse aus Taits Vermutung, und Itai, Papadimitriou und Szwarcfiter bewiesen 1982, dass auch Hamiltonwege in Gittergraphen NP-vollständig sind, obwohl vollständige rechteckige Gitter einfach sind.

Der Gegensatz zu Eulers Problem ist das klarste Beispiel der Graphentheorie für zwei Fragen, die gleich aussehen und auf entgegengesetzten Seiten der Trennlinie zwischen P und NP liegen. Das Hamiltonkreisproblem ist zudem der Kern des Problems des Handlungsreisenden: Ein Graph hat genau dann einen Hamiltonkreis, wenn, nachdem man seinen Kanten die Länge 1 und jeder fehlenden Kante die Länge 2 gegeben hat, die kürzeste Tour durch alle Knoten die Länge n hat. Jeder schnelle Algorithmus für das Problem des Handlungsreisenden würde also auch entscheiden, ob ein Graph hamiltonsch ist.

9. Familien, die immer einen haben

Manche Graphenfamilien sind aus strukturellen Gründen hamiltonsch, und mehrere davon sind für sich genommen berühmt.

• Vollständige Graphen. Jede Anordnung der Knoten von Kn ist ein Hamiltonweg, und für n ≥ 3 gibt es (n − 1)! / 2 Hamiltonkreise.
• Turniere. Ein Turnier ist ein gerichteter Graph mit genau einem Pfeil zwischen je zwei Knoten, wie die Ergebnisse eines Rundenturniers. Rédei bewies 1934, dass jedes Turnier einen Hamiltonweg hat, sodass sich die Spieler immer so auflisten lassen, dass jeder den nächsten geschlagen hat, und Camion bewies 1959, dass ein Turnier einen Hamiltonkreis hat, sobald jeder Spieler jeden anderen über eine Kette von Siegen erreichen kann.
• Hyperwürfel und Gray-Codes. Der Würfelgraph, dessen Knoten die Bitfolgen der Länge n sind, verbunden, wenn sie sich in einem Bit unterscheiden, ist hamiltonsch für n ≥ 2. Ein Hamiltonkreis darin ist ein Gray-Code: eine Liste aller 2n Bitfolgen, in der sich aufeinanderfolgende Folgen in einem einzigen Bit unterscheiden. Frank Gray patentierte den reflektierten Binärcode 1953 für die Signalübertragung.
• Springertouren. Ein Springer, der jedes Feld eines Schachbretts einmal besucht, beschreibt einen Hamiltonweg im Graphen der Springerzüge. Euler untersuchte solche Touren 1759, Warnsdorff schlug 1823 die Regel vor, stets auf das Feld mit den wenigsten Weiterzügen zu ziehen, und Schwenk bestimmte 1991 genau, welche rechteckigen Bretter eine geschlossene Tour haben.

10. Zufallsgraphen: Wann entstehen Hamiltonkreise?

Die Hindernisse aus Abschnitt 3 sind meist lokal: ein Knoten mit nur einer Kante oder einige wenige Knoten, die ein Stück des Graphen abtrennen. In Zufallsgraphen erweist sich das lokale Hindernis als das einzige, das zählt. Pósa bewies 1976, dass ein Zufallsgraph auf n Knoten mit etwa C n log n Kanten, für eine geeignete Konstante C, fast sicher hamiltonsch ist. Komlós und Szemerédi fanden 1983 die genaue Schwelle: Sie liegt dort, wo die erwartete Anzahl von Knoten mit Grad kleiner als 2 auf null fällt.

Die schärfste Form ist eine Aussage über einen Graphen, der Kante für Kante zufällig wächst. Bollobás 1984 und unabhängig davon Ajtai, Komlós und Szemerédi 1985 bewiesen, dass der Graph mit gegen 1 strebender Wahrscheinlichkeit genau in dem Moment hamiltonsch wird, in dem sein letzter Knoten mit Grad kleiner als 2 verschwindet. In einem Zufallsgraphen gilt: Sobald nichts offensichtlich einen Hamiltonkreis blockiert, existiert einer.

11. Wo Hamiltonwege eingesetzt werden

• Routen und Rundreisen. Jede Zustellrunde, Inspektionsroute oder Bohrreihenfolge, die jeden Ort einmal besuchen muss, ist ein Hamiltonkreisproblem mit Entfernungen, und das ist das Problem des Handlungsreisenden.
• Genomassemblierung. Frühe Assembler modellierten DNA-Reads als Knoten, die durch Überlappungen verbunden sind, und suchten einen Hamiltonweg durch sie. Idury und Waterman schlugen 1995 vor, die Assemblierung als Eulerwegproblem in einem De-Bruijn-Graphen neu zu fassen, und Pevzner, Tang und Waterman entwickelten den Ansatz 2001 weiter, weshalb moderne Assembler Eulers leichtes Problem statt Hamiltons schweres lösen.
• Drehgeber und Gray-Codes. Dreh- und Linear-Positionsgeber verwenden Gray-Codes, damit sich beim Übergang von einer Position zur nächsten nur ein einziges Bit ändert, was große Lesefehler während der Übergänge vermeidet.
• Testen und Ablaufplanung. Jeden Zustand eines Systems einmal zu besuchen oder Aufträge so anzuordnen, dass jeder auf einen kompatiblen Vorgänger folgt, sind Hamiltonwegprobleme auf dem Graphen der erlaubten Übergänge.
• Rätsel. Das Icosian-Spiel, Springertouren und viele Rätsel, bei denen Wege gezeichnet werden, fragen in Verkleidung nach Hamiltonwegen oder Hamiltonkreisen.

12. Häufige Fehler

13. Glossar

15. Quellen

Die Definitionen, Sätze und Zuschreibungen oben stammen aus diesen Quellen, in chronologischer Reihenfolge.

1. Euler, L. (1759). "Solution d'une question curieuse qui ne paroît soumise à aucune analyse." Mémoires de l'Académie Royale des Sciences et Belles Lettres de Berlin 15, 310 bis 337. Datiert 1759, gedruckt 1766. Springertouren.
2. Warnsdorff, H. C. von (1823). Des Rösselsprunges einfachste und allgemeinste Lösung. Schmalkalden: Varnhagen.
3. Kirkman, T. P. (1856). "On the Representation of Polyedra." Philosophical Transactions of the Royal Society of London 146, 413 bis 418.
4. Tait, P. G. (1884). "Listing's Topologie." Philosophical Magazine, 5. Serie, 17, 30 bis 46.
5. Petersen, J. (1898). "Sur le théorème de Tait." L'Intermédiaire des Mathématiciens 5, 225 bis 227.
6. Whitney, H. (1931). "A Theorem on Graphs." Annals of Mathematics 32(2), 378 bis 390.
7. Rédei, L. (1934). "Ein kombinatorischer Satz." Acta Litterarum ac Scientiarum Szeged 7, 39 bis 43.
8. Tutte, W. T. (1946). "On Hamiltonian Circuits." Journal of the London Mathematical Society 21(2), 98 bis 101.
9. Dirac, G. A. (1952). "Some Theorems on Abstract Graphs." Proceedings of the London Mathematical Society s3-2, 69 bis 81.
10. Gray, F. (1953). "Pulse Code Communication." US-Patent 2,632,058.
11. Tutte, W. T. (1956). "A Theorem on Planar Graphs." Transactions of the American Mathematical Society 82, 99 bis 116.
12. Camion, P. (1959). "Chemins et circuits hamiltoniens des graphes complets." Comptes Rendus de l'Académie des Sciences 249, 2151 bis 2152.
13. Ore, O. (1960). "Note on Hamilton Circuits." The American Mathematical Monthly 67(1), 55.
14. Bellman, R. (1962). "Dynamic Programming Treatment of the Travelling Salesman Problem." Journal of the ACM 9(1), 61 bis 63.
15. Held, M. und Karp, R. M. (1962). "A Dynamic Programming Approach to Sequencing Problems." Journal of the Society for Industrial and Applied Mathematics 10(1), 196 bis 210.
16. Chvátal, V. und Erdős, P. (1972). "A Note on Hamiltonian Circuits." Discrete Mathematics 2(2), 111 bis 113.
17. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, herausgegeben von R. E. Miller und J. W. Thatcher, 85 bis 103. New York: Plenum.
18. Chvátal, V. (1973). "Tough Graphs and Hamiltonian Circuits." Discrete Mathematics 5(3), 215 bis 228.
19. Bondy, J. A. und Chvátal, V. (1976). "A Method in Graph Theory." Discrete Mathematics 15(2), 111 bis 135.
20. Garey, M. R., Johnson, D. S. und Tarjan, R. E. (1976). "The Planar Hamiltonian Circuit Problem is NP-Complete." SIAM Journal on Computing 5(4), 704 bis 714.
21. Pósa, L. (1976). "Hamiltonian Circuits in Random Graphs." Discrete Mathematics 14(4), 359 bis 364.
22. Itai, A., Papadimitriou, C. H. und Szwarcfiter, J. L. (1982). "Hamilton Paths in Grid Graphs." SIAM Journal on Computing 11(4), 676 bis 686.
23. Komlós, J. und Szemerédi, E. (1983). "Limit Distribution for the Existence of Hamiltonian Cycles in a Random Graph." Discrete Mathematics 43(1), 55 bis 63.
24. Bollobás, B. (1984). "The Evolution of Sparse Graphs." In Graph Theory and Combinatorics, herausgegeben von B. Bollobás, 35 bis 57. London: Academic Press.
25. Ajtai, M., Komlós, J. und Szemerédi, E. (1985). "First Occurrence of Hamilton Cycles in Random Graphs." Annals of Discrete Mathematics 27, 173 bis 178.
26. Holton, D. A. und McKay, B. D. (1988). "The Smallest Non-Hamiltonian 3-Connected Cubic Planar Graphs Have 38 Vertices." Journal of Combinatorial Theory, Series B 45(3), 305 bis 319.
27. Schwenk, A. J. (1991). "Which Rectangular Chessboards Have a Knight's Tour?" Mathematics Magazine 64(5), 325 bis 332.
28. Idury, R. M. und Waterman, M. S. (1995). "A New Algorithm for DNA Sequence Assembly." Journal of Computational Biology 2(2), 291 bis 306.
29. Pevzner, P. A., Tang, H. und Waterman, M. S. (2001). "An Eulerian Path Approach to DNA Fragment Assembly." Proceedings of the National Academy of Sciences 98(17), 9748 bis 9753.
30. Björklund, A. (2014). "Determinant Sums for Undirected Hamiltonicity." SIAM Journal on Computing 43(1), 280 bis 299.
31. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer.