Wird jeder Knoten in einem Graphen durch einen geschlossenen Pfad durchlaufen und sind Anfangs- und Endpunkt identisch, so spricht man von einem Hamiltonkreis. Die Untersuchung eines Graphen nach der Existenz eines solchen Pfades stellt ein wichtiges Problem in der Graphentheorie dar.
Wir erklären dir in diesem Abschnitt was man unter einem Hamiltonkreis versteht und wann er eine Rolle spielt. Außerdem zeigen wir dir, wann und wie der Hamiltonkreis genutzt werden kann. Mit den anschließenden Übungsaufgaben kannst du dein gelerntes Wissen überprüfen.
Synonym: hamiltonischer Kreis
Inhalt dieser Lektion
Warum ist der Hamiltonkreis wichtig?
Die Frage nach der Existenz eines Hamiltonkreises in einem Graphen kann für die Lösung einer Vielzahl von betriebswirtschaftlichen Problemen genutzt werden. So ist beispielsweise die Routenplanung in der Logistik eine der Anwendungsmöglichkeiten
Was versteht man unter dem 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.
Sonderfall: der Hamiltonweg
Synonym: Hamiltonscher Weg
Genau wie beim Hamiltonkreis beschreibt auch der Hamiltonweg einen Pfad in einem Graphen, der jeden Knoten einmal durchläuft. Allerdings sind hierbei der Anfangs- und Endknoten nicht identisch. Existiert in einem Graphen G ein Hamiltonweg aber kein Hamiltonkreis, so bezeichnet man den Graphen als semihamiltonisch.
Weitere Form eines Zyklus im Graphen: Der Eulerkreis
Synonym: Eulerscher Kreis
Neben dem Hamiltonkreis beschreibt auch der Eulerkreis eine besondere Form eines Zykluses in einem Graphen. Im Gegensatz zum Hamiltonkreis stehen hierbei aber weniger die Knoten im Mittelpunkt als vielmehr die Kanten. Von einem Eulerkreis spricht man, wenn innerhalb des Zyklus jede Kante im Graphen genau einmal genutzt wird.
Dieser kann über sieben Brücken überquert werden. Gesucht wird ein Rundgang durch die Stadt, bei der jede Brücke genau einmal überquert wird. Leonhard Euler bewies im Jahr 1736, dass ein solcher Rundgang nicht möglich ist.
Er fand heraus, dass ein Eulerkreis nur möglich ist, wenn höchstens in zwei der Knotenpunkte ein ungerader Knotengrad existiert. Beim Problem der Königsberger Brücken jedoch besitzt jeder der Knoten einen ungeraden Knotengrad. Demnach kann ein Eulerkreis und damit auch kein entsprechender Rundgang durch die Stadt existieren.
Sonderfall: der Eulerweg
Synonym: Eulerscher Weg
Bei einem Eulerweg sind der Anfangs- und Endknoten nicht identisch, dennoch werden alle Kanten im Graphen genutzt. Das bekannte Kinder-Zeichenspiel „Das Haus vom Nikolaus“ beschreibt einen Eulerweg.
