Was ist ein Hamiltonkreis?

Sind der Anfangs- und Endpunkt eines Pfades in einem Graphen gleich, so spricht man von einem Zyklus. Der Hamiltonkreis ist eine Sonderform eines solchen Zyklus. Er beschreibt den Pfad in einem Graphen, welcher am gleichen Knoten beginnt und endet, wobei er jeden Knoten des Graphen durchläuft.

Die Suche nach der Existenz eines Hamiltonkreises in einem Graphen wird als Hamiltonkreisproblem bezeichnet. Gemäß der Unterscheidung nach gerichteten und ungerichteten Graphen kann auch das Hamiltonkreisproblem in ein gerichtetes und ungerichtetes unterschieden werden.