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.