mini|klasse=skin-invert-image|In kantendisjunkte Kreise zerlegter Eulergraph. Eine Eulertour der Knotenfolge (1, 2, 3, 1, 8, 7, 6, 9, 5, 4, 9, 7, 4, 3, 7, 1) ist in alphabetischer Reihenfolge angegeben.
Ein Eulerkreis (auch geschlossener Eulerzug, Eulertour) ist in der Graphentheorie ein Zyklus, der alle Kanten eines Graphen genau einmal enthält.
Ein offener Eulerzug (auch Eulerpfad oder Eulerweg) ist gegeben, wenn Start- und Endknoten nicht gleich sein müssen, wenn also statt eines Zyklus lediglich eine Kantenfolge verlangt wird, welche jede Kante des Graphen genau einmal enthält. Ein bekanntes Beispiel ist das „Haus vom Nikolaus“.
Ein zusammenhängender Graph, der einen Eulerkreis besitzt, heißt eulerscher Graph. Enthält ein Graph lediglich einen Eulerweg und keinen Eulerkreis, so heißt er semi-eulerscher Graph. Die Aufgabe, zu einem gegebenen Graph zu bestimmen, ob dieser eulersch ist oder nicht, wird als Eulerkreisproblem bezeichnet. Es geht auf das 1736 von Leonhard Euler gelöste Königsberger Brückenproblem zurück. Das Problem existiert auch für gerichtete Graphen und Graphen mit Mehrfachkanten.
Entgegen seinem Namen ist der Eulerkreis kein Kreis, zumindest wenn der häufigen Definition gefolgt wird, nach der sich in einem Kreis kein Knoten wiederholen darf.
Geschichte Leonhard Euler fragte in seiner Arbeit 1736 zum Königsberger Brückenproblem – übersetzt in die heutige Fachsprache –, ob der durch die Pregelbrücken der Stadt gegebene Graph ein semi-eulerscher Graph ist, das heißt, ob ein Eulerweg existiert, und verneinte dies, da der Graph mehr als zwei Knoten mit ungeradem Grad hatte. Euler bewies, dass ein semi-eulerscher Graph höchstens zwei Knoten ungeraden Grades haben kann. Er vermutete und gab ohne Beweis an, dass dies eine hinreichende Bedingung sei: Ein zusammenhängender Graph, in dem jeder Knoten geraden Grad hat, ist ein Eulergraph. Ein Beweis des Satzes wurde zuerst von Carl Hierholzer 1873 veröffentlicht.Hierholzer Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren, Mathematische Annalen, Bd. 6, 1873, S. 30–32, Online Auf dem Beweis basiert der Algorithmus von Hierholzer zum Auffinden eines Eulerwegs.
Charakterisierung Nach dem Satz von Euler-Hierholzer sind eulersche Graphen leicht zu charakterisieren.
Sei G ein Graph, bei dem höchstens eine Zusammenhangskomponente Kanten enthält. Dann sind folgende Aussagen äquivalent: G ist eulersch, jeder Knoten in G hat geraden Grad. die Kantenmenge von G ist die Vereinigungsmenge aller Kanten von paarweise disjunkten Kreisen.
Analog sind für einen gerichteten Graphen G, bei dem höchstens eine starke Zusammenhangskomponente Kanten enthält, folgende Aussagen äquivalent: G ist eulersch, für jeden Knoten in G sind Eingangsgrad und Ausgangsgrad gleich. die Kantenmenge von G ist die Vereinigungsmenge aller Kanten von paarweise disjunkten gerichteten Kreisen.
Verallgemeinerung: Eulerweg Ein ungerichteter zusammenhängender Graph enthält genau dann einen Eulerweg, wenn zwei oder keiner seiner Knoten von ungeradem Grad sind. Hat kein Knoten einen ungeraden Grad, handelt es sich bei jedem Eulerweg um einen Eulerkreis.
Entscheidungsproblem Die Frage, ob für einen gegebenen Graph ein Eulerkreis existiert, lässt sich algorithmisch relativ leicht lösen, da ein Graph genau dann eulersch ist, wenn er zusammenhängend ist und jeder Knoten geraden Grad besitzt. Mittels Tiefensuche lässt sich dies leicht in linearer Zeit feststellen.
Auffinden eines Eulerkreises Zum Auffinden eines Eulerkreises existieren mehrere Verfahren. Der Algorithmus von Fleury stammt aus dem Jahr 1883 und verfolgt einen sehr einfachen Ansatz, weshalb er eine Laufzeit von der Größenordnung hat.
Effizienter ist der Algorithmus von Hierholzer, der einen Eulerkreis in Linearzeit berechnet.
Algorithmus von Fleury Im Algorithmus von Fleury spielen Brückenkanten eine wichtige Rolle. Das sind Kanten, ohne die der Graph in zwei Komponenten zerfallen würde.
Der Algorithmus fügt einer anfangs leeren Kantenfolge alle Kanten eines Graphen hinzu, sodass ein Eulerkreis entsteht. Wähle einen beliebigen Knoten als aktuellen Knoten. Wähle unter den unmarkierten, mit dem aktuellen Knoten inzidenten Kanten eine beliebige Kante aus. Dabei sind zuerst Kanten zu wählen, die im unmarkierten Graphen keine Brückenkanten sind. Markiere die gewählte Kante und füge sie der Kantenfolge hinzu. Wähle den anderen Knoten der gewählten Kante als neuen aktuellen Knoten. Wenn noch unmarkierte Kanten existieren, dann gehe zu Schritt 2.
Ob eine Kante eine Brückenkante ist, kann mittels Tiefensuche in Laufzeit überprüft werden. Da pro Schritt eine Kante entfernt wird, werden Iterationen benötigt. Die Anzahl der pro Iteration geprüften Kanten entspricht dem Grad des aktuellen Knotens. Insgesamt kann die gesamte Anzahl überprüfter Kanten durch beschränkt werden. Die gesamte Laufzeit ist damit von der Größenordnung .
Programmierung Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung des Algorithmus von Fleury für einen ungerichteten Graphen. Der ungerichtete Graph wird als Klasse UndirectedGraph deklariert. Bei der Ausführung des Programms wird die Methode Main verwendet, die den Eulerkreis oder Eulerpfad auf der Konsole ausgibt.GeeksforGeeks: Fleury’s Algorithm for printing Eulerian Path or Circuit
Code-Schnipsel using System; using System.Collections.Generic;
// Deklariert die Klasse für die Knoten des Graphen class Node { public int index; public string value; public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Menge der Nachbarknoten }
// Deklariert die Klasse für den ungerichteten Graphen class UndirectedGraph { public HashSet<Node> nodes = new HashSet<Node>();
// Diese Methode verbindet die Knoten node1 und node2 miteinander. public void ConnectNodes(Node node1, Node node2) { node1.adjacentNodes.Add(node2); node2.adjacentNodes.Add(node1);
// Diese Methode trennt die Knoten node1 und node2 voneinander. public void DisconnectNodes(Node node1, Node node2) { node1.adjacentNodes.Remove(node2); node2.adjacentNodes.Remove(node1);
class Program { // Diese Methode gibt die Eulerpfad, die als Liste von Knoten übergeben wird, in der Form (A, B), (B, C), (C, D), ... als Text zurück. public static string EulerPathToString(List<Node> nodeList) { string text = ""; for (int i = 0; i < nodeList.Count - 1; i++) // for-Schleife, die die Knoten durchläuft
text += "(" + nodeList[i].value + ", " + nodeList[i + 1].value + "), ";
text = text.Substring(0, text.Length - 2); return text;
// Diese Methode gibt die Liste der durchlaufenen Knoten zurück public static List<Node> GetEulerPathByFleury(UndirectedGraph undirectedGraph, Node startNode) { // Behandelt den Fall, dass es zwei Knoten mit ungeradem Grad gibt und sucht einen Knoten mit ungeradem Grad foreach (Node node in undirectedGraph.nodes) // foreach-Schleife, die alle Knoten des Graphen durchläuft
if (node.adjacentNodes.Count % 2 == 1) // Wenn der Grad des aktuellen Knoten ungerade ist
startNode = node; // Knoten als Startknoten auswählen und foreach-Schleife verlassen break;
List<Node> nodeList = new List<Node>(); // Initialisiert die Liste der durchlaufenen Knoten Node nextNode = null; // Referenz auf den jeweils nächsten Knoten der Eulerpfad, die gegebenenfalls nach dem vollständigen Durchlaufen der Kanten für den letzten Knoten (Zielknoten) benötigt wird. AddNextEulerPathNode(undirectedGraph, startNode, ref nextNode, nodeList); // Aufruf der rekursiven Methode, die jeweils den nächsten Knoten hinzufügt if (nextNode != null)
nodeList.Add(nextNode); // Wenn Referenz nicht null, Zielknoten hinzufügen
return nodeList;
// Rekursive Methode, die jeweils den nächsten Knoten hinzufügt private static void AddNextEulerPathNode(UndirectedGraph undirectedGraph, Node startNode, ref Node nextNode, List<Node> nodeList) { HashSet<Node> adjacentNodes = new HashSet<Node>(startNode.adjacentNodes); foreach (Node node in adjacentNodes)
if (startNode.adjacentNodes.Contains(node) && IsValidNextEdge(undirectedGraph, startNode, node))
nextNode = node; nodeList.Add(startNode); undirectedGraph.DisconnectNodes(startNode, node); AddNextEulerPathNode(undirectedGraph, node, ref nextNode, nodeList); // Rekursiver Aufruf der Methode
// Diese Methode prüft, ob sich mit der aktuellen Kante die Eulerpfad vervollständigen lässt private static bool IsValidNextEdge(UndirectedGraph undirectedGraph, Node node1, Node node2) { if (node1.adjacentNodes.Count == 1 && node1.adjacentNodes.Contains(node2))
return true;
HashSet<Node> visitedNodes = new HashSet<Node>(); DepthFirstSearch(node1, visitedNodes); int count1 = visitedNodes.Count;
undirectedGraph.DisconnectNodes(node1, node2);
visitedNodes.Clear(); DepthFirstSearch(node1, visitedNodes); int count2 = visitedNodes.Count;
undirectedGraph.ConnectNodes(node1, node2);
return count1 == count2;
// Diese Methode verwendet Tiefensuche, um alle erreichbaren Knoten des Graphen zu durchlaufen private static void DepthFirstSearch(Node startNode, HashSet<Node> visitedNodes) { visitedNodes.Add(startNode); // Fügt den aktuellen Knoten der Menge der markierten Knoten hinzu foreach (Node node in startNode.adjacentNodes) // foreach-Schleife, die alle benachbarten Knoten des Knotens durchläuft
if (!visitedNodes.Contains(node)) // Wenn der Knoten noch nicht markiert wurde
DepthFirstSearch(node, visitedNodes); // Rekursiver Aufruf der Methode mit dem Nachbarknoten als Startknoten
// Hauptmethode, die das Programm ausführt public static void Main() { // Deklariert und initialisiert 5 Knoten Node node1 = new Node{index = 0, value = "A"}; Node node2 = new Node{index = 1, value = "B"}; Node node3 = new Node{index = 2, value = "C"}; Node node4 = new Node{index = 3, value = "D"}; Node node5 = new Node{index = 4, value = "E"}; // Deklariert und initialisiert ein Array mit den Knoten Node[] nodes = {node1, node2, node3, node4, node5}; // Erzeugt einen ungerichteten Graphen UndirectedGraph undirectedGraph = new UndirectedGraph(); int numberOfNodes = nodes.Length; for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten durchläuft
undirectedGraph.nodes.Add(nodes[i]); // Fügt die Knoten dem Graphen hinzu
// Verbindet Knoten des Graphen miteinander undirectedGraph.ConnectNodes(node2, node1); undirectedGraph.ConnectNodes(node1, node3); undirectedGraph.ConnectNodes(node3, node2); undirectedGraph.ConnectNodes(node1, node4); undirectedGraph.ConnectNodes(node4, node5); undirectedGraph.ConnectNodes(node4, node3); undirectedGraph.ConnectNodes(node4, node2); undirectedGraph.ConnectNodes(node3, node5); List<Node> eulerPath = GetEulerPathByFleury(undirectedGraph, node1); // Aufruf der Methode, die die Liste der durchlaufenen Knoten zurückgibt if (eulerPath.Count == 9) // Wenn die Anzahl der durchlaufenen Knoten um 1 größer als die Anzahl aller Kanten ist
string eulerPathText = EulerPathToString(eulerPath); // Aufruf der Methode Console.WriteLine(eulerPathText); // Ausgabe auf der Konsole
else
Console.WriteLine("Es existiert kein Eulerpfad."); // Ausgabe auf der Konsole
Console.ReadLine();
Hinweise: Sowohl für das Referenzieren der Knoten des ungerichteten Graphen als auch für das Referenzieren der Nachbarknoten jedes Knoten wird ein HashSet (Menge) als Datentyp verwendet und mit foreach-Schleifen durchlaufen. Der Vorteil des HashSet für die Nachbarknoten im Vergleich zu einer Liste ist, dass dann meist viel schneller, nämlich mit konstanter Laufzeit, geprüft werden kann, ob ein bestimmter Knoten Nachbarknoten eines anderen Knoten ist (siehe Hashtabelle – Vorteile). Ein Nachteil ist, dass dann die Reihenfolge der durchlaufenen Knoten in den foreach-Schleifen und damit auch die Reihenfolge der ausgegebenen Knoten des Eulerpfads nicht eindeutig oder teilweise zufällig ist.