Zu den anderen Abschnitten:
 


Von Graphen, Genen und dem WWW


Online-Skriptum


Spaziergänge und Buslinien
 

Spaziergänger-Kauderwelsch

Das Problem, das zur Entwicklung der Graphentheorie Anlass gegeben hat - wir werden es weiter unten besprechen - handelt von einem Spaziergang. Um in gebührender Strenge über Spaziergänge sprechen zu können, benötigen wir einige Definitionen. Mancherlei Dinge kann es in einem Graphen G geben:

  • Ein Kantenzug von G ist eine Folge von Kanten (k1k2,...kr), über die man der Reihe nach spazieren kann. Formal bedeutet das: Es gibt Ecken (x0x1,...xr), so dass für alle j = 0, 1,...r die Kante kj+1 die Ecken xj und xj+1 verbindet. Wir sagen, dass x0 und xr durch den Kantenzug verbunden werden. Die Kanten müssen dabei nicht voneinander verschieden sein! Theoretisch ist auch der "leere Kantenzug" in dieser Definition enthalten. Ein Kantenzug heißt nicht-trivial, wenn er zumindest eine Kante enthält.
  • Die Länge eines Kantenzugs ist die Anzahl seiner Kanten.
  • Ein Kantenzug heißt Weg, falls alle seinen Kanten voneinander verschieden sind.
  • Ein Kantenzug heißt geschlossen, falls man beim Spaziergang wieder an den Ausgangspunkt zurückkommt, d.h. wenn es Ecken (x0x1,...xr) gemäß der obigen Definition gibt, so dass xr = x0 gilt.
  • Ein Kreis ist ein geschlossener Weg, d.h. ein geschlossener Kantenzug, dessen Kanten voneinander verschieden sind. Manchmal wollen wir den trivialen Fall eines "leeren Kreises" ausschließen. Daher nennen wir einen Kreis nicht-trivial, wenn seine Länge größer als 0 ist.
  • Ein Kreis heißt eulersch, falls jede Kante von G in ihm vorkommt, d.h. wenn er einen Rundgang durch den gesamten Graphen darstellt, in dem keine Kante mehrfach beschritten wird.
  • Eine offene eulersche Linie ist ein Weg, der kein Kreis ist, und in dem jede Kante von G vorkommt. Mit anderen Worten: Entlang einer offenen eulerschen Linie ist ein Spaziergang durch den gesamten Graphen möglich, in dem keine Kante mehrfach beschritten wird, und für den Anfangs- und End-Ecke voneinander verschieden sind.

Diese Begriffe benutzen wir, um einige wichtige Eigenschaften von Graphen formulieren:

  • Ein Graph heißt zusammenhängend, falls in ihm je zwei Ecken durch (mindestens) einen Kantenzug verbunden werden können.
  • Ist ein Graph nicht zusammenhängend, so besteht er aus Zusammenhangskomponenten, die jeweils für sich einen zusammenhängenden Graphen definieren. Ein Beispiel ist


    wobei die beiden Zusammenhangskomponenten farblich verschieden dargestellt sind.
  • Ein Graph heißt eulersch, falls er einen eulerschen Kreis enthält, d.h. falls ein Rundgang durch ihn möglich ist, der überall hin führt, wobei aber keine Kante mehrmals beschritten werden darf. Ein eulerscher Graph ist notwendigerweise zusammenhängend.

Die Graphen, die in einem Zug (ohne Absetzen und ohne Kantenwiederholungen) gezeichnet werden können, sind genau jene, die

  • entweder einen eulerschen Kreis besitzen, d.h. eulersch sind (Anfangspunkt = Endpunkt),
  • oder eine offene eulersche Linie besitzen (Anfangspunkt ¹ Endpunkt).

Damit haben wir bereits ein ansehliches Vokabular zusammengestellt, und es wird Zeit für erste Resultate.
 

Spaziergänge und die Grade der Ecken

Die beiden folgenden Sätze stellen einfache Kriterien für die Existenz ausgiebiger Spaziergänge entlang der Kanten eines Graphen dar.

Satz 1: Sei G ein zusammenhängender Graph. Dann gilt:

G ist eulersch  Û  Jede Ecke von G hat geraden Grad (d.h. q(x) ist für alle x Î E geradzahlig)

