Das Skript zum Seminar "Geometrie" umfasst die folgenden Themen: Flüsse und Netzwerke und Ford Fulkerson Algorithmus mit Beispiel.
Inhaltsverzeichnis
- Definitionen
- Gerichteter Graph oder Digraph
- s - t-Fluss
- Wert eines s - t-Flusses
- Residualgraph
- Ford-Fulkerson Algorithmus
- Lemmata
- Wert eines s - t-Flusses
- Wert eines s - t-Flusses im Residualgraphen
Zielsetzung und Themenschwerpunkte
Dieser Text befasst sich mit der mathematischen Modellierung von Netzwerken mithilfe gerichteter Graphen und Flüssen. Die Zielsetzung ist es, die grundlegenden Definitionen und Konzepte im Zusammenhang mit gerichteten Graphen, s-t-Flüssen und deren Wert sowie dem Residualgraphen darzustellen. Darüber hinaus wird der Ford-Fulkerson-Algorithmus zur Berechnung des maximalen Flusses in einem Netzwerk vorgestellt.
- Gerichtete Graphen und ihre Eigenschaften
- Definition und Eigenschaften von s-t-Flüssen
- Der Wert eines s-t-Flusses und dessen Berechnung
- Der Residualgraph und seine Bedeutung für die Flussoptimierung
- Der Ford-Fulkerson-Algorithmus zur Bestimmung des maximalen Flusses
Zusammenfassung der Kapitel
Der Text behandelt die Definition und die wichtigsten Eigenschaften gerichteter Graphen und Flüssen in Netzwerken. Zuerst werden die Grundbegriffe wie gerichtete Graphen, s-t-Flüsse und der Wert eines s-t-Flusses definiert. Anschließend werden die wichtigsten Lemmata zum Thema behandelt, die den Zusammenhang zwischen dem Wert eines s-t-Flusses und der Kapazität eines Schnitts im gerichteten Graphen aufzeigen. Weiterhin wird der Residualgraph vorgestellt, der eine entscheidende Rolle bei der Optimierung von Flüssen in Netzwerken spielt. Der Text schließt mit einer detaillierten Beschreibung des Ford-Fulkerson-Algorithmus, einem effizienten Verfahren zur Berechnung des maximalen Flusses in einem Netzwerk.
Schlüsselwörter
Gerichtete Graphen, Digraph, s-t-Fluss, Flusswert, Residualgraph, Kapazitätsfunktion, Ford-Fulkerson-Algorithmus, maximaler Fluss, Schnitt, Netzwerk, Flusserhaltungssatz
- Arbeit zitieren
- Felix Busch (Autor:in), 2018, Gerichtete Graphen und Flüsse in Netzwerken (Ford Fulkerson), München, GRIN Verlag, https://www.grin.com/document/441920
