Ein Eulerkreis (auch Euler-Tour, Eulerscher Kreis) ist ein geschlossener Kantenzug in einem Graphen, der jede Kante genau einmal enthält und am Ausgangsknoten endet. Benannt ist er nach dem Mathematiker Leonhard Euler (1707–1783), der 1736 mit dem Königsberger Brückenproblem die Grundlage der Graphentheorie legte: Sieben Brücken verbinden die Stadtteile von Königsberg — die Frage, ob es einen Rundweg über alle Brücken gibt, verneinte Euler, weil vier Knoten ungeraden Grad hatten. Der Eulerkreis hat mit der Kreiszahl e übrigens nichts zu tun, er ehrt nur ihren Namensgeber.
Wann existiert ein Eulerkreis?
Der Satz von Euler liefert eine einfache, vollständige Charakterisierung: Ein zusammenhängender Graph besitzt genau dann einen Eulerkreis, wenn jeder Knoten geraden Grad hat. Ist der Graph zusammenhängend und haben genau zwei Knoten ungeraden Grad, gibt es keinen geschlossenen Kreis, aber einen offenen Eulerschen Weg: Er startet an dem einen ungeraden Knoten und endet am anderen. Diese Prüfung ist in linearer Zeit möglich und damit deutlich einfacher als beim Hamiltonkreis, für den es kein einfaches Kriterium gibt.
Einen Eulerkreis finden: Hierholzer
Der Hierholzer-Algorithmus konstruiert einen Eulerkreis in O(E): Er startet an einem Knoten, folgt Kanten, bis er wieder am Start ankommt, und integriert dann übersprungene Zyklen entlang des Wegs per Tiefensuche. Der ältere Fleury-Algorithmus wählt Schritt für Schritt nur Brücken-Kanten, ist aber mit O(E²) langsamer.
Anwendungen
- Chinesisches Postbotenproblem: kürzeste Route über alle Straßen eines Viertels.
- Straßenreinigung, Müllabfuhr und Winterdienst planen Routen als Eulerkreise.
- Leiterplatten-Design: Bohrfahrten über alle Löcher minimieren.
- Bioinformatik: Genom-Assemblierung über De-Bruijn-Graphen.
Abgrenzung
Der Eulerkreis besucht Kanten genau einmal, der Hamiltonkreis besucht Knoten genau einmal — zwei verwandte, aber unabhängige Konzepte. Grundbausteine sind Knoten und Kanten aus der Graph-Datenstruktur; das Grad-Konzept (grad) entscheidet über die Existenz. Übliche Darstellungen sind Adjazenzliste und Adjazenzmatrix. Eulerkreise werden meist in ungerichteten Graphen betrachtet, die Zusammenhangskomponente muss dafür durchgängig sein. Eigenes Beispiel: ein Quadrat mit beiden Diagonalen hat fünf Knoten mit ungeradem Grad — und damit weder Eulerkreis noch Eulerschen Weg.