Netzwerke. Ein spezielles Gebiet der Graphentheorie

Inhaltsverzeichnis

Einleitung

1 Graphentheoretische Grundlagen
1.1 Vollständige Graphen
1.2 Bipartite Graphen
1.3 Kantenzug
1.4 Weg
1.5 Pfad
1.6 Kreis
1.7 Grad einer Ecke
1.8 Hamiltongraphen
1.9 Bäume

2 Gerichtete Graphen
2.1 Einführung
2.2 Turniere

3 Netzwerke
3.1 Einführung
3.2 Flüsse und Schnitte
3.3 Der Algorithmus von Ford und Fulkerson

4 Trennende Mengen
4.1 Zerlegungsecken & Eckenzusammenhangszahl
4.2 Brücke & Kantenzusammenhangszahl
4.3 Trennende Ecken- und Kantenmenge
4.4 Der Satz von Menger

5 Anwendungsbeispiele
5.1 Major League Baseball
5.2 Flugplanerstellung 66

Schlussbemerkung

Literaturverzeichnis

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.

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 e0 und e1 entweder durch keine, genau eine oder mehrere Kanten ks miteinander verbunden sein. Zum Beispiel bedeutet k1 = {e0,e1}, dass die Kante k1 die Ecken e0 und e1 verbindet.

Graphen werden im folgenden mit G bezeichnet. Soll die Eckenmenge

E = { e0, e1,... , es} oder die Kantenmenge K = { k1, k2, ...,ks} 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 Kn bezeichnet. Es folgen Beispiele für die vollständigen Graphen

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1.1 Die vollständigen Graphen K1 bis K

Graphentheoretische Grundlagen

Der vollständige Graph Kn hat immer Kanten. Da eine Kante immer genau zwei Ecken verbindet und jede Ecke aufgrund der Vollständigkeit mit allen anderen Ecken verbunden ist, gibt es für jede Ecke genau Kanten. Bei n Ecken gibt es dann Kanten. Da e0,e1} = {e1,e0} ist, halbiert sich das Produkt und es folgt.

Abbildung in dieser Leseprobe nicht enthalten

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 E1 und E2 zusammen: E = E1 È E2 . Dabei gilt

[Abbildung in dieser Leseprobe nicht enthalten], das heißt die beiden Eckenklasse haben keine gemeinsamen Ecken. Im folgenden Beispiel sind die schwarzen Ecken E1 und die grauen Ecken E2 zu zuordnen.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1.2.1 Bipartite Graphen

Ein bipartiter Graph heißt vollständig, wenn jede Ecke aus E1 mit jeder anderen Ecke aus E2 durch genau eine Kante verbunden ist. Wenn E1 genau m und E2 genau n Ecken hat, wird der vollständig bipartite Graph auch mit Km,n bezeichnet.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1.2.2 Die vollständig bipartiten Graphen K2,2 , K3,3 und K2,

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 k1, k2, ..., ks die Ecken e0, e1, ..., es auf folgende Weise verbinden:

k1 verbindet die Ecken e0 und e1,

k2 verbindet die Ecken e1 und e2,

ks verbindet die Ecken es-1 und es.

Anders ausgedrückt: k1 = {e0,e1}, k2= {e1, e2}, ..., ks = { es-1, es},

mit ki Î K und ei Î E.

Zu beachten ist, dass weder die Ecken noch die Kanten verschieden sein müssen. Der Graph muss jedoch zusammenhängend sein.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1.3.1 Ein Kantenzug von e0 nach e

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1.3.1 Ein geschlossener Kantenzug von e0 nach e

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 e0 nach e4 , so dass die Ecke e1 zweimal genutzt wird.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1.4 Ein Weg von e0 nach e4^[1]

Der Weg in Abb. 1.4 verläuft von e0 über die Ecken e1, e2 und e3, dann erneut über e1 zur Endecke e4.

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 e0 über e1 hin zur Endecke e4.

1.6 Kreis

Ein Kreis ist ein geschlossener Pfad. Da einem geschlossenem Pfad ein geschlossener Kantenzug zugrunde liegt, gilt auch hier e0 = es. 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 Cn geschrieben. In Abb. 2.5 ist links der Kreis C4 zusehen. Der rechte Graph ist zwar kein Kreis, besteht aber aus zwei Kreisen der Länge 3.

