Eulerpfadproblem

Geschrieben von Kevin De Keyser.

Das folgende Skript befasst sich mit der Geschichte des Eulerkreisproblems, einem Beweis von Euler’s theorem und einer Implementierung von zwei verschiedenen Algorithmen um einen konkreten Eulerpfad zu finden.

Die sieben Brücken von Königsberg

Frühmorgens 1736 bekam Leonhard Euler einen Brief vom Adelsgeschlecht in Preussen. Dort wollte nämlich ein König eine Parade durch Kaliningrad organisieren und dabei war ihm wichtig jede Brücke einmal zu überqueren, damit ihn möglichst viele Leute bewundern konnten. Um nicht albern zu wirken, wollte der König das mehrfache überqueren einer Brücke vermeiden. Nach ein paar Stunden Kopfzerbrechen fand der König immer noch keine Lösung und entschied sich diese Frage einem berühmten Rätsellöser (Mathematiker) seiner Zeit zu stellen. Vielleicht findest du ja eine Lösung zu diesem Problem. Unten findest du eine Karte von Königsberg zu Eulers Lebzeiten, die Brücken sind dabei Gelb markiert:

So oder ähnlich hätte dieses Problem bei Leonhard Euler landen können, die vorherige Geschichte ist aber nur Spekulation meinerseits.

Tatsächlich hat sich aber Leonhard Euler an dieses Problem gewagt und wie jeder gute Mathematiker hat er dieses Brückenproblem ein wenig abstrahiert. Er vereinfachte die Landmassen zu Punkten (sogenannte Knoten) und die Brücken zu Linien (sogenannte Kanten). Diese Gebilde nennen wir heute Graphen und verwenden sie als mächtiges Hilfsmittel um verschiedene Probleme zu lösen, Strassen sind nur eines von vielen Anwendungsgebieten von Graphen.

Eine etwas mathematischere Definition eines Graphes wäre wohl, dass ein Graph ein geordnetes Paar von 2 Mengen ist. Die erste Menge besteht aus den Knoten (bzw. deren Nummerierung) und die zweite Menge besteht aus ungeordneten Paaren, welche jeweils eine Verbindung zwischen zwei Elementen der ersten Menge darstellen. Formal: \(G = (V,E) \,|\, E \subseteq \{\{u,v\}\,|\,u,v\in V \}\)

Doch damit nicht genug! Leonhard Euler war schliesslich kein Amateur-Mathematiker, und wenn er keinen Pfad finden konnte, dann musste er wenigstens beweisen, dass es keine Lösung für dieses Problem gibt.

Um das Problem zu lösen erfand er das Konzept des Grads (Englisch: degree). Der Grad ist dabei die Anzahl Kanten, die mit einem Knoten verbunden sind, und ist damit eine Eigenschaft eines Knotens. Die jeweiligen Grade des Graphs sind unten mit weiss eingezeichnet.

Würde der König nun entlang des Graphen laufen, müsste er bei jedem Knoten, den er besucht, den Grad um zwei senken, da er dieselben Kanten nicht zweimal besuchen kann (die Brücke, die er nimmt um zur Landmasse zu kommen, und die Brücke, die er nimmt um von der Landmasse wegzukommen). Wenn die Grade aller Knoten 0 sind, hat der König sein Ziel geschafft.

In der Theorie unterscheidet man dabei zwischen einem Eulerzyklus und einem Eulerpfad. Beim Eulerzyklus muss der König am gleichen Ort ankommen, an dem er gestartet ist (Rundspaziergang), beim Eulerpfad nicht.

Euler fiel auf, dass ein Eulerzyklus genau dann möglich ist, wenn die Grade aller Knoten gerade sind.

Wenn genau 2 Knoten einen ungeraden Grad besitzen, ist zwar kein Eulerzyklus mehr möglich, doch ist ein Eulerpfad immer noch möglich. Einen Graph, bei dem ein Eulerzyklus oder Eulerpfad möglich ist, wird manchmal traversierbar genannt.

Findest du den Eulerpfad im untenstehenden Bild? (Die Überschneidungen ohne Knoten kannst du dir als übereinander hängende, aber nicht verbundene Brücken vorstellen.)

