Hamiltonkreise
Wir stellen nun die zur Existenz von Eulerzügen analoge Frage, wann und wie man geschlossene Kantenzüge findet, die jede Ecke des Graphen genau einmal besuchen:
Definition (Hamiltonkreis)
Sei G ein Graph der Ordnung n. Ein Kreis mit n Ecken in G heißt ein Hamiltonkreis. G heißt Hamiltonsch, falls ein Hamiltonkreis in G existiert.
In diesem Graphen ist 1, 2, 3, 5, 9, 6, 8, 7, 4, 1 ein Hamiltonkreis.
War das Problem der Existenz von Eulerzügen überraschend einfach, so ist nun das Problem der Existenz von Hamiltonkreisen überraschend schwierig. Es scheint keinen schnellen Algorithmus zu geben, der einen gegebenen Graphen daraufhin überprüft, ob er Hamiltonsch ist oder nicht. Ebenso scheint es kein einfaches notwendiges und hinreichendes Kriterium dafür zu geben, wann ein Graph Hamiltonsch ist. Hinreichend ist die folgende Reichhaltigkeitsbedingung:
Satz (Satz von Gabriel Dirac)
Sei G = (E, K) ein Graph der Ordnung n* ≥ 3, und es gelte d(a) ≥ n*/2 für alle a ∈ E. Dann ist G Hamiltonsch.
Beweis
Sei W = a0, …, an ein maximaler Weg in G, d. h. ein Weg in G, den wir nach links und nach rechts nicht mehr fortsetzen können. Dann werden alle Nachbarecken von a0 und von an auf W besucht, da wir sonst den Weg verlängern könnten. Insbesondere ist n ≥ d(a0) ≥ n*/2 ≥ 3/2. Andererseits ist n* ≥ n + 1, da W ein Weg ist. Weiter gilt:
(+) Es gibt ein i < n, sodass C = a0, …, ai, an, an − 1, …, ai + 1, a0 ein Kreis ist.
(Im Falle i = n − 1 ist C = a0, …, an, a0 ein Kreis.)
Beweis von (+)
Gesucht ist ein i < n, sodass ai mit an und ai + 1 mit a0 in G verbunden ist. Wir setzen hierzu
A = { i < n | aian ∈ K }, B = { i < n | ai + 1a0 ∈ K }.
Dann gilt |A|,|B| ≥ n*/2 > n/2, da alle Nachbarecken von an und a0 besucht werden. Wegen A ∪ B ⊆ { 0, …, n − 1 } gilt dann aber
|A ∩ B| = |A| + |B| − |A ∪ B| > n/2 + n/2 − n = 0,
also ist A ∩ B nichtleer.
Ist n + 1 = n*, so haben wir mit C einen Hamiltonkreis gefunden.
Andernfalls gilt:
(++) Ist a eine auf C nicht besuchte Ecke, so gibt es ein j ≤ n mit aaj ∈ K.
Beweis von (++)
Andernfalls gilt { a0, …, an } ∩ N(a) = ∅, und wegen n ≥ n*/2 gilt dann
n* = |E| ≥ (n + 1) + d(a) ≥ (n*/2 + 1) + n*/2 = n* + 1,
Widerspruch.
Aus (++) erhalten wir durch Aufschneiden des Kreises C an der Ecke aj und Anfügen von a einen Weg in G, der länger ist als W. Diesen Weg können wir zu einem maximalen Weg fortsetzen, und dann liefert (+) wieder einen entsprechend langen Kreis. Nach endlicher Iteration dieses Verfahrens haben wir dann einen Hamiltonkreis von G gefunden.
Der Beweis liefert einen effizienten „Algorithmus von Dirac“, der einen Hamiltonkreis in Graphen findet, die der Reichhaltigkeitsbedingung des Satzes genügen. Der Leser ist aufgefordert, diesen Algorithmus explizit zu notieren.
Der Satz von Gabriel Dirac (1952) kann noch zum Satz von Øystein Ore (1960) verbessert werden: Ein Graph G = (E, K) der Ordnung n* ≥ 3 ist Hamiltonsch, falls d(a) + d(b) ≥ n* für alle a, b ∈ E mit a ≠ b und a b ∉ K gilt. Noch stärker ist der Satz von Bondy-Chvátal (1972): Sei G = (E, K) ein Graph der Ordnung n* ≥ 3, und seien a, b ∈ E mit a ≠ b, a b ∉ K und d(a) + d(b) ≥ n*. Dann ist G genau dann Hamiltonsch, wenn (E, K ∪ { a b }) Hamiltonsch ist.