Beweis:

  • Þ
    Sei G
    ein eulerscher Graph und x eine Ecke. Beim Durchlaufen eines eulerschen Kreises komme ein Spaziergänger r mal bei x vorbei. Bei jedem Vorbeikommen durchläuft er 2 Kanten. (Entlang einer kommt er, und entlang einer anderen geht er). Da jede Kante auf seinem Weg nur einmal vorkommt, ist die Zahl der Kanten, die von x ausgehen (d.h. der Grad von x) gleich 2r, also eine gerade Zahl. (Die Beweisidee läßt sich so zusammenfassen: Es müssen gleich viele Kanten zu x hin- wie von x wegführen, daher ist ihre Anzahl gerade).
  • Ü
    Induktion nach der Anzahl m der Kanten von G:
    - Induktionsvoraussetzung: Für m = 0 ist die Aussage trivial erfüllt (keine Kanten, höchstens eine Ecke), und ebenso für m = 1 (es gibt dann 2 Ecken, die beide von ungeradem Grad sind, G ist nicht eulersch). Falls m = 2 ist, so muss die Zahl der Ecken ebenfalls 2 sein. Es gibt (bis auf Isomorphie) nur einen solchen Graphen, und zwar den nebenstehend abgebildeten, und dieser ist eulersch.
    - Induktionsschluss: Wir nehmen an, die Aussage gelte für alle Graphen mit weniger als m Kanten und betrachten einen zusammenhängenden Graphen G mit m Kanten, dessen Ecken alle geraden Grad haben. Zunächst zeigen wir, dass es in diesem Graphen (zumindest) einen nicht-trivialen Kreis gibt. Um ihn zu konstruieren, geht man von einer beliebigen Ecke aus und wandert eine beliebige Kante entlang. (Das ist immer möglich, da G zusammenhängend ist und es daher keine isolierten Ecken gibt). Bei jeder weiteren Ecke, zu der man kommt, tritt einer der beiden Fälle auf:
    1. Es handelt sich nicht um die Ecke, von der man ausgegangen ist. Die Anzahl der Kanten, die von ihr ausgehen, ist gerade. Auf einer der Kanten ist man selbst gerade gekommen. Möglicherweise hat man eine (gerade) Anzahl von Kanten bereits durchwandert. Es gibt also mindestens eine Kante, die noch nicht beschritten wurde, und eine solche wählt man zum Weitergehen aus.
    2. Es handelt sich um die Ecke, von der man ausgegangen ist, d.h. der Kreis hat sich geschlossen.
    Klarerweise tritt nach endlich vielen Schritten der zweite Fall ein, womit die Existenz eines nicht-trivialen Kreises in G bewiesen ist.
    Da nun jeder Kreis eine Länge besitzt (die Zahl seiner Kanten) und kein Kreis länger als m sein kann, gibt es einen Kreis A mit maximaler Länge. Entfernen wir die Kanten von A, so entsteht ein Graph B, der weniger als m Kanten hat, und dessen Ecken alle geraden Grad haben. Dieser neue Graph kann zusammenhängend sein oder in Zusammenhangskomponenten zerfallen, die ebenfalls diese Eigenschaften haben. Besäße nun B auch nur eine einzige Kante, so gäbe es laut Induktionsvoraussetzung einen nicht-trivialen eulerschen Kreis von B oder einer Zusammenhangskomponente von B, aus dem sich, durch Vereinigung mit A, ein Kreis konstruieren ließe, der länger als A ist. Da das aber nicht möglich ist (A ist ja bereits von maximaler Länge), besitzt B
    überhaupt keine Kanten (B ist der triviale Graph). Daraus folgt, dass alle Kanten von G in A vorkommen, d.h. dass A ein eulerscher Kreis ist. Dessen Existenz impliziert per Definition, dass G eulersch ist.

Satz 2: Sei G ein zusammenhängender Graph. Dann gilt:

G besitzt eine offene eulersche Linie  Û  G besitzt genau zwei Ecken ungeraden Grades

Beweis:

  • Þ
    Wir fügen eine zusätzliche Hilfskante ein, die Anfangs- und End-Ecke der offenen eulerschen Linie verbindet. Da der so entstandene größere Graph einen eulerschen Kreis besitzt, hat er gemäß Satz 1 nur Ecken geraden Grades. Wird die Hilfskante wieder entfernt, so erweist triviales Abzählen, dass die Anfangs- und End-Ecke der offenen eulerschen Ecke die einzigen Ecken von G mit ungeradem Grad sind.
  • Ü
    Die beiden Ecken ungeraden Grades werden durch eine Hilkskante verbunden. Der so entstandere größere Graph ist zusammenhängend und besitzt nur Ecken geraden Grades, besitzt daher gemäß Satz 1 einen eulerschen Kreis. In diesem kommt per Definition auch die Hilfskante vor. Wird sie wieder entfernt, so ergibt sich eine offene eulersche Linie.

Mit diesen Resultaten ausgerüstet, wenden wir uns der Problemstellung zu, mit der die Graphentheorie ihren Anfang nahm.
 

Das Königsberger Brückenproblem

Im Jahr 1736 wurde Leonhard Euler gefragt, ob es möglich ist, einen Spaziergang durch die Stadt Königsberg (heute Kaliningrad) zu unternehmen, so dass jede der sieben Brücken über die Pregel genau einmal begangen wird. Hier ein schematischer Plan der Stadt im 18. Jahrhundert:

Euler nahm die Frage zum Anlass, die Graphentheorie zu begründen. Formulieren wir das Problem in graphentheoretischen Begriffen:

Jedem Stadtviertel wird
eine Ecke zugeordnet.

Jeder Brücke wird eine
Kante, die zwei Ecken
verbindet, zugeordnet.
Der resultierende Graph.

Nach einer kleinen Verschönerung sieht der Graph für das Königsberger Brückenproblem so aus:

