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
- Einleitung
- Graphentheoretische Grundlagen
- Vollständige Graphen
- Bipartite Graphen
- Kantenzug
- Weg
- Pfad
- Kreis
- Grad einer Ecke
- Hamiltongraphen
- Bäume
- Gerichtete Graphen
- Einführung
- Turniere
- Netzwerke
- Einführung
- Flüsse und Schnitte
- Der Algorithmus von Ford und Fulkerson
- Trennende Mengen
- Zerlegungsecken & Eckenzusammenhangszahl
- Brücke & Kantenzusammenhangszahl
- Trennende Ecken- und Kantenmenge
- Der Satz von Menger.
- Anwendungsbeispiele
- Major League Baseball
- Flugplanerstellung
Zielsetzung und Themenschwerpunkte
Diese Arbeit soll einen Einblick in die Graphentheorie mit dem Fokus auf Netzwerke als graphische Darstellungsform bieten. Sie dient dazu, die grundlegenden Konzepte der Graphentheorie zu erklären und verschiedene Anwendungen dieser Konzepte in der Praxis zu beleuchten.
- Grundlagen der Graphentheorie
- Gerichtete und ungerichtete Graphen
- Netzwerke und ihre Eigenschaften
- Der Satz von Menger und seine Anwendungen
- Anwendungsbeispiele in verschiedenen Bereichen
Zusammenfassung der Kapitel
Die Arbeit beginnt mit einer Einführung in die Graphentheorie, wobei verschiedene Grundbegriffe wie vollständige Graphen, bipartite Graphen und Kantenzüge erläutert werden. Das Kapitel 2 erweitert diese Grundlagen auf gerichtete Graphen und stellt den Begriff des Turniers vor. Das 3. Kapitel widmet sich dem Thema Netzwerke und führt wichtige Konzepte wie Flüsse und Schnitte ein, um den Maximum-Fluss-Minimum-Schnitt-Satz von Ford und Fulkerson zu beweisen. Im 4. Kapitel werden trennende Mengen und der Satz von Menger behandelt, der wiederum mit dem Maximum-Fluss-Minimum-Schnitt-Satz zusammenhängt. Abschließend werden in Kapitel 5 zwei Anwendungsbeispiele für den Maximum-Fluss-Minimum-Schnitt-Satz vorgestellt.
Schlüsselwörter
Die Arbeit beschäftigt sich mit den Themen Graphentheorie, Netzwerke, Flüsse und Schnitte, Maximum-Fluss-Minimum-Schnitt-Satz, Ford und Fulkerson Algorithmus, trennende Mengen, Satz von Menger, Anwendungsbeispiele.
- Quote paper
- Sandra Riedemann (Author), 2007, Netzwerke. Ein spezielles Gebiet der Graphentheorie, Munich, GRIN Verlag, https://www.grin.com/document/92740
