Hausarbeit zur ersten Staatsprüfung
für das Lehramt an der Grund- und Mittelstufe
im Prüfungsfach Mathematik
Netzwerke
- ein spezielles Gebiet der Graphentheorie -
Sandra Riedemann
Universität Hamburg
Fachbereich Mathematik
Abgabedatum: 19.12.2007
Inhaltsverzeichnis
Einleitung 2
1 Graphentheoretische Grundlagen 3
1.1 Vollständige Graphen 3
1.2 Bipartite Graphen 4
1.3 Kantenzug 5
1.4 Weg 6
1.5 Pfad 6
1.6 Kreis
6
1.7 Grad einer Ecke 7
1.8 Hamiltongraphen 7
1.9 Bäume 8
2
Gerichtete Graphen 9
2.1 Einführung 9
2.2 Turniere 13
3
Netzwerke 23
3.1 Einführung 23
3.2 Flüsse und Schnitte 25
3.3 Der Algorithmus von Ford und Fulkerson 35
4
Trennende Mengen 41
4.1 Zerlegungsecken & Eckenzusammenhangszahl 41
4.2 Brücke & Kantenzusammenhangszahl 44
4.3 Trennende Ecken- und Kantenmenge 48
4.4 Der Satz von Menger 50
5
Anwendungsbeispiele 58
5.1 Major League Baseball 58
5.2 Flugplanerstellung 66
Schlussbemerkung 74
Literaturverzeichnis 75
1
Einleitung
Einleitung
Die vorliegende Arbeit soll einen Einblick in die Graphentheorie geben.
Dabei wird insbesondere auf Netzwerke als graphische Darstellungsform
eingegangen. Bevor aber ein Blick auf die Netzwerke geworfen werden
kann, sollen in Kapitel 1 einige Grundbegriffe der Graphentheorie erläutert
werden. Diese Grundbegriffe wurden im Jahr 1736 eingeführt als Leonard
Euler sein ,,Königsberger Brückenproblem" veröffentlichte in dem er
versucht, einen Rundweg durch die Stadt Königsberg zu finden, ohne
dabei eine der sieben Brücken zweimal passieren zu müssen. Am Ende
de Rundganges sollte sich der Spaziergänger am Ausgangspunkt
wiederfinden. Euler zeigt durch die Übertragung des Königsberger
Stadtplanes in einen ungerichteten Graphen, dass es einen solchen Weg
nicht gibt.
Die von Euler eingeführten Begriffe lassen sich aber auch auf gerichtete
Graphen übertragen, die in Kapitel 2 behandelt werden. Weiterhin soll in
diesem Kapitel der Begriff des Turniers erläutert werden.
Im 3. Kapitel werden schließlich die Netzwerke thematisiert. Der Leser
wird mit Begriffen wie ,,Flüsse" und ,,Schnitte" vertraut gemacht, um den
Maximum-Fluss-Minimum-Schnitt-Satz von Ford und Fulkerson beweisen
zu können. In einem ausführlichen Beispiel ist dann der Algorithmus von
Ford und Fulkerson dargestellt.
Kapitel 4 befasst sich mit ,,trennenden Mengen". Der Schwerpunkt dieses
Kapitels liegt auf dem Satz von Menger und den daraus resultierenden
Folgerungen, die mit dem Maximum-Fluss-Minimum-Schnitt-Satz des
vorherigen Kapitels bewiesen werden können.
Zum Schluss werden im 5. Kapitel die bisher erzielten Ergebnisse auf zwei
Bespiele angewendet. In beiden Beispielen steht der Maximum-Fluss-
Minimum-Schnitt-Satz im Vordergrund.
2
Graphentheoretische Grundlagen
Kapitel 1
Graphentheoretische Grundlagen
Die Graphentheorie hat sich seit dem 18. Jahrhundert zu einem zentralen
Thema der diskreten Mathematik entwickelt. Graphen sind besonders gut
zur Modellierung von Alltagsproblemen geeignet. So können zum Beispiel
chemische Moleküle mit Hilfe von Strukturformeln dargestellt und
Verkehrsflüsse in Straßennetzen simuliert werden.
In diesem Kapitel werden nur ungerichtete Graphen behandelt, während
das folgende 2. Kapitel sich mit gerichteten Graphen auseinandersetzt.
1.1 Vollständige Graphen
Ein Graph besteht aus Ecken und Kanten. Dabei verbindet jede Kante
genau zwei Ecken. Folglich können zwei Ecken e
0
und e
1
entweder durch
keine, genau eine oder mehrere Kanten k
s
miteinander verbunden sein.
Zum Beispiel bedeutet k
1
= {e
0
,e
1
}, dass die Kante k
1
die Ecken e
0
und e
1
verbindet.
Graphen werden im folgenden mit G bezeichnet. Soll die Eckenmenge
E = { e
0
, e
1
,... , e
s
} oder die Kantenmenge K = { k
1
, k
2
, ...,k
s
} hervorgehoben
werden, so wird die Schreibweise G(E,K) benutzt.
Ein Graph heißt vollständig, wenn jede Ecke mit jeder anderen Ecke durch
genau eine Kante verbunden ist. Der vollständige Graph mit n Ecken wird
mit K
n
bezeichnet. Es folgen Beispiele für die vollständigen Graphen
K
1
, ..., K
5
:
K
1
K
2
K
3
K
4
K
5
Abb. 1.1 Die vollständigen Graphen K
1
bis K
5
3
Graphentheoretische Grundlagen
Der vollständige Graph K
n
hat immer 1
2
nn1 Kanten. Da eine Kante
immer genau zwei Ecken verbindet und jede Ecke aufgrund der
Vollständigkeit mit allen anderen n1 Ecken verbunden ist, gibt es für
jede Ecke genau n1 Kanten. Bei n Ecken gibt es dann nn1
Kanten. Da e
0
,e
1
} = {e
1
,e
0
} ist, halbiert sich das Produkt und es folgt
1
2
nn1 .
1.2 Bipartite Graphen
Ein Graph heißt bipartit, wenn seine Ecken in zwei Klassen eingeteilt
werden können, so dass jede Kante stets eine Ecke der einen Klasse mit
einer Ecke der anderen Klasse verbindet. Die Eckenmenge E setzt sich
somit aus den Eckenmengen E
1
und E
2
zusammen: E = E
1
E
2
. Dabei gilt
E
1
E
2
und E
1
E
2
=
, das heißt die beiden Eckenklasse haben
keine gemeinsamen Ecken. Im folgenden Beispiel sind die schwarzen
Ecken E
1
und die grauen Ecken E
2
zu zuordnen.
Abb. 1.2.1 Bipartite Graphen
Ein bipartiter Graph heißt vollständig, wenn jede Ecke aus E
1
mit jeder
anderen Ecke aus E
2
durch genau eine Kante verbunden ist. Wenn E
1
genau m und E
2
genau n Ecken hat, wird der vollständig bipartite Graph
auch mit K
m,n
bezeichnet.
K
2,2
K
3,3
K
2,3
Abb. 1.2.2 Die vollständig bipartiten Graphen K
2,2
, K
3,3
und K
2,3
4
Graphentheoretische Grundlagen
1.3 Kantenzug
Den Begriffen in den Kapitel 1.3 bis 1.5 liegen zusammenhängende
Graphen zugrunde. In einem zusammenhängenden Graph ist jede Ecke
über eine Folge von Kanten erreichbar. Es gibt also keine isolierten Ecken.
Ein grundlegender Begriff der Graphentheorie ist der des Kantenzuges.
Ein Kantenzug ist eine Folge von aneinander gefügten Kanten, so dass
die Kanten k
1
,
k
2
, ..., k
s
die Ecken e
0
, e
1
, ..., e
s
auf folgende Weise
verbinden:
k
1
verbindet die Ecken e
0
und e
1
,
k
2
verbindet die Ecken e
1
und e
2
,
...,
k
s
verbindet die Ecken e
s-1
und e
s
.
Anders ausgedrückt: k
1
= {e
0
,e
1
}, k
2
= {e
1
, e
2
}, ..., k
s
= { e
s-1
, e
s
},
mit k
i
und e
i
E.
Zu beachten ist, dass weder die Ecken noch die Kanten verschieden sein
müssen. Der Graph muss jedoch zusammenhängend sein.
e
1
e
2
e
4
e
0
e
3
Abb. 1.3.1 Ein Kantenzug von e
0
nach e
4
Ein Kantenzug heißt geschlossen, wenn e
0
= e
s
e
1
e
2
e
4
e
3
e
0
Abb. 1.3.1 Ein geschlossener Kantenzug von e
0
nach e
4
5
Graphentheoretische Grundlagen
1.4 Weg
Ein Kantenzug wird genau dann als Weg bezeichnet, wenn alle Kanten
verschieden sind. Die Ecken des Graphen dürfen weiterhin mehrfach
genutzt werden. Das folgende Beispiel soll den Sachverhalt noch einmal
verdeutlichen. Es existiert ein Weg von e
0
nach
e
4
, so dass die Ecke e
1
zweimal genutzt wird.
e
2
e
0
e
1
e
3
e
4
Abb. 1.4 Ein Weg von e
0
nach e
4
1
Der Weg in Abb. 1.4 verläuft von e
0
über die Ecken e
1
, e
2
und e
3
, dann
erneut über e
1
zur Endecke e
4
.
1.5 Pfad
Ein Pfad ist ein spezieller Weg. Zusätzlich gilt bei einem Pfad, dass nun
auch die Ecken nicht mehrfach genutzt werden dürfen. Jede Kante und
Ecke darf folglich nur einmal genutzt werden. Der Graph in Abbildung 2.4
enthält zum Beispiel den Pfad von e
0
über e
1
hin
zur Endecke e
4
.
1.6 Kreis
Ein Kreis ist ein geschlossener Pfad. Da einem geschlossenem Pfad ein
geschlossener Kantenzug zugrunde liegt, gilt auch hier e
0
= e
s
. Die Länge
eines Kreises wird durch die Anzahl der Ecken bestimmt. Es gilt
E= n.
Ein Kreis der Länge n wird auch kurz als C
n
geschrieben. In Abb. 2.5 ist
links der Kreis C
4
zusehen. Der rechte Graph ist zwar kein Kreis, besteht
aber aus zwei Kreisen der Länge 3.
1 Diese Definition ist von BEUTELSPACHER (2004) übernommen. Bezüglich anderer
Literatur kann es zu Abweichungen kommen. Gleiches gilt für die Definition eines
Pfades.
6
Graphentheoretische Grundlagen
C
4
C
3
C
3
Abb. 1.6 Kreise der Länge 4 und der Länge 3
1.7 Grad einer Ecke
Sei a
E, dann heißt d(a):= {k Ka K}Grad der Ecke a. Als Grad
einer Ecke a wird also die Anzahl der Kanten bezeichnet, die durch a
gehen.
Gilt d(a) = 0 handelt es sich um eine isolierte Ecke und somit um einen
nicht zusammenhängenden Graphen.
In einem vollständigem Graphen K
n
gilt füt jede Ecke d(a) = n1 , da
jede Ecke mit jeder anderen der n1 Ecken durch genau eine Kante
verbunden ist.
e
2
e
0
e
1
e
3
e
4
e
5
Abb. 1.7 Ecken mit den Graden 0, 1, 2 und 4
Für die Ecken in Abbildung 1.7 gilt:
d(e
5
) = 0, d(e
0
) = d(e
4
) = 1, d(e
2
) = d(e
3
) = 2 und d(e
1
) = 4.
1.8 Hamiltongraphen
Die Bezeichnung hamiltonsch ist auf den irischen Mathematiker und
Physiker Sir William Rowan Hamilton zurückzuführen (1805 1865), der
1859 das Spiel ,,around the world" erfand. Die Punkte eines Dodekaeders
stellten die Städte dar. Die Aufgabe des Spiels bestand nun darin, entlang
der Kanten des Dodekaeders eine Rundreise zu unternehmen, bei der
jede Stadt genau einmal besucht wird. Dabei sollte die Reise genau in der
7
Graphentheoretische Grundlagen
Stadt enden, in der sie zuvor begonnen hatte.
Die roten Kanten in der unten stehende Abbildung zeigen eine solche
mögliche Rundreise.
Abb. 1.8 Ein Hamiltonkreis in dem Graphen des Dodekaeders
Ziel des Spiels war es also einen Kreis zu finden, der durch jede Ecke des
Graphen geht. Dabei müssen aber nicht alle Kanten genutzt werden.
Kreise mit dieser Eigenschaft werden als Hamiltonkreise bezeichnet.
Ein Hamiltonpfad in einem Graphen G ist demzufolge ein Pfad, der jede
Ecke von G enthält.
Die Definition eines Hamiltonweges ist analog.
1.9 Bäume
Ein Baum ist ein zusammenhängender Graph, der keinen Kreis C
n
(mit n > 0) enthält. Abb. 1.9 zeigt alle Bäume mit fünf Knoten.
Abb. 1.9 Alle Bäume mit fünf Knoten
8
Gerichtete Graphen
Kapitel 2
Gerichtete Graphen
2.1 Einführung
Die im vorherigen Kapitel behandelten graphentheoretischen Grundlagen
lassen sich auch auf gerichtete Graphen übertragen. Bisher konnten mit
Hilfe von ungerichteten Graphen nur symmetrische Beziehungen
dargestellt werden. Mit Hilfe gerichteter Graphen ist es nun auch
möglich unsymmetrische, nur in eine Richtung weisende Beziehungen zu
modellieren. Dieser Sachverhalt lässt sich gut an Hand eines
Sozigrammes erläutern. Ein Soziogramm ist eine graphische Darstellung
der Beziehungen in einer Gruppe, etwa in einer Schulklasse oder einem
Unternehmen. Ausgehend von den ermittelten Daten, werden die
Beziehungen in der Darstellung durch Pfeile symbolisiert. So können
Daten in einer Schulklasse zum Beispiel mit folgender Frage ermittelt
werden: ,,Neben wem möchtest du gerne sitzen? Du darfst bis zu drei
Mitschüler benennen." Wenn Schüler A neben Schüler B sitzen möchte,
zeigt in der graphischen Darstellung ein Pfeil von A nach B. Auf diese
Weise entsteht ein anschaulicher Überblick. Beispielsweise werden
Außenseiter sofort erkennbar, da auf sie nur wenige oder gar keine Pfeile
gerichtet sind. Im Gegensatz zu den beliebtesten Schülern, auf die viele
Pfeile gerichtet sind. Im unten stehenden Soziogramm wurde die Umfrage
in der Schulklasse mit der Frage ,,Neben wem möchtest du auf gar keinem
Fall sitzen?" erweitert. Abneigungen werden mit roten, Zuneigungen mit
schwarzen Pfeilen dargestellt. Durch die roten Pfeile werden Außenseiter
noch stärker hervorgehoben und sind gleich auf den ersten Blick zu
erkennen.
9
Gerichtete Graphen
Abb. 2.1 Ein Soziogramm, das Zuneigung und Abneigung darstellt
2
Um eine bessere Übersicht zu ermöglichen, ist in dem Soziogramm nur
eine Teil der Schulklasse dargestellt. Schon auf den ersten Blick wird
Schüler B als Außenseiter entlarvt. Hingegen ist Schüler A sehr beliebt
und Schüler F nimmt eher eine Randposition ein.
Das Soziogramm ist nur eines von vielen Anwendungsbeispielen.
Gerichtete Graphen sind auch in der Logistik von großer Bedeutung. Eine
zentrale Frage lautet hier: ,,Wie kann die größtmögliche Menge an Gütern
auf dem schnellsten Weg von A nach B transportiert werden?" Diese und
weitere Aspekte werden in Kapitel 4 an gegebener Stelle näher erläutert.
Wie bereits erwähnt, können mit Hilfe von gerichteten Graphen nun auch
unsymmetrische Beziehungen dargestellt werden. Die Aussage des
obigen Soziogrammes kann auch als Menge von geordneten Paaren
dargestellt werden. Bezüglich der Zuneigungen ergibt sich folgende
Menge:
{(A,C), (A,D), (B,A), (C,A), (C,D), (C,E), (D,A), (D,E), (E,A), (E,D), (F,E)}
2 http://de.wikipedia.org/wiki/Soziogramm
10
Gerichtete Graphen
Die Ordnung innerhalb der Paare ist wichtig, denn (A, B) ist verschieden
von (B,A), vorausgesetzt A und B sind nicht identisch. Diese Ordnung
wurde im Soziogramm durch die Richtung der Pfeilspitzen dargestellt.
Deshalb wird in diesem Zusammenhang von gerichteten Graphen
gesprochen. Bisher wurden das Eckenpaar einer ungerichteten Kante
immer so geschrieben: {e
s-1
, e
s
}. Da die Ordnung bei gerichteten Kanten
aber eine Rolle spielt, wird das Eckenpaar einer solchen Kante wie folgt
geschrieben: (e
s-1
, e
s
).
Ein gerichteter Graph
GE ,
K besteht ebenso wie ein ungerichteter
Graph aus zwei endlichen Mengen. Der Eckenmenge E und der
Kantenmenge K. Dabei gilt stets E
. Die Kantenmenge
K kann leer
sein, muss sie aber nicht. Wenn gilt
K = , dann handelt es sich um
einen nicht zusammenhängenden Graphen.
e
1
e
0
e
2
e
3
Abb. 2.2 Ein einfach gerichteter Graph
Abb. 2.2 stellt den gerichteten Graphen
G mit der Eckenmenge
E = {e
0
,e
1
, e
2
, e
3
} und der Kantenmenge
K = {
k
1,
k
2,
k
3,
k
4,
k
5,
k
6
}
dar,
wobei
k
1
die Ecken e
0
und e
1
verbindet und somit dem geordneten Paar (e
0
,e
1
)
zugewiesen ist,
k
2
die Ecken e
1
und e
3
verbindet und somit dem geordneten Paar (e
1
,e
3
)
zugewiesen ist,
k
3
die Ecken e
2
und e
1
verbindet und somit dem geordneten Paar (e
2
,e
1
)
zugewiesen ist,
k
4
die Ecken e
3
und e
1
verbindet und somit dem geordneten Paar (e
3
,e
1
)
zugewiesen ist,
11
Gerichtete Graphen
k
5
die Ecken e
3
und e
2
verbindet und somit dem geordneten Paar (e
3
,e
2
)
zugewiesen ist und
k
6
die Ecken e
3
und e
0
verbindet und somit dem geordneten Paar (e
3
,e
0
)
zugewiesen ist.
Viele Begriffe, die bereits in Kapitel 1 für ungerichtete Graphen eingeführt
wurden, lassen sich auf gerichtete Graphen übertragen. So ist ein
gerichteter Kantenzug eines gerichteten Graphen
G eine Folge von
aneinander gefügten Kanten, so dass die Kanten
k
1,
k
2,
... ,
k
s
die Ecken
e
0
, e
1
, ..., e
s
auf folgende Weise verbinden:
k
1
zeigt von e
0
nach e
1
,
k
2
zeigt von e
1
nach e
2
,
...,
k
s
zeigt von e
s-1
nach e
s
.
Anders ausgedrückt:
k
1
= e
0,
e
1
,
k
2
=e
1,
e
2
,... ,
k
s
=e
s1
,e
s
mit
k
i
und e
i
E.
Ein gerichteter Kantenzug heißt geschlossen, wenn e
0
= e
s
gilt.
Ein gerichteter Kantenzug wird genau dann als Weg bezeichnet, wenn alle
Kanten verschieden sind. Sind zusätzlich alle Ecken der gerichteten
Kanten verschieden, wird von einem Pfad gesprochen. Ein geschlossener
gerichteter Pfad heißt gerichteter Kreis.
Der in Kapitel 1 eingeführte Begriff ,,Grad einer Ecke" ist in veränderter
Form auch in gerichteten Graphen anwendbar. Hier wird zwischen einem
Eingangsgrad deg
-
(e) und einem Ausgangsgrad deg
+
(e) unterschieden.
Dabei meint der Begriff des Ausgangsgrades alle gerichteten Kanten, die
von einer Ecke e weg zeigen und der des Eingangsgrades alle gerichteten
Kanten, die zu e hin zeigen. Ist der Eingangsgrad einer Ecke gleich Null,
gilt also deg
-
(e) = 0, so wird diese Ecke als Quelle bezeichnet. Ist der
Ausgangsgrad einer Ecke e gleich Null, das heißt es gilt deg
+
(e) = 0, wird
diese Ecke als Senke bezeichnet. Aus einer Quelle zeigen also nur
gerichtete Kanten heraus, während sie in eine Senke nur hineinzeigen.
In jedem gerichteten Graphen
G ist auch ein ungerichteter Graph G zu
finden. Es müssen einfach nur alle Pfeile von den Kanten entfernt werden,
das heißt gerichtete Kanten werden durch ungerichtete Kanten ersetzt.
12
Gerichtete Graphen
Der Graph G enthält also dieselbe Eckenmenge wie der Graph
G .
Dementsprechend existiert zu jeder gerichteten Kante k
K mit dem
geordneten Paar (e
s-1
, e
s
) eine ungerichtete Kante k K mit dem
ungeordneten Paar (e
s-1
, e
s
). Dieser Graph G heißt zugrundeliegender
oder unterliegender Graph von.
G
2.2 Turniere
3
Der Begriff Turnier wird für gerichteten Graphen verwendet, da mit ihrer
Hilfe Ergebnisse von Wettkämpfen dargestellt werden können. Ein Turnier
mit n Ecken ist ein Turnier, in dem jeder der n Spieler gegen jeden der
anderen n 1 Spieler antritt und das Ergebnis stets aus einem Sieg für
den einen Spieler und einer Niederlage für den anderen besteht, das heißt
es gibt kein Unentschieden. Bei der Modellierung des Graphen
symbolisieren die Ecken die Spieler und die Kanten die Ergebnisse. Eine
gerichtete Kante von A nach B bedeutet, dass Spieler A gegen Spieler B
gewonnen hat. Da jeder Spieler gegen jeden antritt, liegt dem Graphen
G ein vollständiger Graph G zugrunde. Abb. 2.2.1 zeigt alle nicht
isomorphen Turniere mit höchstens vier Ecken. Die Anzahl der nicht
isomorphen Turniere steigt mit der Anzahl der Ecken stark an. Bei genau
einer Ecke gibt es nur ein Turnier. Gleiches gilt für zwei Ecken. Bei drei
Ecken gibt es zwei Turniere, bei vier Ecken sind es vier und bei fünf Ecken
sind es schon zwölf Turniere. CLARK und HOLTON [1994, S. 271] zufolge
existieren bei zehn Ecken über neun Millionen solcher nicht isomorphen
Turniere.
T
1
T
2
T
3
T
4
1 Ecke 2 Ecken
3 Ecken
e
1
e
0
e
1
e
0
e
1
e
0
e
1
e
0
T
5
T
6
T
7
T
8
e
2
e
3
e
2
e
3
e
2
e
3
e
2
e
3
4 Ecken
Abb. 2.2.1 Alle Turniere mit maximal vier Ecken
3 Ab hier ist jede erwähnte Kante eine gerichtete, daher wird auf die Darstellung
k
verzichtet. Das Symbol k soll an dieser Stelle genügen.
13
Gerichtete Graphen
In den Turnieren T
5
bis
T
8
gibt es jeweils vier Ecken, also vier Teilnehmer.
Da jedem Turnier eine vollständiger Graph zugrunde liegt, gibt es
1
2
nn1=
1
2
4 41=6 Kanten. Der maximale Ausgangsgrad einer
Ecke ist drei, nämlich immer dann, wenn ein Spieler gegen alle anderen
Spieler gewinnt. Dies ist in den beiden Turnieren T
5
und T
6
der Fall.
Gesucht ist nun eine weitere Ecke mit nächst größtem Ausgangsgrad. In
T
5
gibt es eine Ecke, für die deg
+
(e) = 2 gilt. Da die Summe der
Ausgangsgrade aller Ecken der Anzahl der Kanten entsprechen muss,
kann es nur noch eine Ecke geben, für die deg
+
(e) = 1 ist und eine
weitere, für die deg
+
(e) = 0 ist. Für die Turniere T
5
bis T
8
ergibt sich daher
folgendes Bild:
T
5
deg
+
(e
0
) = 3, deg
+
(e
1
) = 2, deg
+
(e
3
) = 1 und deg
+
(e
2
) = 0
T
6
deg
+
(e
1
) = 3, deg
+
(e
0
) = 1, deg
+
(e
2
) = 1 und deg
+
(e
3
) = 1
T
7
deg
+
(e
0
) = 2, deg
+
(e
2
) = 2, deg
+
(e
3
) = 2 und deg
+
(e
1
) = 0
T
8
deg
+
(e
0
) = 2, deg
+
(e
1
) = 2, deg
+
(e
2
) = 1 und deg
+
(e
3
) = 1
Andere Zahlenkombinationen der Ausgangsgrade sind nicht möglich.
Würden die Ausgangsgrade anders auf die Ecken verteilt werden,
entstünden nur isomorphe Turniere.
In jedem der Turniere gibt es eine Ecke mit maximalem Ausgangsgrad.
Von dieser Ecke aus ist jede andere Ecke in dem Turnier über einen
gerichteten Pfad der maximalen Länge 2 erreichbar. Dies kann in obiger
Abbildung überprüft werden. Die allgemeine Gültigkeit wird in Satz 3.2.1
bewiesen.
Satz 2.2.1. Es sei e eine beliebige Ecke mit maximalem Ausgangsgrad in
einem Turnier T. Dann gibt es für jede Ecke a von T einen gerichteten Pfad
von e nach a, dessen Länge maximal zwei beträgt.
Beweis. Es sei deg
+
(e) = m. Dann zeigen genau m Kanten von e nach
e
1
, e
2
, ..., e
m
. Wenn T insgesamt n Ecken hat, gibt es n
-m-1 weitere
Ecken a
1
, a
2
, ..., a
n-m-1
. Weil T ein Turnier und somit vollständig ist, sind
diese Ecken adjazent zu e, das heißt es gibt Kanten von a
j
nach e
für 1
j n-m-1 (siehe Abb. 3.2.2). Die Kanten müssen von a
j
nach e
14
0 Kommentare