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 Endpunkt 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 Ecken 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, jede Ecke mit jeder anderen verbunden), so muss man aufpassen: Beim Viereck (Sechseck, Achteck usw.) wird der Eckengrad dadurch ungerade, diese Graphen sind also nicht eulersch. Alle vollständigen Vielecke mit ungerader Eckenzahl sind jedoch eulerscht, weil jede Ecke mit jeder anderen Ecke verbunden ist, also mit einer geraden Zahl. Damit bleibt der Grad der Ecken gerade.

Haus des Nikolaus

Das „Haus des Nikolaus“ ist ein bekannter Graph, der sich ohne abzusetzen zeichnen lässt - aber dieser Graph ist nicht eulerscht, da Start- und Zielpunkt nicht identisch sind. Solch einen Linienzug nennt man dann eine Tour.

Touren sind in jedem Graphen vorhanden, der neben Ecken mit geradem Grad genau zwei Ecken mit ungeradem Grad hat, diese sind damit als Start- bzw. Zielpunkt festgelegt.

Begründung: Die Startecke hat zunächst mindestens den Grad 1. Bei jedem Besuch einer Ecke (also hinkommen und weggehen) erhöht sich der Eckengrad um zwei. Wenn ein weiteres Mal eine Ecke besucht wird, bleibt man dort irgendwann stecken, wenn der Grad ungerade ist.

Hat ein Graph mehr als zwei ungerade Ecken, so kann der Graph in verschiedene Touren zerfallen, wenn die Anzahl der ungeraden Ecken 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 Ecken und die Wege über die Brücken zu den Kanten:

ABCD
A0201
B2021
C0201
D1110

Aus der Tabelle wird deutlich, dass der Grad jeder Ecke 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)

1) Man könnte aber zwei einzelne Touren so planen, dass jede Brücke insgesamt nur einmal betreten wird, wenn man den Gang von einem Zielpunkt zum nächsten Startpunkt nicht mitzählt.

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:

  1. Überprüfen, dass alle Ecken gerade sind (sonst nicht eulersch)
  2. Graphen in geschlossene Touren einteilen (bei komplexeren Graphen sind Farben hilfreich)
  3. Start- / Zielpunkt wählen (beliebig)
  4. Immer dann, wenn es möglich ist, auf eine Tour wechseln, auf der man noch nicht war.
  5. 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).
mint/graphen/euler.txt · Zuletzt geändert: 2012/01/08 17:48 von ahrens
CC Attribution-Noncommercial-Share Alike 3.0 Unported
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0