Das Problem geht auf das 1736 von Leonhard Euler gelöste Königsberger Brückenproblem zurück. Das Problem gilt auch für gerichtete Graphen und Graphen mit Mehrfachkanten.

Table of contents

1 Beispiele 2 Eigenschaften 3 Algorithmus

Beispiele

Das Königsberger Brückenproblem lässt sich in folgendem Graphen ausdrücken:

Die roten Punkte (Knoten), sind die jeweiligen Stadtteile bzw. Standpunkte. Die blauen Linien (Kanten) sind die Brücken. Durch Probieren wird man herausfinden, dass es nicht möglich ist, alle Stadtteile hintereinander zu besuchen und jede Brücke nur ein einziges Mal zu benutzen. Es gibt also keinen Eulerweg und demzufolge auch keinen Eulerkreis. Warum ist das so?

Euler hat die folgende Gesetzmäßigkeit entdeckt: In einem Graph gibt es mindestens einen Eulerweg, wenn dieser maximal 2 Knoten mit ungeradem Grad besitzt (wenn also an mehr als zwei Knoten eine ungerade Anzahl Kanten angeschlossen sind). Beim Königsberger Brückengraphen gibt es drei Knoten mit ungeradem Grad (die Zahlen neben den Knoten geben hier deren Grad an). Deshalb ist der Stadtrundgang mit dem nur einmaligen Benutzen jeder Brücke unmöglich.

Das beliebte Kinderrätsel "Das-ist-das-Haus-vom-Nikolaus" hingegen enthält einen Eulerweg, aber keinen Eulerkreis, da sein Graph Knoten vom Grad 3 enthält.

Ein Eulerweg ist z.B. 1-2-4-3-1-4-5-3-2.

Ein Quadrat mit Diagonalen enthält keinen Eulerweg, da alle seine Knoten den Grad 3 haben. (Im Bild sind das nur die Punkte 1,2,3,4 mit den verbindenden Kanten.)

Bei folgendem Graphen ist sowohl Eulerkreis als auch Eulerweg möglich:

Egal, an welchem Knoten man beginnt: Der "Rundgang" ist immer möglich.

Eigenschaften

Für ungerichtete Graphen sind folgende Aussagen äquivalent:

1. G ist eulersch,
2. G ist zusammenhängend und jeder Knoten hat geraden Grad (Graphentheorie).
3. G ist zusammenhängend und die Kantenmenge von G ist die Vereinigung aller Kanten von paarweise disjunkten Kreisen.

1. G ist eulersch,
2. G ist stark zusammenhängend und für jedem Knoten sind Eingangsgrad und Ausgangsgrad äquivalent.
3. G ist stark zusammenhängend und die Kantenmenge von G ist die Vereinigung aller Kanten von paarweise disjunkten gerichteten Kreisen.