Netzwerkflussalgorithmen

Netzwerkflussalgorithmen berechnen die maximale Flussmenge, die von einer Quelle zu einer Senke durch ein kapazitiertes Netzwerk gesendet werden kann, ein Problem, dessen Optimum durch Dualität mit dem minimalen Schnitt des Netzwerks verbunden ist.

Definition

Ein Flussnetzwerk ist ein gerichteter Graph mit Kantenkapazitäten, einer Quelle und einer Senke; ein Maximum-Flow-Algorithmus findet eine Zuweisung von Fluss zu Kanten, die Kapazitäten und Erhaltung an Zwischenknoten respektiert und den Gesamtfluss von der Quelle zur Senke maximiert.

Scope

Dieses Thema behandelt das Maximum-Flow-Problem und seine Algorithmen: die Ford-Fulkerson-Methode mit augmentierenden Pfaden, die Edmonds-Karp- und Dinic-Verfeinerungen, die die Laufzeit begrenzen, und den Max-Flow-Min-Cut-Theorem, der das Optimum charakterisiert. Es behandelt auch Reduktionen anderer Probleme – bipartites Matching, knotendisjunkte Pfade, Projektauswahl – auf den Netzwerkfluss. Es schließt die allgemeine lineare Programmierung aus, von der der Fluss ein Spezialfall ist.

Core questions

• Wie wird ein Fluss definiert und welche Beschränkungen muss er erfüllen?
• Wie erhöhen augmentierende Pfade im Residualgraphen den Fluss in Richtung des Maximums?
• Warum ist der maximale Fluss gleich der minimalen Schnittkapazität?
• Wie garantieren die Algorithmen von Edmonds-Karp und Dinic eine polynomiale Laufzeit?
• Wie werden Matching- und andere Probleme auf den maximalen Fluss reduziert?

Key concepts

• Flussnetzwerk
• Kapazität und Erhaltung
• augmentierender Pfad
• Residualgraph
• Max-Flow-Min-Cut-Theorem
• Edmonds-Karp-Algorithmus
• Dinic-Algorithmus
• Reduktion auf bipartites Matching

Key theories

Max-Flow-Min-Cut-Theorem

Der Wert eines maximalen Flusses von der Quelle zur Senke entspricht der minimalen Kapazität eines Schnitts, der sie trennt; diese Dualität, die auf Ford und Fulkerson zurückgeht, bestätigt die Optimalität und verbindet den Fluss mit Konnektivitäts- und Partitionierungsproblemen.

Augmentierende Pfade und Residualgraphen

Die Ford-Fulkerson-Methode erhöht den Fluss, indem sie Pfade mit freier Kapazität im Residualgraphen findet; die Wahl kürzester augmentierender Pfade (Edmonds-Karp) oder die Verwendung von Level-Graphen und blockierenden Flüssen (Dinic) gewährleistet polynomiale Laufzeitgarantien.

Clinical relevance

Der Netzwerkfluss ist ein vielseitiges Modellierungswerkzeug: Er löst bipartite Zuordnungs- und Zeitplanungsprobleme, berechnet die Konnektivität und Zuverlässigkeit von Netzwerken, führt Bildsegmentierung mittels Graph-Schnitten in der Computer Vision durch und untermauert Logistik, Transportplanung und Optimierung der Projektauswahl, wo Kapazitäten und Engpässe eine Rolle spielen.

History

Ford und Fulkerson führten das Maximum-Flow-Problem und den Max-Flow-Min-Cut-Theorem 1956 bei der Untersuchung von Transportnetzwerken ein. Edmonds und Karp (1972) und, unabhängig davon, Dinic (1970) lieferten die ersten polynomialzeitlichen Algorithmen, und nachfolgende Arbeiten haben die asymptotische Laufzeit des maximalen Flusses stetig verbessert.

Key figures

• Lester Ford
• Delbert Fulkerson
• Jack Edmonds
• Yefim Dinic

Seminal works

• fordfulkerson1956
• cormen2009

Frequently asked questions

Was besagt der Max-Flow-Min-Cut-Theorem eigentlich?

Er besagt, dass die größte Flussmenge, die man von der Quelle zur Senke schieben kann, der kleinsten Gesamtkapazität jeder Menge von Kanten entspricht, deren Entfernung die Quelle von der Senke trennt. Der minimale Schnitt fungiert als Engpass, der den maximalen Fluss begrenzt.

Warum hat der einfache Ford-Fulkerson-Algorithmus keine polynomiale Laufzeit?

Wenn augmentierende Pfade schlecht gewählt werden und Kapazitäten groß (oder irrational) sind, kann die Anzahl der Augmentationen sehr hoch sein oder sogar nicht terminieren. Die Wahl kürzester augmentierender Pfade (Edmonds-Karp) oder die Verwendung von blockierenden Flüssen (Dinic) begrenzt die Anzahl der Augmentationen und führt zu polynomialer Zeit.