Hamilton-Kreise
Bislang haben wir beim Durchlaufen eines Graphen nur die Kanten betrachtet. Ein Durchlauf-Problem lässt sich auch für die Ecken formulieren:
Definition (Hamilton-Kreis)
Sei G = (E, K) ein Graph. Ein Kreis in G heißt ein Hamilton-Kreis in G, wenn er alle Ecken von G besucht. Der Graph G heißt Hamiltonsch, falls ein Hamilton-Kreis in G existiert.
Ein Kreis C = a1, …, an, a1 in G ist genau dann ein Hamilton-Kreis, wenn er |E| Ecken besitzt, d. h. wenn n = |E|. Ebenfalls äquivalent ist, dass C jede Ecke von E mit Ausnahme der Startecke a1 genau einmal besucht; die Startecke wird genau zweimal besucht.
Ein Hamilton-Kreis wird in der Regel viele Kanten von G unbesucht lassen. Für jede Ecke a besucht ein Hamilton-Kreis genau zwei Kanten mit a als Ecke. Damit bleiben d(a) − 2 Kanten mit a als Ecke unbesucht.
Beispiele
Die Graphen der Platonischen Körper sind Hamiltonsch. Der Dodekaeder-Graph besitzt zum Beispiel den folgenden rot markierten Hamilton-Kreis:
Notwendige Bedingungen für „Hamiltonsch“ sind nur spärlich vorhanden: G muss zusammenhängend sein und alle Ecken müssen mindestens den Grad 2 besitzen. Spezielle hinreichende Bedingungen sind gefunden worden. So gilt etwa folgender Satz, den wir in den Übungen diskutieren:
Satz (Satz von Dirac)
Sei G = (E, K) ein Graph mit mindestens drei Ecken. Es gelte
(+) d(a) ≥ |E|/2 für alle a ∈ E.
Dann ist G Hamiltonsch.
Die geforderte Reichhaltigkeitsbedingung (+) ist sehr stark, und sie wird in der Regel von Hamiltonschen Graphen nicht erfüllt. Als triviales Beispiel betrachte der Leser einen Kreis mit 100 Ecken. Wie jeder Kreis ist dieser Graph Hamiltonsch. Es gilt aber d(a) = 2 < 50 für alle Ecken a. Auch der Dodekaeder-Graph hat mit 20 Ecken und der konstanten Gradfolge 3 relativ kleine Grade.
Im Gegensatz zu Euler-Zügen scheint es kein einfaches allgemeines Kriterium und auch keinen effizienten Algorithmus zu geben, mit dem wir entscheiden könnten, ob ein Graph Hamiltonsch ist oder nicht. Hierzu diskutieren wir allgemein: