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.
Inhaltsverzeichnis
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
Zielsetzung & Themen
Die vorliegende Arbeit zielt darauf ab, einen fundierten Einblick in die Graphentheorie mit besonderem Fokus auf die Modellierung von Netzwerken und deren Anwendungen zu vermitteln. Die zentrale Fragestellung konzentriert sich darauf, wie mithilfe des Maximum-Fluss-Minimum-Schnitt-Satzes optimale Lösungen für Transport- und Logistikprobleme gefunden werden können.
- Grundlagen der Graphentheorie (Graphen, Pfade, Kreise, Bäume)
- Eigenschaften und Anwendungen gerichteter Graphen und Turniere
- Theorie der Netzwerke, Flüsse und Schnitte
- Konzepte trennender Mengen und der Satz von Menger
- Praktische Anwendungsbeispiele (Baseball-Turnierplanung und Flugplanerstellung)
Auszug aus dem Buch
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 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.
Zusammenfassung der Kapitel
Graphentheoretische Grundlagen: Dieses Kapitel führt zentrale Begriffe der Graphentheorie ein, darunter verschiedene Graphentypen, Pfade und Kreise, die als Fundament für die weiteren Analysen dienen.
Gerichtete Graphen: Hier wird die Graphentheorie auf gerichtete Kanten erweitert, wobei das Konzept der Turniere als Modell für Wettbewerbsergebnisse im Detail untersucht wird.
Netzwerke: Das Kapitel behandelt den Fluss durch Netzwerke und führt den Maximum-Fluss-Minimum-Schnitt-Satz sowie den Algorithmus von Ford und Fulkerson ein.
Trennende Mengen: Es werden Methoden zur Analyse der Zusammenhangszahlen von Graphen vorgestellt, wobei der Satz von Menger die Verbindung zwischen Pfaden und trennenden Mengen herstellt.
Anwendungsbeispiele: Die theoretischen Erkenntnisse werden abschließend auf die Planung von Baseball-Spielplänen und die Erstellung von Flugplänen in der Logistik angewendet.
Schlüsselwörter
Graphentheorie, Netzwerke, Maximum-Fluss-Minimum-Schnitt-Satz, Ford-Fulkerson-Algorithmus, Gerichtete Graphen, Turniere, Satz von Menger, Zerlegungsecken, Kantenzusammenhang, Logistik, Modellierung, Hamiltonpfad, Fluss, Kapazität, Disjunkte Wege.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit bietet eine systematische Einführung in die Graphentheorie und konzentriert sich besonders auf die Anwendung von Netzwerkmodellen zur Lösung praktischer Probleme.
Was sind die zentralen Themenfelder?
Die zentralen Themen sind Graphenstrukturen, der Fluss in Netzwerken, die mathematische Analyse von trennenden Mengen sowie die Anwendung dieser Theorien in der Logistik.
Was ist das primäre Ziel oder die Forschungsfrage?
Das Ziel ist es, die theoretischen Grundlagen der Graphentheorie zu erläutern und aufzuzeigen, wie sie genutzt werden können, um Flussprobleme in Netzwerken effizient zu lösen.
Welche wissenschaftliche Methode wird verwendet?
Es werden klassische graphentheoretische Beweismethoden verwendet, ergänzt durch die Modellierung mittels Algorithmen wie dem von Ford und Fulkerson.
Was wird im Hauptteil behandelt?
Der Hauptteil behandelt die mathematische Theorie hinter gerichteten Graphen, die Eigenschaften von Flüssen und Schnitten sowie die Bedeutung von trennenden Mengen für den Zusammenhang von Graphen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Schlüsselbegriffe sind Netzwerke, Fluss-Schnitt-Sätze, Ford-Fulkerson, Graphentheorie, Menger-Satz und angewandte diskrete Mathematik.
Was genau versteht man unter einem Turnier im graphentheoretischen Kontext?
Ein Turnier ist ein gerichteter Graph, bei dem zwischen jedem Paar verschiedener Ecken genau eine gerichtete Kante verläuft, was Ergebnisse von "Jeder gegen Jeden"-Wettkämpfen ohne Unentschieden abbildet.
Wie hilft der Satz von Menger bei der Analyse von Graphen?
Der Satz von Menger zeigt die mathematische Äquivalenz zwischen der maximalen Anzahl disjunkter Wege zwischen zwei Knoten und der minimalen Anzahl an Knoten oder Kanten, deren Entfernung die Verbindung zwischen diesen Knoten unterbrechen würde.
- Quote paper
- Sandra Riedemann (Author), 2007, Netzwerke. Ein spezielles Gebiet der Graphentheorie, Munich, GRIN Verlag, https://www.grin.com/document/92740
