Eulerweg
Eulerweg Definition
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.
Eulertour / Eulerkreis
Eine Eulertour (auch Eulerkreis genannt) 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).
Eine Eulertour gibt es nur bei Graphen, deren Knoten alle gerade Knotengrade haben, also 2 oder 4 oder 10 usw. (Knotengrad ist die Anzahl der Kantenenden an einem Knoten).
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.