Graphentheoretische Grundlagen

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1.6 Kreise der Länge 4 und der Länge

1.7 Grad einer Ecke

Sei a Î E, dann heißt d(a):= ï{k Î Kïa Î 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.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1.7 Ecken mit den Graden 0, 1, 2 und

Für die Ecken in Abbildung 1.7 gilt:

d(e5) = 0, d(e0) = d(e4) = 1, d(e2) = d(e3) = 2 und d(e1) = 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

Graphentheoretische Grundlagen

Stadt enden, in der sie zuvor begonnen hatte.

Die roten Kanten in der unten stehende Abbildung zeigen eine solche mögliche Rundreise.

Abbildung in dieser Leseprobe nicht enthalten

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 Cn

(mit n > 0) enthält. Abb. 1.9 zeigt alle Bäume mit fünf Knoten.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1.9 Alle Bäume mit fünf Knoten

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.

Gerichtete Graphen

Abbildung in dieser Leseprobe nicht enthalten

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)}

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: {es-1, es}. Da die Ordnung bei gerichteten Kanten aber eine Rolle spielt, wird das Eckenpaar einer solchen Kante wie folgt geschrieben: (es-1, es).

Ein gerichteter Graph besteht ebenso wie ein ungerichteter Graph aus zwei endlichen Mengen. Der Eckenmenge E und der Kantenmenge K. Dabei gilt stets E ¹ Æ. Die Kantenmenge kann leer sein, muss sie aber nicht. Wenn gilt = Æ, dann handelt es sich um einen nicht zusammenhängenden Graphen.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.2 Ein einfach gerichteter Graph

Abb. 2.2 stellt den gerichteten Graphen mit der Eckenmenge

Abbildung in dieser Leseprobe nicht enthalten

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 eine Folge von aneinander gefügten Kanten, so dass die Kanten die Ecken e0, e1, ..., es auf folgende Weise verbinden:

Abbildung in dieser Leseprobe nicht enthalten

Ein gerichteter Kantenzug heißt geschlossen, wenn e₀ = 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 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.

Abbildung in dieser Leseprobe nicht enthalten

Gerichtete Graphen

Abbildung in dieser Leseprobe nicht enthalten

2.2 Turniere

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 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.^[3]

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.2.1 Alle Turniere mit maximal vier Ecken

Gerichtete Graphen

In den Turnieren T5 bis T8 gibt es jeweils vier Ecken, also vier Teilnehmer. Da jedem Turnier eine vollständiger Graph zugrunde liegt, gibt es

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 T5 und T6 der Fall. Gesucht ist nun eine weitere Ecke mit nächst größtem Ausgangsgrad. In T5 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 T5 bis T8 ergibt sich daher folgendes Bild:

Abbildung in dieser Leseprobe nicht enthalten

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

e1, e2, ..., em. Wenn T insgesamt n Ecken hat, gibt es n-m-1 weitere Ecken a1, a2, ..., an-m-1. Weil T ein Turnier und somit vollständig ist, sind diese Ecken adjazent zu e, das heißt es gibt Kanten von aj nach e

Abbildung in dieser Leseprobe nicht enthalten

zeigen, weil e schon den maximalen Ausgangsgrad hat.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.2.2 Die Ecke e mit maximalem Ausgangsgrad

Die Kanten von e zu ei für 1 £ i £ m liefern bereits einen gerichteten Pfad der Länge 1. Zu zeigen bleibt also nur noch, dass es einen gerichteten Pfad der Länge zwei von e nach aj für 1 £ j £ n-m-1 gibt.

Existiert eine Ecke aj und eine Kante von ei nach aj, dann ist e ei aj ein gerichteter Pfad der Länge zwei. Es bleibt zu zeigen, dass die Kanten stets von ei nach aj zeigen. Angenommen es gäbe eine Ecke ak für

[Abbildung in dieser Leseprobe nicht enthalten], für die es keine solche Kante gibt, dann muss es aber aufgrund der Vollständigkeit von T Kanten von ak zu jedem der m Ecken ei

geben. Außerdem existiert bereits eine Kante von ak nach e, so dass für den Ausgangsgrad von [Abbildung in dieser Leseprobe nicht enthalten]. Dies jedoch ist ein Widerspruch zu der eingangs aufgestellten Behauptung [Abbildung in dieser Leseprobe nicht enthalten] sei maximal.

