Max-Flow-Min-Cut-Theorem

mathematischer Satz

Auf dem Gebiet der Graphentheorie bezeichnet das Max-Flow-Min-Cut-Theorem einen Satz, der eine Aussage über den Zusammenhang von maximalen Flüssen und minimalen Schnitten eines Flussnetzwerkes gibt. Der Satz besagt:

Ein maximaler Fluss im Netzwerk hat genau den Wert eines minimalen Schnitts.

Der Satz ist eine Verallgemeinerung des Satzes von Menger. Er wurde im Jahr 1956 unabhängig von L.R. Ford Jr. und D.R. Fulkerson, sowie von P. Elias, A. Feinstein und C.E. Shannon bewiesen.[1][2]

Definitionen

Bearbeiten

Sei   ein endlicher gerichteter Graph mit den Knoten   und den Kanten  . Jede Kante   vom Knoten   zum Knoten   habe eine nichtnegative Kapazität   Außerdem gibt es einen Quellknoten  , in dem der Netzwerkfluss beginnt, und einen Zielknoten  , in dem der Netzwerkfluss endet.

Ein Schnitt ist eine Aufteilung der Knoten in zwei disjunkte Teilmengen   und   für die gilt,   und  . Die Kapazität eines Schnittes   ist die Summe aller Kantenkapazitäten von   nach  , also

 .

Die folgenden drei Aussagen sind äquivalent:

  1.   ist der maximale Fluss in  .
  2. Das Residualnetzwerk   enthält keinen augmentierenden Pfad.
  3. Für mindestens einen Schnitt   ist der Wert des Flusses gleich der Kapazität des Schnittes:  

Beweisskizze

Bearbeiten
  •   Wenn es einen augmentierenden Pfad gäbe, so könnte man den Fluss entlang dessen vergrößern; somit kann der Fluss nicht maximal gewesen sein.
  •   Wenn es keinen augmentierenden Pfad gibt, dann teile den Graph in  , die von   im Residualnetzwerk erreichbaren Knoten, und  , den Rest. Dann ist   (wäre es nicht 0, so wäre   doch erreichbar gewesen). Dann ist für diesen Schnitt  .
  •   Wenn   nicht maximal wäre, so könnte man ihn vergrößern. Da   kleiner gleich der Kapazität eines jeden Schnitts ist, kann für mindestens einen Schnitt die Kapazität noch nicht ausgenutzt sein; darüber hinaus gilt   für keinen Schnitt, weil sonst kein augmentierender Pfad für die Flussvergrößerung bestünde und der Fluss maximal wäre.

Insbesondere zeigt dies, dass der maximale Fluss gleich dem minimalen Schnitt ist: Wegen 3. hat er die Größe mindestens eines Schnitts, also mindestens des kleinsten, und wegen 2. auch höchstens diesen Wert, weil das Residualnetzwerk bereits wenn   die Größe des kleinsten Schnitts erreicht hat, keinen augmentierenden Pfad mehr enthalten kann.

Beispiel

Bearbeiten
 
Ein Netzwerk mit maximalem Fluss und drei minimalen Schnitten
 
Das Residualnetzwerk des Beispielnetzwerks

Sei das Flussnetzwerk mit den Knoten   gegeben, und ein maximaler Fluss von der Quelle   zur Senke   der Größe 5.

Es gibt drei minimale Schnitte in diesem Netzwerk:

Schnitt Kapazität
   
   
   

Anmerkung: Bei allen anderen Schnitten ist die Summe der Kapazitäten (nicht zu verwechseln mit dem Fluss) der ausgehenden Kanten größer gleich 6. Zum Beispiel ist   kein minimaler Schnitt, da die Summe der Kapazitäten der ausgehenden Kanten gleich   ist. Des Weiteren ist   kein minimaler Schnitt, obwohl   und   voll genutzt werden; denn es gibt im Residualnetzwerk   noch eine Kante (r,q) der Restkapazität  .

Algorithmus zum Finden minimaler Schnitte

Bearbeiten

Es gibt verschiedene Algorithmen zum Finden minimaler Schnitte. Der folgende Algorithmus findet die Kanten eines minimalen Schnittes direkt aus dem Residualnetzwerk und macht sich damit die Eigenschaften des Max-Flow-Min-Cut-Theorems zu Nutze. Der Restflussgraph kann zum Beispiel mit Hilfe des Algorithmus von Ford und Fulkerson erzeugt werden.

  ein endlicher gerichteter Graph mit einer Quelle  , einer Senke   und jede Kante habe eine nichtnegative Kapazität.
findeKantenEinesMinCut( )
1  Residualnetzwerk( )
2  
3  
4 Für jeden Knoten  
5  Wenn Pfad( ) in   existiert
6  dann  
7  ansonsten  
8  
9 Für jede Kante  
10 Wenn startKnoten( )  und endKnoten( )  liegt
11  dann  
12   ist jetzt die Menge der Kanten für einen minimalen Schnitt

  würde im oberen Beispiel die Schnittkanten von   enthalten.

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. L.R. Ford Jr., D.R Fulkerson: Maximal flow through a network. In: Canad. J. Math. 8. Jahrgang, 1956, S. 399–404, doi:10.4153/CJM-1956-045-5 (math.ca [PDF]).
  2. P. Elias, A. Feinstein, C.E. Shannon: Note on Maximum Flow Through a Network. In: IRE Trans. on Information Theory, IT. 2. Jahrgang, Nr. 4, 1956, S. 117–119, doi:10.1109/TIT.1956.1056816 (ece.rice.edu (Memento des Originals vom 4. März 2016 im Internet Archive) [abgerufen am 3. September 2013]).