Inhaltsverzeichnis
1. Was ist ein Eulerweg?
Ein Eulerweg (auch Euler-Pfad genannt) ist ein Weg durch einen Graphen, der jede Kante genau einmal benutzt. Man darf denselben Knoten mehrmals passieren, aber niemals dieselbe Kante zweimal entlanggehen.
Er beantwortet eine erstaunlich praktische Frage: Kann ich bei einem Netz aus Straßen, Rohren oder Kabeln alle durchlaufen, ohne je eine Verbindung zu wiederholen?
2. Eulerweg vs Eulerkreis
Die beiden Begriffe sind eng verwandt, aber nicht identisch:
- Ein Eulerweg benutzt jede Kante einmal und darf an verschiedenen Knoten beginnen und enden.
- Ein Eulerkreis ist ein geschlossener Eulerweg — er benutzt jede Kante einmal und kehrt zum Startknoten zurück.
Jeder Eulerkreis ist auch ein Eulerweg, aber nicht umgekehrt. Was ein Graph zulässt, hängt allein von den Graden seiner Knoten ab.
3. Das Königsberger Brückenproblem
Die preußische Stadt Königsberg wurde durch einen Fluss in vier Landmassen geteilt, die durch sieben Brücken verbunden waren. Die Bürger fragten sich, ob ein Spaziergang möglich sei, der jede Brücke genau einmal überquert und zum Ausgangspunkt zurückkehrt.
1736 bewies Leonhard Euler, dass es einen solchen Weg nicht gibt. Er modellierte jede Landmasse als Knoten und jede Brücke als Kante und machte eine entscheidende Beobachtung: Jedes Mal, wenn man eine Landmasse über eine Brücke betritt, muss man sie über eine andere verlassen — also braucht jeder „Durchgangsknoten" eine gerade Anzahl von Brücken. Alle vier Knoten Königsbergs hatten eine ungerade Anzahl, was den Weg unmöglich machte. Dieser Beweis gilt als die Geburtsstunde der Graphentheorie. (Siehe unsere Geschichte der Graphentheorie.)
4. Die Gradregel: Wann existiert er?
Der Grad eines Knotens ist die Anzahl der Kanten, die ihn berühren. Eulers Erkenntnis liefert einfache, exakte Regeln für einen zusammenhängenden Graphen:
- Ein Eulerkreis existiert genau dann, wenn jeder Knoten einen geraden Grad hat.
- Ein offener Eulerweg existiert genau dann, wenn genau zwei Knoten einen ungeraden Grad haben — und er muss bei einem beginnen und beim anderen enden.
- Haben mehr als zwei Knoten einen ungeraden Grad, existiert kein Eulerweg.
Der Graph muss zudem zusammenhängend sein. Ansonsten zählt man einfach die Knoten mit ungeradem Grad.
Durchlaufen Sie den Graphen selbst
Bauen Sie ein Netz und sehen Sie zu, wie ein Algorithmus einen Eulerweg Kante für Kante zeichnet — und warum Knoten mit ungeradem Grad ihn verhindern.
Visualisierung öffnen5. Ihn finden: Algorithmen von Fleury und Hierholzer
Sobald man weiß, dass ein Weg existiert, konstruieren ihn zwei klassische Algorithmen:
Algorithmus von Fleury
Durchlaufen Sie den Graphen Kante für Kante und überqueren Sie nie eine Brücke (eine Kante, deren Entfernung den Graphen trennen würde), außer Sie haben keine andere Wahl. Leicht verständlich, aber das ständige Prüfen auf Brücken macht ihn relativ langsam.
Algorithmus von Hierholzer
Die effiziente Wahl mit Laufzeit O(E). Folgen Sie Kanten zu einer geschlossenen Schleife, suchen Sie dann wiederholt einen Knoten auf Ihrem Weg, der noch ungenutzte Kanten hat, und fügen Sie dort eine weitere Schleife ein. Wenn keine ungenutzten Kanten mehr übrig sind, verschmelzen die Schleifen zu einem einzigen Eulerkreis.
6. Euler vs Hamilton
Sie werden ständig verwechselt, sind aber völlig verschiedene Probleme:
- Ein Euler-Weg besucht jede Kante einmal.
- Ein Hamilton-Weg besucht jeden Knoten einmal.
Der Clou ist rechnerisch: Zu entscheiden, ob ein Eulerweg existiert, ist einfach (ungerade Grade zählen), während die Frage nach einem Hamiltonweg NP-vollständig ist — eines der schwersten Probleme der Informatik. Das Problem des Handlungsreisenden ist eine berühmte Hamilton-Aufgabe.
7. Praktische Anwendungen
- Routeninspektion (Briefträgerproblem): die kürzeste Route finden, die jede Straße abdeckt — Postzustellung, Müllabfuhr, Schneeräumung, Straßenreinigung.
- DNA-Sequenzierung: moderne Genom-Assemblierung baut aus kurzen Reads einen De-Bruijn-Graphen und findet einen Eulerweg, um die Sequenz zu rekonstruieren.
- Netzwartung: jede Verbindung eines Telekom- oder Versorgungsnetzes genau einmal prüfen.
- „In einem Zug" gezeichnete Figuren: das klassische Rätsel, eine Figur ohne Absetzen des Stifts zu zeichnen, ist genau eine Eulerweg-Frage.
Häufig gestellte Fragen
Was ist der Unterschied zwischen Eulerweg und Eulerkreis?
Ein Eulerweg benutzt jede Kante genau einmal und kann an verschiedenen Knoten beginnen und enden. Ein Eulerkreis benutzt ebenfalls jede Kante einmal, muss aber am selben Knoten beginnen und enden.
Woran erkenne ich, ob ein Graph einen Eulerweg hat?
In einem zusammenhängenden Graphen existiert ein Eulerkreis, wenn jeder Knoten geraden Grad hat, und ein offener Eulerweg, wenn genau zwei Knoten ungeraden Grad haben. Haben mehr als zwei Knoten ungeraden Grad, existiert kein Eulerweg.
Was ist der Unterschied zwischen Euler- und Hamiltonweg?
Ein Eulerweg besucht jede Kante einmal, ein Hamiltonweg jeden Knoten einmal. Das Prüfen auf einen Eulerweg ist einfach, das Prüfen auf einen Hamiltonweg dagegen NP-vollständig.
Warum ist das Königsberger Brückenproblem unlösbar?
Alle vier Landmassen waren mit einer ungeraden Anzahl von Brücken verbunden. Ein Eulerweg erlaubt höchstens zwei Knoten mit ungeradem Grad, daher ist es unmöglich, jede Brücke genau einmal zu überqueren.