Euler-Hamilton-Kreis

Euler-Hamilton-KreisIst ein Graph mit Knoten und Kanten gegeben, so kann nach einer Eulerschen Linie (Eulerweg, Eulerkreis) gesucht werden.
Dabei versteht man unter einem Eulerweg einen geschlossenen Kantenzug längs des Graphen, bei dem jede Kante genau einmal durchlaufen wird.

Ein bekanntes Beispiel ist das Königsberger Brückenproblem. Dort sollen alle sieben Brücken bei einem Spaziergang genau einmal passiert werden. Leonhard Euler beschrieb dieses Problem 1736 und begründete auch, warum es keine Lösung geben kann.

Eine Eulersche Linie existiert, wenn von jedem Knotenpunkt eine gerade Anzahl von Kanten ausgeht. Eine geschlossene Linie kann aber auch existieren, wenn maximal zwei Knoten mit ungeradzahliger Kantenzahl existieren. Einen Graph, der einen Eulerkreis besitzt, bezeichnet man auch als Eulerschen Graphen.

In diesem Teilprogramm können Sie Graphen auf die Existenz von Euler- und Hamiltonkreisen untersuchen.
Zuerst müssen Sie einen Graphen mit Knoten und Kanten konstruieren bzw. von der Festplatte laden.

Koordinaten der Knoten
Einen neuen Knoten des Graphen geben Sie ein, indem Sie unter X = und Y = die Koordinaten des Knotens eintragen. Quittieren Sie mit Knoten hinzufügen, wird der Knoten der Liste hinzugefügt und sofort dargestellt.

Im linken Fensterteil wird der entstehende Graph gezeigt. Im rechten Teil wird der Eulersche Kreis später gezeichnet.

Eingetragene Knoten können Sie wieder löschen (Schalter Löschen) oder deren Koordinaten ändern. Für das Ändern empfiehlt sich folgendes Verfahren: Klicken Sie einen Knoten in der Knotenliste mit der Maus doppelt an, so werden dessen Koordinaten in die Eingabezeilen übertragen. Geben Sie dort nun die Änderung ein und bestätigen Sie mit dem Schalter Ändern.

Koordinatenänderungen der Knoten können Sie auch mit der Maus durchführen: Klicken Sie im linken Darstellungsbereich einen Knoten an und bewegen Sie die Maus (Maustaste festhalten), so werden die Koordinaten automatisch übernommen.
Die Knoten werden automatisch mit A beginnend beschriftet. Markieren Sie das Feld Punkte beschriften, werden die Buchstaben auch angezeigt.

Kanten des Graphen
Nach der Eingabe der Knoten müssen die durch Kanten miteinander verbundenen Knoten angegeben werden.
Dazu können Sie unter Kante von … bis den Anfangs- und Endknoten einer Kante eintragen und mit dem Schalter Hinzufügen wieder bestätigen.

Effektiver und vor allem schneller ist es, wenn Sie die Kanten mittels Maus zeichnen. Klicken Sie dazu mit der rechten (!) Maustaste den Anfangsknoten der Kante an. Bewegen Sie nun die Maus bei festgehaltener rechter Maustaste, so sehen Sie eine Strecke. Verschieben Sie die Maus einfach auf den Endknoten und geben Sie die Taste frei. Das Programm übernimmt die eingezeichnete Kante sofort in die Kantenliste.

Ermittlung des Eulerkreises
Nachdem der Graph konstruiert wurde, können Sie nach einem Eulerweg suchen lassen. Klicken Sie dazu auf den Schalter.
Das Programm analysiert den Graphen und testet, ob ein Eulerweg existiert. Ist dies der Fall, beginnt die Suche. Für Graphen ohne ungerade Knoten wird ab dem Knoten A gesucht, bei ungeraden Knoten beginnend ab diesen Stellen.
Im rechten Fensterteil werden die Eulerwege in einer Liste angezeigt, und zwar in der Reihenfolge der besuchten Knoten.

Bei größeren Graphen mit relativ vielen Kanten kann die Suche einige Zeit in Anspruch nehmen. Abbrechen können Sie jederzeit über den Schalter Abbruch.
Das Programm stoppt auch automatisch, wenn 100000 Eulerwege gefunden wurden.

