Eulerpfad (auch Eulerweg oder offener Eulerzug) ist ein Pfad durch einen Graphen, der jede Kante genau einmal benutzt — und an einem anderen Knoten endet, als er begonnen hat. Er ist die offene Variante des Eulerkreises, der am Startknoten zurückkehrt.
Existenzkriterium
Ein zusammenhängender Graph besitzt genau dann einen Eulerpfad, wenn er genau zwei Knoten ungeraden Grades hat. Der Pfad muss an einem dieser beiden Knoten beginnen und am anderen enden. Hat der Graph dagegen keinen Knoten ungeraden Grades, existiert sogar ein Eulerkreis — die geschlossene Variante. Bei mehr als zwei Knoten ungeraden Grades ist kein vollständiger Kantenpfad möglich.
Konstruktion: Hierholzer-Algorithmus
Der Hierholzer-Algorithmus findet einen Eulerpfad in linearer Zeit: Man startet an einem der Knoten ungeraden Grades, folgt beliebigen unbenutzten Kanten, bis man nicht weiterkommt, und fügt gefundene Kreisstücke anschließend zur Route zusammen. Entscheidend ist, dass man danach noch vorhandene unbenutzte Kanten aufgreift und einbaut.
Praktische Bedeutung
- Routenplanung: Straßenkehren oder Postzustellung — jede Strecke genau einmal abfahren, ohne Wenden zu müssen.
- Schneeräumung: Winterdienst plant Touren so, dass jede Fahrbahn abgedeckt ist.
- Bioinformatik: DNA-Sequenz-Assemblierung nutzt Eulerpfade in de-Bruijn-Graphen.
- Netzwerk-Design: Inspektion von Leitungen mit minimaler Wiederholung.
Abgrenzung
Der Eulerkreis ist der Sonderfall mit Rückkehr zum Start — beide zusammen werden als Euler-Touren bezeichnet. Nicht zu verwechseln mit dem Hamiltonkreis, bei dem jeder Knoten genau einmal besucht wird (Kanten dürfen frei bleiben). Während das Euler-Problem in linearer Zeit lösbar ist, ist das Hamilton-Problem NP-vollständig. Wichtige Grundlagen sind der Knotengrad und die Zusammenhangskomponente des Graphen.