Man muss logischerweise bei den Knoten mit ungeradem Grad beginnen, beziehungsweise enden, da man sonst irgendwann in eine Sackgasse läuft.

Die Eigenschaft traversierbar gilt als historisch erstes Theorem der Graphentheorie, jedoch hat nicht Euler diese Eigenschaft bewiesen, sondern erst Hierholzer 137 Jahre später. Hierholzer hat nicht nur einen Beweis geliefert, sondern gleich auch noch einen Algorithmus um einen konkreten Eulerpfad zu finden, falls einer existiert.

Das Eulerpfadproblem (bzw. Eulerzyklusproblem) ist auch auf gerichtete Graphen anwendbar. In unserem Beispiel wären die Kanten eines gerichteten Graphen Einbahnstrassenbrücken. Im Gegensatz zum Grad (degree) gibt es hier sowohl den indegree (Anzahl Kanten, die auf den Knoten zeigen, bzw. Anzahl Einbahnstrassenbrücken, mit welchen man auf die Landmasse kommen kann), als auch den outdegree (Anzahl Kanten, die weg vom Knoten zeigen, bzw. Anzahl Einbahnstrassenbrücken mit welchen man die Landmasse verlassen kann). Ein Eulerzyklus ist nun nur möglich wenn bei allen Kanten \(outdegree = indegree\) gilt. Ein Eulerpfad ist ausserdem möglich wenn genau ein Knoten mit \(outdegree - indegree = 1\) und genau ein Knoten mit \(outdegree - indegree = -1\) existiert, die jeweiligen Start- bzw. Endknoten des Pfades.

Zudem muss der gesamte Graph ein strongly connected component sein, da es sonst per Definition unmöglich ist jede Kante zu besuchen. Der untenstehende Algorithmus wird aber beim berechnen automatisch feststellen, ob ein Eulerpfad möglich ist oder nicht.

Hamiltonpfad vs. Eulerpfad Verwechsle nie das Eulerpfadproblem mit dem Hamiltonpfadproblem! Beim Hamiltonpfadproblem ist nach einem Pfad gesucht der jeden Knoten genau einmal besucht, beim Eulerpfadproblem ist nach einem Pfad gesucht der jede Kante genau einmal besucht. Das Eulerpfadproblem lässt sich in polynomieller Laufzeit lösen, während sich das Hamiltonpfadproblem nur in exponentioneller Laufzeit lösen lässt (ausser \(P = NP\)).

Hierholzer-Algorithmus

Der Hierholzer-Algorithmus löst das Eulerpfadproblem in \(\mathcal{O}(E)\), wobei \(E\) die Anzahl gerichteter Kanten ist. Der gerichtete Graph wird hier als Adjazenzliste dargestellt (konkret in C++ als std::vector<std::vector<int> >). Erinnerung: Dabei ist eine gerichtete Kante von u nach v dargestellt als ein Element von graph[u] mit Wert v (d.h. es gibt einen Index i sodass graph[u][i]=v).

Bevor man den Algorithmus beginnt, sollte man feststellen, ob ein Eulerpfad überhaupt möglich ist, und falls ja, sollte man den Knoten mit \(outdegree - indegree = 1\) als Startpunkt verwenden. Haben alle Knoten \(outdegree = indegree\), kann man einfach einen beliebigen Knoten als Startpunkt für den Algorithmus wählen.

Vom Startpunkt aus wird nun eine Art Tiefensuche (DFS) gestartet. Man beginnt beim Startpunkt und besucht einen beliebigen Nachbarknoten. Die Kante, die man dabei verwendet hat, wird aus dem Graphen gelöscht. Beim nächsten Knoten passiert das Gleiche und so weiter. Wichtig dabei ist, dass der bisherige Pfad abgespeichert wird.

Irgendwann stösst man dann auf eine Sackgasse. Diese Sackgasse muss der Endpunkt des Eulerpfads sein!

Warum muss an dieser Stelle ausgerechnet der Endpunkt des Eulerpfads sein? Jedes Mal wenn man einen Knoten besucht, senkt sich der indegree um 1 und der outdegree ebenfalls um 1. Bei Knoten mit \(outdegree = indegree\) kann es deswegen nie zu einer Sackgasse führen! Beim Startknoten wird aber gleich zu Beginn nur der outdegree um 1 gesenkt. Im Fall wo es einen Eulerzyklus gibt, kann es also nur an diesem Punkt zu einer Sackgasse kommen, da es der einzige Punkt ist bei dem \(outdegree - indegree = -1\). Im Fall wo es einen Eulerpfad gibt, aber keinen Eulerzyklus, wird der Startknoten gleich zu Beginn wie der Rest auf \(outdegree = indegree\) abgeändert. Auch in diesem Fall gibt es nur einen Endpunkt bei dem \(outdegree - indegree = -1\).

Dieser Pfad, den man bis jetzt gefunden hat, ist aber noch nicht unbedingt der ganze Eulerpfad.

Wenn man bei dem Diagramm unten z.B. bei Knoten a beginnt und folgenden Pfad findet a->b->c->a, hat man noch nicht alle Kanten besucht.

%3 a a b b a->b c c b->c d d b->d c->a e e d->e f f d->f e->b f->d f->f

Die wichtige Feststellung hier sollte aber sein, dass der übriggebliebene Teilgraph zwingend einen Eulerzyklus haben muss, da bei jedem Knoten gilt \(indegre=outdegree\) !

Da der übrig gebliebene Teilgraph einen Eulerzyklus hat, können wir den selben Algorithmus wieder an einem beliebigen Startknoten des Teilgraphen beginnen. Damit der Eulerpfad aber zusammenhängend ist, wählt man einen Knoten, den man bereits besucht hat (bei unserem Beispiel wäre das Knoten b). In blau wird nun eine zweite Suche gestartet, die irgend einen Pfad wählt, aber am Ende am Knoten b enden muss, da dieser der einzige Knoten ist bei dem \(outdegree - indegree = -1\).

%3 a a b b a->b c c b->c d d b->d c->a f f d->f e e d->e f->d f->f e->b

Diesen blauen Pfad kann man dann einfach zu dem bisher gefundenen Lösungspfad hinzufügen: a->b-> d->e->b ->c.

Wiederholt man diesen Prozess, bis alle Kanten entfernt sind, hat man den Eulerpfad bzw. Eulerzyklus gefunden, es sei denn der Graph war nicht streng zusammenhängend (strongly connected). Einfach die Länge des berechneten Pfades vergleichen mit den Anzahl Kanten, und wenn diese gleich sind, hat man den Pfad gefunden.

