Das Skript zum Seminar "Geometrie" umfasst die folgenden Themen: Flüsse und Netzwerke und Ford Fulkerson Algorithmus mit Beispiel.
Inhaltsverzeichnis
2.1 Definition
2.2 Definition
2.3 Definition
2.4 Definition
2.5 Definition
2.6 Lemma
2.7 Definition
2.8 Definition
2.9 Lemma
2.10 Algorithmus
Zielsetzung & Themen
Die vorliegende Arbeit befasst sich mit den theoretischen Grundlagen gerichteter Graphen sowie der mathematischen Modellierung von Flüssen in Netzwerken. Das primäre Ziel ist es, die Definitionen von Flusskapazitäten, den Flusserhaltungssatz sowie die Funktionsweise des Ford-Fulkerson-Algorithmus zur Bestimmung maximaler Flüsse in einem Netzwerk präzise darzulegen und anhand von Beispielen zu erläutern.
- Mathematische Definition gerichteter Graphen (Digraphen)
- Eigenschaften und Berechnung von s-t-Flüssen
- Einführung in Kapazitätsfunktionen und zulässige Flüsse
- Konzept des Residualgraphen
- Anwendung des Ford-Fulkerson-Algorithmus zur Flussmaximierung
Auszug aus dem Buch
Definition 2.7: Residualgraph
Sei G(E,K) ein gerichteter Graph. u, v ∈ E. Man betrachte Kante k ∈ K mit a(k) := u und e(k) := v. Dann definieren wir Kante k-1 durch a(k-1) := e(k) = v und e(k-1) := a(k) = u, wobei K-1 = {k-1 : k ∈ K}.
Sei f ein s - t-Fluss und c eine Kapazitätsfunktion. Wir definieren den Residualgraphen durch Gf = (E,Kf ), mit:
Kf := {k ∈ K : f(k) < c(k)} ∪ {k-1 ∈ K-1 : f(k) > 0}
Zusammenfassung der Kapitel
Definition 2.1: Einführung in die formalen Grundlagen eines gerichteten Graphen als Quadrupel mit Ecken- und Kantenmenge.
Definition 2.2: Spezifikation von Quelle und Senke in einem gerichteten Graphen.
Definition 2.3: Erläuterung des s-t-Flusses und des Flusserhaltungssatzes, der besagt, dass die einfließende Menge der fließenden Menge entsprechen muss.
Definition 2.4: Definition des Wertes eines s-t-Flusses und der Beschränkung durch eine Kapazitätsfunktion.
Definition 2.5: Bestimmung eines maximalen s-t-Flusses durch Ausschöpfung der Kapazitäten.
Lemma 2.6: Beweisführung über die Schranken des Flusswertes in Bezug auf Kapazitätsfunktionen.
Definition 2.7: Konstruktion eines Residualgraphen zur Abbildung freier Kapazitäten.
Definition 2.8: Definition der Indikatorfunktion für Kanten in einem Residualgraphen.
Lemma 2.9: Nachweis der Maximalität eines Flusses unter der Bedingung, dass kein erweiternder Weg existiert.
Algorithmus 2.10: Praktische Demonstration des Ford-Fulkerson-Algorithmus zur sukzessiven Steigerung des Flusswertes.
Schlüsselwörter
Gerichteter Graph, Digraph, Netzwerkanalyse, Fluss, Kapazitätsfunktion, Quelle, Senke, Flusserhaltungssatz, Residualgraph, Ford-Fulkerson-Algorithmus, Maximaler Fluss, Kantenmenge, Eckenmenge, s-t-Fluss, In-Grad
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die mathematische Modellierung von Flüssen innerhalb von gerichteten Graphen unter Berücksichtigung von Kapazitätsbeschränkungen.
Was sind die zentralen Themenfelder?
Die zentralen Themen sind die Definition von Graphen, die Analyse von Flusskapazitäten, die theoretische Herleitung maximaler Flüsse und deren algorithmische Bestimmung.
Was ist das primäre Ziel der Arbeit?
Das Ziel ist die Vermittlung der theoretischen Voraussetzungen und der praktischen Anwendung des Ford-Fulkerson-Algorithmus zur Optimierung von Netzflüssen.
Welche wissenschaftliche Methode wird verwendet?
Es wird eine deduktive, mathematische Methodik verwendet, die auf Definitionen, Lemmata und algorithmischen Konstruktionen basiert.
Was wird im Hauptteil behandelt?
Der Hauptteil befasst sich detailliert mit der mathematischen Formalisierung von Graphen, der Definition von Flüssen, dem Flusserhaltungssatz und der Herleitung des Residualgraphen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wesentliche Begriffe sind Flussnetzwerke, maximale Flüsse, Kapazitätsfunktionen und der Ford-Fulkerson-Algorithmus.
Was unterscheidet einen s-t-Fluss von einem normalen Graphen?
Ein s-t-Fluss ist ein spezieller gerichteter Graph, der eine eindeutige Quelle (s) und eine Senke (t) besitzt, wobei die Kanten mit Werten (Flüssen) belegt sind, die den Flusserhaltungssatz erfüllen müssen.
Warum ist der Residualgraph für den Algorithmus wichtig?
Der Residualgraph zeigt auf, welche Kanten noch freie Kapazitäten haben oder wo bereits fließende Mengen rückgängig gemacht werden können, um den Gesamtdurchsatz weiter zu erhöhen.
Wie wird im Ford-Fulkerson-Algorithmus die Maximalität erreicht?
Die Maximalität wird erreicht, indem man sukzessive Pfade in den Residualgraphen findet, solange dies möglich ist, und den Fluss entlang dieser Wege erhöht.
- Citar trabajo
- Felix Busch (Autor), 2018, Gerichtete Graphen und Flüsse in Netzwerken (Ford Fulkerson), Múnich, GRIN Verlag, https://www.grin.com/document/441920