Bezogen auf ein Turnier, in dem jeder Spiel gegen jeden anderen antritt, bedeutet dies folgendes: es sei e der Gewinner dieses Turniers, also der Spieler mit den meisten Siegen. Dann wurde dieser Spieler e nur von Spielern besiegt, die wiederum von Spielern besiegt wurden, die gegen e verloren haben.

Turniere besitzen noch weitere Eigenschaften. Angenommen T ist ein Turnier mit n Ecken und e eine beliebige Ecke von T. Werden nun e und alle mit dieser Ecke verbundenen Kanten entfernt, entsteht der Graph T-e. Da alle anderen Kanten bestehen bleiben, ist auch dieser Graph vollständig und folglich ein Turnier. Diese Eigenschaft hilft den nächsten

Satz zu beweisen.

Satz 2.2.2. In jedem Turnier T existiert ein gerichteter Hamiltonpfad.

Beweis. Der Beweis erfolgt durch vollständige Induktion.

Abbildung in dieser Leseprobe nicht enthalten

1. Fall: Es gibt eine Kante von e zu e1, das heißt die Ecke e wird dem Pfad P vorangestellt und es entsteht der Pfad P' = e, e1, e2,..., en-1.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.2.3 Die Ecke e wird dem Pfad vorangestellt

2. Fall: Es gibt eine Kante von en-1 zu e, das heißt die Ecke e wird dem Pfad P angehängt und es entsteht der Pfad P'' = e1, e2,..., en-1, e.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.2.4 Die Ecke e wird dem Pfad hinten angehängt

3. Fall: Die Ecke e wird weder vorne noch hinten an den Pfad P

abgehängt, das heißt es gibt keine Kante (e, e1) und keine Kante

(en-1, e). Stattdessen gibt es eine Ecke mit dem Index r (mit 1< r< n-1), für die gilt: alle Ecken e1, e2,..., er haben Kanten, die zu e hin zeigen. Die Ecke er+1 hat eine Kante, die von e weg zeigt. Auf diese Weise entsteht der gesuchte gerichtete Hamiltonpfad Q = e1, e2,..., er, er+1, er+2, ..., en-1.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.2.5 Einfügen einer Ecke mit dem Index r

Mit Hilfe der vollständigen Induktion wurde gezeigt, dass jedes Turnier einen gerichteten Hamiltonpfad besitzt. Solch ein Hamiltonpfad bietet nun die Möglichkeit, die Teilnehmer des Turniers entsprechend ihrer Position auf dem Pfad zu ordnen. Leider wird dieses System der Platzvergabe nicht immer allen Spielern gerecht, da es im allgemeinen mehrere Hamiltonpfade gibt, wenn das Turnier aus mindestens vier Teilnehmern besteht. Deshalb soll an dieser Stelle ansatzweise ein Wertungsverfahren beschrieben werden. Dabei ist die Wertung eines Spielers bzw. einer Ecke e in einem Turnier T als der Ausgangsgrad der Ecke definiert. In der ersten Wertung wird der Ausgangsgrad jeder Ecke in dem Turnier bestimmt, das heißt die Anzahl der gewonnenen Spiele eines jeden Teilnehmers. Steht nun schon eine eindeutige Rangfolge fest, so ist der Prozess abgeschlossen. Es kann aber auch mehrere Spieler mit derselben Wertung geben Diese müssen in einer zweiten Wertung genauer betrachtet werden. Die zweite Wertung eines Spielers ergibt sich aus der Summe der Wertungen derjenigen Spieler, die er besiegt hat. Liefert die zweite Wertung immer noch keine eindeutige Rangfolge,so folgt eine dritte Wertung usw. Wann genau ein Abbruch der Wertungen eintritt, kann mit Hilfe der Matrixtheorie bestimmt werden. CLARK und HOLTON verweisen in diesem Zusammenhang auf J.A. BONDY, U.S.R. MURTY: Graph Theory with Applications. Elsevier/MacMillan, New York/London, 1976.

[...]

---

^[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.

^[2] http://de.wikipedia.org/wiki/Soziogramm

^[3] Ab hier ist jede erwähnte Kante eine gerichtete, daher wird auf die Darstellung verzichtet. Das Symbol k soll an dieser Stelle genügen.

Abbildung in dieser Leseprobe nicht enthalten