Hamilton-Kreise

1. Hamilton-Kreis:
Ein Elementarkreis in einem Graphen G, der alle Knoten von G durchläuft, heißt HAMILTON-Kreis.
Beispiel

In der Abbildung bilden die grün gezeichneten Linien einen HAMILTON-Kreis.

Bild

Die Idee für ein Spiel, in dem man in dem abgebildeten Graphen eines Pentagondodekaeders HAMILTON-Kreise auffinden soll, geht auf Sir W. HAMILTON zurück.

Hinweis: Die Frage nach der Charakterisierung der Graphen mit HAMILTON-Kreisen führt auf eins der klassischen NP-vollständigen Probleme. Deshalb kann hier kein effizienter Algorithmus zur Ermittlung von HAMILTON-Kreisen angegeben werden.

2. Satz von Dirac:
Enthält ein schlichter Graph G=(V,E) mindestens 3 Knoten, und gilt für jeden Knoten v von dann enthält G einen HAMILTON-Kreis. Diese hinreichende Bedingung für die Existenz eines HAMILTON-Kreises ist aber nicht notwendig. Auch die folgenden Sätze mit verallgemeinerten Voraussetzungen liefern nur hinreichende Bedingungen für die Existenz von HAMILTON-Kreisen.
Beispiel

In der Abbildung ist ein Graph gezeigt, der einen HAMILTON-Kreis besitzt, ohne die Voraussetzungen des folgenden Satzes von ORE zu erfüllen.

Bild
3. Satz von Ore:
Enthält ein schlichter Graph G=(V,E) mindestens 3 Knoten, und gilt für je zwei nichtadjazente Knoten dann enthält G einen HAMILTON-Kreis.
4. Satz von Posa:
Es sei G=(V,E) ein schlichter Graph mit mindestens 3 Knoten. Er besitzt einen HAMILTON-Kreis, wenn die folgenden Bedingungen erfüllt sind:
  1. Für gelte: Die Anzahl derjenigen Knoten, deren Grad höchstens k ist, ist kleiner als
  2. Ist |V| ungerade, dann gelte zusätzlich: Die Anzahl derjenigen Knoten, deren Grad höchstens (|V|-1)/2 ist, ist höchstens