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. 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.
Hamiltonweg
Ein Hamiltonweg ist wie ein Hamiltonkreis, Anfangs- und Endknoten müssen hier jedoch nicht gleich sein.
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.
Alternative Begriffe: Hamilton-Kreis, Hamiltonscher Kreis.