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 (k1, k2,...kr),
über die man der Reihe nach spazieren kann. Formal bedeutet das:
Es gibt Ecken (x0, x1,...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 (x0, x1,...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:
- 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.
- 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:
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!)
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.
|