Nicht rekursiv implementieren! Das Eulerzyklusproblem (Eulerpfadproblem) sollte nicht rekursiv implementiert werden, da das Stack-Limit sehr schnell erreicht wird. Nur rekursiv implementieren, wenn \(E < 100'000\), ansonsten iterativ implementieren.

Effiziente Implementation für Hierholzer’s Algorithmus für gerichtete Graphen, aber stack-limit anfällig (rekursiv): UNTESTED

//Euler tour for directed graphs:
list<int> eulerPath;
vector<vector<int> > graph;
void hierholzerCycle(list<int>::iterator it) {
    while(!graph[*it].empty()) {
        eulerPath.insert(it, graph[*it].back());
        graph[*it].pop_back(); //delete directed edge
        --it;
    }
    //now crawl back and make sure that there are no more cycles left
    while(++it != eulerPath.end()) {
        if(!graph[*it].empty()) hierholzerCycle(it);
    }
}

Iterative Implementation von Johannes (tabs vs. spaces):

int n, m; cin >> n >> m;
vector<vector<pair<int, int> > > g(n);
for (int i=0; i<m; ++i) {
  int a, b; cin >> a >> b; --a; --b;
  g[a].emplace_back(b, i);
  g[b].emplace_back(a, i);
};
int w=-1; //initial start position
for (int i=0; i<n; ++i) {
  if (g[i].size()%2) {
    if (w != -1) {
      g[i].emplace_back(w, m);
      g[w].emplace_back(i, m++);
      w = -1;
    } else {
      w = i;
    }
  }
}
// BEGIN EULER TOUR
vector<bool> deleted(m);
vector<int> tour, backtrack{0};
while (!backtrack.empty()) {
  auto c = backtrack.back();
  while (!g[c].empty() && deleted[g[c].back().second])
    g[c].pop_back();
  if (g[c].empty()) {
    tour.push_back(backtrack.back());
    backtrack.pop_back();
  } else {
    deleted[g[c].back().second] = true;
    backtrack.push_back(g[c].back().first);
    g[c].pop_back();
  }
}
// END EULER TOUR
if (tour.size()%2==0)
  tour.push_back(tour.front());

Den genau gleichen Algorithmus kann man verwenden um das Eulerpfadproblem für ungerichtete Graphen zu lösen. Als Startpunkt wählt man einen Knoten, der einen ungeraden Grad besitzt, oder falls es keinen Knoten mit ungeradem Grad gibt, kann man einen zufälligen wählen. Ab hier läuft der Algorithmus genau gleich ab. Bei jedem Sprung wird eine Kante gelöscht, bis keine Kanten mehr übrig bleiben. Ein Problem fällt beim löschen einer Kante an, da sie bei beiden Knoten aus der Adjazenzliste gelöscht werden muss. Ein schneller Fix würde einfach die Adjazenzliste mit vector<set<int> > ersetzen. Damit büsst man aber einen Faktor von \(\mathcal{O}(\log(E))\) ein.

\(\mathcal{O}(E \cdot \log(E))\) Implementierung für Hierholzer’s Algorithmus für ungerichtete Graphen: UNTESTED

//Euler tour for undirected graphs:
list<int> eulerPath;
vector<multiset<int> > graph;
void hierholzerCycle(list<int>::iterator it) {
    while(!graph[*it].empty()) {
        int other = *graph[*it].begin();
        //delete both edges
        graph[other].erase(graph[other].find(*it));
        graph[*it].erase(graph[*it].find(other)); //only erase once!
        eulerPath.insert(it, other); //this line also increases it by one
        --it;
    }
    while(++it != eulerPath.end()) {
        if(!graph[*it].empty()) hierholzerCycle(it);
    }
}

Algorithmus von Fleury

Der Algorithmus von Fleury ist ineffizienter als der von Hierholzer und ist zudem schwieriger zu implementieren, er könnte aber etwas intuitiver sein. Fleurys Algorithmus basiert auf einem Brückenpunkt-Algorithmus (einen Algorithmus welcher Bridges (Brücken) findet). Bevor man sich mit Fleurys Algorithmus auseinandersetzt, sollte man doch einen Vortrag über Bridges (bzw. Articulation points) gehört haben.

Als Repetition: Eine Brücke ist eine Kante, welche wenn man sie entfernen würde, den Graph in zwei nicht verbundene Teilgraphen trennen würde.

Fleurys Algorithmus beginnt am gleichen Startknoten wie Hierholzers Algorithmus und die Idee ist im Prinzip gleich. Man startet eine Art DFS und löscht jede Kante die man besucht hat. Der grosse Unterschied zu Hierholzers Algorithmus ist, dass man nicht eine beliebige Kante wählt, sondern wenn möglich immer eine Kante, welche keine Brücke ist.

Der Gedanke dahinter ist, dass wenn man eine Brücke löscht, man dann keine Möglichkeit mehr hat die getrennten Kanten wieder zu besuchen. Die Brücken gelten also als eine Art Pfad um wieder zum Endpunkt gelangen zu können. Da es garantiert einen Eulerpfad (bzw. Eulerzyklus) gibt, gibt es auch garantiert einen Weg ohne den Graphen jemals in zwei Teilgraphen (mit Kanten) aufteilen zu müssen (eben dieser Eulerpfad).

Das Problem mit Fleurys Algorithmus ist, dass man naiv nach jeder entfernten Kante neu die Brückenkanten berechnen müsste, welches eine Laufzeit von \(\mathcal{O}(E^2)\) zur Konsequenz hätte.

Dies ist jedoch noch keine untere Schranke für die Laufzeit, denn das Problem ist in Wirklichkeit eine dynamische Version von bridges (Brücken). Laut Thorup (2010) gibt es einen Algorithmus der Fleurys Angehensweise in \(\mathcal{O}(E\cdot \log^3(E) \cdot \log(\log(E)))\) lösen könnte.