Eulerpfad

Ein Eulerpfad ist in der Graphentheorie ein Pfad, der jede Kante eines endlichen Graphen genau einmal durchläuft. Enthält der Pfad dieselben Knoten, spricht man von einem Eulerpfad, der von einem Startknoten zu einem Endknoten führt. Falls Start- und Endknoten identisch sind, spricht man von einem Eulerkreis (Eulerzyklus), der alle Kanten genau einmal besucht und wieder zum Startknoten zurückkehrt.

Ein wichtiger Unterschied besteht zwischen ungerichteten und gerichteteten Graphen. Bei ungerichteten Graphen gilt Folgendes: Ein endlicher Graph besitzt einen Eulerpfad genau dann, wenn er zusammenhängend ist, abgesehen von Knoten ohne Kanten, und entweder genau Null oder genau zwei Knoten mit ungeradem Grad besitzt. Sind keine Knoten ungeraden Grads, existiert ein Eulerkreis; treten genau zwei ungerade Grade auf, verläuft der Eulerpfad beginnend an einem der ungeraden Knoten und endend am anderen.

Bei gerichteten Graphen (Digraphen) gelten andere Bedingungen: Die Knoten mit nichtnullen Kanten müssen zu einer zusammenhängenden Struktur gehören, und in/outdegrees müssen bestimmten Gleichungen folgen. Für einen Eulerpfad gilt: An allen Knoten außer Start- und Endknoten gilt indegree = outdegree; der Startknoten hat outdegree = indegree + 1, der Endknoten indegree = outdegree + 1. Gilt Indegree = Outdegree für alle Knoten, existiert ein Eulerkreis. Häufig wird zusätzlich vorausgesetzt, dass der Graph nach Entfernen von Knoten mit null Degree stark zusammenhängend bleibt.

Algorithmisch lässt sich ein Eulerpfad oder -kreis mit dem Hierholzer-Algorithmus finden. Dieser spult systematisch Zyklen ab und verbindet sie zu einem Gesamtkadenzpfad. Die Methode läuft in Zeit O(E), wobei E die Anzahl der Kanten ist.

Historisch geht der Begriff auf Leonard Euler zurück, der das Problem der Königsberger Brücken 1736 analysierte und damit die Idee eines Eulerpfades begründete. Anwendungen finden sich in Puzzle-Lösungen, Genom-Sequenzierung und Netzwerkdesign.