|
|
|
|
,
der alle Knoten von
durchläuft,
heißt HAMILTON-Kreis .
| Beispiel | |
|
In der Abbildung bilden die grün gezeichneten Linien einen HAMILTON-Kreis.
| |
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 
mindestens 3 Knoten, und gilt 
für jeden Knoten 
von 
dann enthält
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.
| |
3. Satz von Ore:Enthält ein schlichter Graph
mindestens 3 Knoten, und gilt
für je zwei nichtadjazente Knoten 
dann enthält
einen HAMILTON-Kreis.
4. Satz von Posa:
Es sei
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 
ist, ist kleiner als 
2. Ist 
ungerade, dann gelte zusätzlich: Die Anzahl derjenigen Knoten,
deren Grad höchstens 
ist, ist höchstens 
|
|
