Inhaltsverzeichnis
Eulersche Graphen
Am Anfang stand, der Legende nach, das Königsberger Brückenproblem: „Ist es möglich, in einem Spaziergang alle Brücken Königsbergs genau einmal zu betreten und kommt man dann vielleicht auch wieder am Ausgangspunkt an?“ Leonhard Euler hat die Antwort 1736 veröffentlicht und damit die Graphentheorie begründet.
Definition
Ein eulerscher Graph enthält einen Linienzug, der jede Kante genau einmal verwendet und dessen Start- und Endknoten identisch sind. Solch einen Linienzug nennt man dann eine eulersche Tour.
Eulersche Graphen lassen sich also ohne abzusetzen vollständig zeichnen.
Damit das gelingen kann, darf der Graph nur Knoten haben, deren Grad gerade ist.
Beispiele
Jedes Dreieck, Viereck, Fünfeck usw. ist damit ein eulerscher Graph.
Zeichnet man zusätzlich zu den Seiten auch die Diagonalen (vollständige Vielecke, jeder Knoten mit jeder anderen verbunden), so muss man aufpassen: Beim Viereck (Sechseck, Achteck usw.) wird der Knotengrad dadurch ungerade, diese Graphen sind also nicht eulersch. Alle vollständigen Vielecke mit ungerader Eckenzahl sind jedoch eulersch, weil jeder Knoten mit jedem anderen Knoten verbunden ist, also mit einer geraden Zahl. Damit bleibt der Grad der Knoten gerade.
Haus des Nikolaus
Das „Haus des Nikolaus“ ist ein bekannter Graph, der sich ohne abzusetzen zeichnen lässt - aber dieser Graph ist nicht eulersch, da Start- und Zielknoten nicht identisch sind. Solch einen Linienzug nennt man dann eine Tour.
Touren sind in jedem Graphen vorhanden, der neben Knoten mit geradem Grad genau zwei Knoten mit ungeradem Grad hat, diese sind damit als Start- bzw. Zielknoten festgelegt.
Begründung: Der Startknoten hat zunächst mindestens den Grad 1. Bei jedem Besuch eines Knoten (also hinkommen und weggehen) erhöht sich der Knotengrad um zwei. Wenn ein weiteres Mal ein Knoten besucht wird, bleibt man dort irgendwann stecken, wenn der Grad ungerade ist.
Hat ein Graph mehr als zwei ungerade Knoten, so kann der Graph in verschiedene Touren zerfallen, wenn die Anzahl der ungeraden Knoten gerade ist.
Königsberger Brückenproblem
Der Fluss Pregel, über den die Brücken gehen, umfließt die Innenstadt von Königsberg und spaltet sich in insgesamt drei Arme. Dadurch wird die Stadt in vier Stadtteile geteilt (A im Norden, B in der Mitte, C im Süden und D im Osten). Über den Fluss führen sieben Brücken, die die vier Stadtteile verbinden. Stellt man sich die Stadt als Graph vor, so werden die Stadtteile zu den Knoten und die Wege über die Brücken zu den Kanten:
|
Aus der Tabelle wird deutlich, dass der Grad jedes Knoten ungerade ist: A(3), B(5), C(3), D(3). Damit ist der gewünschte Spaziergang, der über jede Brücke nur einmal führt, nicht möglich - außer, es wird noch mindestens eine weitere Brücke gebaut oder eine existierende Brücke wird abgerissen (für eine Tour mit unterschiedlichem Start- und Zielpunkt).1) |
Schlingen und Mehrfachkanten
Ist ein Graph eulersch, so kann man beliebig viele Schlingen hinzufügen. Da eine Schlinge den Grad einer Ecke um zwei erhöht, bleibt der Grad der Ecke gerade und der Graph damit eulersch.
Will man zusätzliche Kanten hinzufügen, so dass Mehrfachkanten entstehen, so muss man mehr aufpassen, wenn der Graph eulersch bleiben soll. Denn da eine Kante den Grad der beiden verbundenen Ecken jeweils um eins erhöht, würde eine Ecke mit geradem Grad danach einen ungeraden Grad haben. Wenn man jedoch an den Ecken eine weitere Kante zufügt, ist der Graph wieder eulersch. Es müssen an den Ecken eines eulerschen Graphen also immer gerade Anzahlen von Kanten ergänzt werden, wenn der Graph eulersch bleiben soll.
Eulersche Touren finden
C.F.B. Hierholzer hat eine Anleitung (einen Algorithmus) für das Auffinden von eulerschen Touren in eulerschen Graphen entwickelt (Zwiebelschalenalgorithmus):
- Überprüfen, dass alle Ecken gerade sind (sonst nicht eulersch)
- Graphen in geschlossene Touren (Kreise) einteilen (bei komplexeren Graphen sind Farben hilfreich)
- Start- / Zielpunkt wählen (beliebig)
- Immer dann, wenn es möglich ist, auf eine Tour wechseln, auf der man noch nicht war.
- Stößt man in einer Ecke nur auf Touren, die man schon verwendet hat, so bleibt man auf der aktuellen Tour bis zum Ende und wechselt erst dann auf eine andere Tour (oder ist im Zielpunkt angekommen).
