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

Eulerweg
Eulerweg: Weg, bei dem jede Kante genau einmal durchlaufen wird

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).

Eulerkreis
Eulerkreis: Rundweg, bei dem jede Kante genau einmal durchlaufen wird und Start- und Endpunkt der Reise identisch sind

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.