Anzeige eines Eulerkreises
Wurden Eulersche Kreise gefunden, so können Sie diese nach beendeter Suche veranschaulichen. Markieren Sie dazu einen Eintrag in der Liste der Eulerwege und quittieren Sie mit Eulerweg anzeigen. Ein Doppelklick auf einen Eintrag startet die Anzeige sofort.
Das Programm zeigt Ihnen nun im rechten Fensterteil, wie in der Abbildung zu sehen, Schritt für Schritt die Kantenfolge des Eulerweges an.

Hamiltonkreis
Ein Elementarkreis in einem Graphen, der alle Knoten des Graphen genau einmal durchläuft, heißt Hamiltonkreis. Ist ein Graph mit Knoten und Kanten gegeben, so kann nach einem solchen Hamiltonkreis gesucht werden.

Die Springertour ist eine berühmte Anwendung eines Hamiltonkreises: Der Springer soll sich auf einem Schachbrett so bewegen, dass er jedes Feld nur einmal passiert und zum Startpunkt zurückkehrt.

Mitunter kann man auf einem Graphen keinen geschlossenen Hamiltonkreis finden: Es gelingt nicht, zum Anfangsknoten zurückzukehren. Ist es trotzdem möglich, jeden Knoten genau einmal zu erreichen, ohne den Weg zu schließen, so spricht man von einem Hamilton-Pfad.

Nachdem der Graph konstruiert bzw. geladen wurde, können Sie nach Hamiltonkreisen oder Pfaden suchen lassen. Markieren Sie dazu links oben Hamiltonkreis.
Mit dem Schalterklick beginnt das Programm mit der Suche. Im Normalfall wird ab dem Knoten A gesucht. Markieren Sie einen Knoten in der Knotenliste, beginnt die Suche ab diesem Knoten.

Im rechten Fensterteil werden die gefundenen Ergebnisse in einer Liste angezeigt, und zwar in der Reihenfolge der besuchten Knoten. Wird kein geschlossener Hamiltonkreis ermittelt, so können Sie auch nur nach Hamilton-Pfaden suchen lassen, indem Sie das entsprechende Feld markieren.

Bei größeren Graphen mit relativ vielen Kanten kann die Suche sehr viel Zeit in Anspruch nehmen. Abbrechen können Sie wieder über den Schalter Abbruch. Das Programm stoppt auch automatisch, wenn 100000 Kreise bzw. Pfade gefunden wurden.
Die Anzeige des Hamiltonkreises verläuft in gleicher Weise wie die Darstellung des Eulerkreises.

Euler-Hamilton-Kreise auf Graphen

Download

Download eines Einzelprogramms zu Euler- und Hamiltonkreisen:
Den Delphi-Quelltext finden Sie unter Quelltexte.

Haus des Nikolaus

Das Haus des Nikolaus ist ein altes Zeichenspiel für Kinder.
Das Haus soll in einem Zug aus acht Strecken gezeichnet, ohne dass Strecke zweimal durchlaufen wird. Während des Zeichnens spricht man den Satz: „Das ist das Haus des Ni – ko – laus“.
Zu jeder Strecke gehört ein Wort bzw. eine Silbe.
Man sagt auch: „Das ist das Haus vom Nikolaus“ oder „Das ist ein wunderschönes Haus“. Mädchen sollten den Satz beachten: „Wer dies nicht kann, kriegt keinen Mann“.
Graphentheoretisch gesehen ist das Haus vom Nikolaus eine Eulersche Linie.

Numeriert man die Ecken durch, so kann die links beschriebene Zeichenmethode durch 142354312 angegeben werden. Insgesamt existieren 44 verschiedene Lösungen, die bei 1 beginnen und bei 2 enden. Analog beginnen 44 weitere Möglichkeiten bei 2 und enden bei 1.

123143542 123543142 132453412 134235412
135421432 123145342 135423412 142354312
124531432 142135432 143213542 145312432
124134532 124534132 134123542 134532142
142345312 143245312 145321342 123413542
132143542 134124532 134532412 135432142
124135432 132145342 143542312 135412432
143542132 145324312 123453142 124314532
134214532 135412342 135432412 143123542
145342132 123541342 124354132 132435412
142134532 143124532 145312342 145342312

Werden zwei Häuser vom Nikolaus aneinandergefügt, so ist keine Eulersche Linie mehr möglich, da es vier Knoten mit ungeradem Grad gibt.