Eulerianorientierung

Eine Eulerianorientierung eines ungerichteten Graphen G ist eine Orientierung seiner Kanten, bei der der Eingangsgrad jedes Knotens gleich dem Ausgangsgrad ist. Isolierte Knoten mit Grad Null erfüllen die Bedingung ebenfalls.

Existenzkriterium: Eine Eulerianorientierung existiert genau dann, wenn jeder Knoten eine gerade Gradzahl besitzt. Denn aus der Gleichheit von Eingangs- und Ausgangsgrad folgt deg(v) = Eingangsgrad(v) + Ausgangsgrad(v) = 2·Eingangsgrad(v), also gerade. Umgekehrt besitzt jede nicht isolierte Komponente eines Graphen mit allen geraden Graden einen Eulerkreis. Orientiert man die Kanten dieses Kreises, erhält man eine Eulerianorientierung für diese Komponente; isolierte Knoten bleiben unverändert.

Konstruktion: In jeder Zusammenhangskomponente mit mindestens einer Kante wird ein Eulerkreis ermittelt (z. B. mit Hierholzers Algorithmus). Die Kanten werden in der Reihenfolge des Kreises orientiert. Die Vereinigung der Orientierungen ergibt die Eulerianorientierung des ursprünglichen Graphen.

Eigenschaften: Für eine zusammenhängende Graph gilt, dass die Eulerianorientierung, die aus einem Eulerkreis entsteht, eine stark zusammenhängige gerichtete Graph ergibt. Allgemein bleibt jede Komponente mit Kanten stark zusammenhängend, während isolierte Knoten unproblematisch bleiben. Anwendungen finden sich in balancierten Netzwerken, Fluss- und Routingproblemen, wo eine gleichmäßige Verteilung von Eingangs- und Ausgangsverbindungen wünschenswert ist.