Eulerweg
Überblick: Eulerweg und Eulerkreis
Ein – nach dem Mathematiker Leonhard Euler benannter – Eulerweg bezieht sich auf einen ungerichteten, zusammenhängenden Graphen, bei dem Knoten mit Kanten in beide Richtungen verbunden sind; etwa eine Eisenbahnkarte (Graph), in der die 10 größten Städte (Knoten) eines Landes mit in beiden Richtungen befahrbaren Bahnstrecken (Kanten) verbunden sind.
Ein Eulerweg ist dann ein Weg, der jede Kante des Graphen genau einmal durchläuft.
Ein Eulerkreis bzw. eine Eulertour haben zusätzlich die Bedingung, dass der Eulerweg an einem Knoten beginnt und dort auch endet. Es ist damit ein Rundweg.
Eulerweg
Beispiel für Eulerweg
In dem obigen Graphen (auch als "Haus des Nikolaus" bekannt) gibt es 5 Knoten A bis E und 8 Kanten 1 bis 8, die in der Reihenfolge der Zahlen jeweils genau einmal genutzt werden.
Eulertour / Eulerkreis
Beispiel für Eulertour / Eulerkreis
Eine Eulertour (auch Eulerkreis genannt, man muss sich aber von "kreisförmig" lösen wie man am Graphen unten sieht) ist ein spezieller Eulerweg, der an einem Knoten beginnt und endet (also eine zusätzliche Bedingung; eine Eulertour startet beispielsweise in München und endet dort; ein Eulerweg hingegen könnte in München beginnen und in Hamburg enden).
In dem obigen Graphen gibt es 6 Knoten A bis F und 10 Kanten 1 bis 10, die in der Reihenfolge der Zahlen jeweils genau einmal genutzt werden, bis man am Ausgangspunkt A wieder ankommt.
Voraussetzung für Eulertour
Eine Eulertour gibt es nur bei Graphen, deren Knoten alle gerade Knotengrade haben, also 2 oder 4 oder 6 und so weiter (Knotengrad ist die Anzahl der Kantenenden an einem Knoten).
Im obigen Graphen hat
- A 4 Kantenenden und damit einen geraden Knotengrad
- B 4 Kantenenden
- C 2 Kantenenden
- D 4 Kantenenden
- E 4 Kantenenden
- F 2 Kantenenden.
Keine Eulertour
Ein Rechteck, bei dem man sich die 4 Ecken als Knoten denkt, hat zum Beispiel nur gerade Knotengrade; in jeden der 4 Knoten / Ecken endet von jeder Seite eine Kante, also jeweils 2 und damit gerade. Hier gibt es eine Eulertour.
Verbindet man zusätzlich zwei der 4 Knoten / Ecken des Rechtecks diagonal, haben diese beiden Knoten einen Knotengrad von 3, also ungerade. Hier gibt es keine Eulertour mehr.
Man kann derartige Probleme (keine Eulertour vorhanden) durch zusätzliche (möglichst kostengünstige) Hilfskanten lösen; dadurch verändert man die Knotengrade und macht sie passend.
Eulergraph
Enthält ein Graph eine Eulertour, ist das ein Eulergraph.
Eulerkreisproblem
Das Eulerkreisproblem besteht darin, in einem Graphen Eulertouren bzw. -kreise zu finden.
Dafür gibt es verschiedene Algorithmen, etwa den Algorithmus von Hierholzer.