Der gewünschte Spaziergang erfordert die Existenz eines eulerschen Kreises oder einer offenen eulerschen Linie. Dieses Problem können wir leicht lösen: Alle vier Ecken des Graphen besitzen ungeraden Grad. Die obigen Sätze 1 und 2 sagen uns daher unmittelbar: Der Graph ist weder eulersch, noch besitzt er eine offene eulersche Linie. Der gewünschte Spaziergang ist nicht möglich.

Weitere Ressourcen zu diesem Thema:

Denksport mit Hintergrund

Übungsaufgabe: Welche dieser Figuren kann man in einem Zug zeichen, ohne dabei abzusetzen und ohne eine Linie mehrfach zu durchlaufen?

Begründen Sie Ihre Antworten graphentheoretisch! Tipp: Denken Sie sich die Figuren zu Graphen erweitert, schreiben Sie zu jeder Ecke ihren Grad und wenden Sie die beiden obigen Sätze an!

Zusatzfragen:

  • Welche der Graphen besitzen einen eulerschen Kreis, welche eine offene eulersche Linie? Wie verlaufen diese (Beispiele)?
  • Stellen Sie eine Regel auf: Wo muss man zu zeichnen beginnen, wenn der Graph eine offene eulersche Linie besitzt? (Tipp: Die Antwort steckt im Beweis von Satz 2!)
     
Linienführung

Um eine praxisbezogene Anwendung der Spaziergängertheorie zu studieren, stellen wir uns vor, eine neu zu schaffende Buslinie soll in jedem Fall folgende Straßen eines Stadtviertels befahren:

Wie soll die Linienführung genau aussehen? Wir analysieren zunächst den aus den roten Linien bestehenden Graphen. Da er vier Ecken ungeraden Grades besitzt, ist er nicht eulersch, und es existiert auch keine offene eulersche Linie. Eine Linienführung, die keine Straße zweimal benutzt, ist daher aufgrund der Sätze 1 und 2 nicht möglich. Wir können aber fragen: Wie kann die mehrfach zu befahrende Strecke minimiert werden? Dazu lassen wir die beiden Straßen, die der An- und Abfahrt dienen, zunächst außer Acht und markieren alle Ecken ungeraden Grades. Jetzt sind es insgesamt sechs:

Die markierten Ecken, die an den Anschlussstellen zur An- und Abfahrt liegen, kommen uns gelegen: Wird der Graph in sinnvoller Weise modifiziert, so können hier die beiden Enden einer offenen eulersche Linie liegen. Um den verbleibenden vier Ecken geraden Grad zu geben, können wir je zwei von ihnen durch neu hinzuzufügende Kanten (die dann den doppelt zu befahrenden Straßenstücken entsprechen) miteinander verbinden. Bereits ohne Rechnung ist aus obigem Plan klar, dass es zwei optimale Lösungen gibt. Wenn Sie die Maus über das Bild führen, wird eine der beiden (in blauer Farbe) eingeblendet, wenn Sie auf das Bild klicken, sehen Sie die andere. Beide modifizierten Graphen besitzen eine eulersche Linie ist, die genau an den gewünschten Stellen beginnt und endet, womit der Großteil des Problems gelöst ist. Was bleibt, ist die Auswahl einer der beiden modifizierten Graphen (vom gestellten Problem her sind beide gleichwertig) und das Auffinden einer offenen eulersche Linie. Das kann durch Probieren geschehen oder, systematischer, unter Zuhilfenahme der Argumente, mit denen die beiden obigen Sätze bewiesen wurden. (Übungsaufgabe: Finden Sie eine offene eulersche Linie, d.h. eine mögliche Linienführung!) Praxisnäher ist es allerdings, mehrere (in diesem einfachen Fall: alle) Lösungen zu konstruieren und die geeignetste nach anderen Kriterien zu wählen. (Man könnte den Auftraggeber auch darauf hinweisen, dass sich die Gesamtstrecke zusätzlich ein wenig verkürzen würde, wenn - trotz der Vorgaben - auf die kurze Strecke zwischen den zwei nächstliegenden markierten Ecken verzichtet werden könnte).

Das Schöne an dieser Herangehensweise besteht darin, dass der Graph zunächst in systematischer Weise so verändert wird, dass die Existenz einer sinnvollen Lösung sichergestellt ist. Wird versucht, das Problem von Beginn an durch Probieren zu lösen, kostet das nicht nur mehr Zeit und Anstrengung, sondern führt unter Umständen nur zu einer Linienführung, in der die mehrfach zu befahrende Strecke nicht minimal ist.

Beispiele dieses Typs sind keine reinen Erfindungen, sondern treten bei der Optimierung von Verkehrsystemen in Städten auf. Tatsächlich sind die gestellten Aufgaben in der Regel ziemlich komplex und werden immer häufiger unter Hinzuziehung von MathematikerInnen (und unter erheblichem Computereinsatz) gelöst.


¬   Graphen Übersicht Von Bäumen, Wurzeln und        
Blättern, Tieren und Menschen   ®