Hamiltonkreis
Hamiltonkreis Definition
Der Hamiltonkreis ist in der Graphentheorie ein Kreis / Zyklus, der bei einem Knoten beginnend und endend alle Knoten eines Graphen enthält bzw. genau einmal durchläuft.
In einem Eisenbahnnetz (Graph) aus Städten (Knoten) und Bahnstrecken (Kanten) ist ein Hamiltonkreis somit ein Kreis, der alle Städte enthält.
Der Hamiltonkreis betrachtet also – im Gegensatz zu beispielsweise dem Eulerweg – die Knoten (Städte), nicht die Kanten (Bahnstrecken); einige Kanten werden in der Regel nicht benötigt, um alle Knoten zu besuchen.
Ein Hamiltonweg ist wie ein Hamiltonkreis, Anfangs- und Endknoten müssen hier jedoch nicht gleich sein.
Alternative Begriffe: Hamilton-Kreis, Hamiltonscher Kreis.
Beispiel
Beispiele für Hamiltonkreise
In dem obigen Graphen gibt es 6 Knoten A bis F und 6 Kanten 1 bis 6, die in der Reihenfolge der Zahlen jeweils genau einmal genutzt werden, bis man am Ausgangspunkt A wieder ankommt.
Mehrere Hamiltonkreise
Es gibt oft mehrere Hamiltonkreise in einem Graphen und es werden oft auch nicht alle Kanten benötigt:
Der Graph ist links aufgezeichnet: 4 Knoten A bis D in quadratischer Anordnung und 6 Kanten.
In der Mitte ist ein möglicher Hamiltonkreis farbig markiert; dieser fährt einfach die 4 Außenkanten ab.
Rechts ist ein weiterer möglicher Hamiltonkreis farbig markiert; dieser nutzt 2 Außenkanten und 2 Diagonalen.
Der Hamiltonkreis in der Mitte ist kürzer als der rechts, da in einem Quadrat die Diagonalen länger sind als die Außenkanten.
Beispielhafte Probleme
Das Travelling-Salesman-Problem, bei dem ein Handlungsreisender eine bestimmte Anzahl von Städten (etwa Aachen, Bonn und Celle) (nur) einmal besuchen muss, sucht beispielsweise den kürzesten Hamiltonkreis.