Max-Flow-Min-Cut-Theorem - LinkFang.de





Max-Flow-Min-Cut-Theorem


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

Sei [math]G(V, E)[/math] ein endlicher gerichteter Graph mit den Knoten [math]V[/math] und den Kanten [math]E[/math]. Jede Kante [math](u,v)[/math] vom Knoten [math]u[/math] zum Knoten [math]v[/math] habe eine nichtnegative Kapazität [math]c(u,v).[/math] Außerdem gibt es einen Quellknoten [math]s[/math], in dem der Netzwerkfluss beginnt, und einen Zielknoten [math]t[/math], in dem der Netzwerkfluss endet.

Ein Schnitt ist eine Aufteilung der Knoten senkrecht zum Netzwerkfluss in zwei disjunkte Teilmengen [math]S[/math] und [math]T[/math] für die gilt, [math]s\in S[/math] und [math]t\in T[/math]. Die Kapazität eines Schnittes [math](S,T)[/math] ist die Summe aller Kantenkapazitäten von [math]S[/math] nach [math]T[/math], also

[math]c(S,T) = \sum_{u \in S, v \in T | (u,v) \in E} c(u,v)[/math].

Satz

Die folgenden drei Aussagen sind äquivalent:

  1. [math]f[/math] ist der maximale Fluss in [math]G[/math].
  2. Das Residualnetzwerk [math]G_f[/math] enthält keinen augmentierenden Pfad.
  3. Für mindestens einen Schnitt [math](S,T)[/math] ist der Wert des Flusses gleich der Kapazität des Schnittes: [math]|f| = c(S,T)[/math]

Beweisskizze

  • [math]1 \Rightarrow 2[/math] 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.
  • [math]2 \Rightarrow 3[/math] Wenn es keinen augmentierenden Pfad gibt, dann teile den Graph in [math]S[/math], die von [math]s[/math] im Residualnetzwerk erreichbaren Knoten, und [math]T[/math], den Rest. Dann ist [math]c(S,T) = 0[/math] (wäre es nicht 0, so wäre [math]T[/math] doch erreichbar gewesen). Dann ist für diesen Schnitt [math]|f| = c(S,T)[/math].
  • [math]3 \Rightarrow 1[/math] Wenn [math]f[/math] nicht maximal wäre, so könnte man ihn vergrößern. Da [math]f[/math] 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 [math]|f| = c(S,T)[/math] 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 [math]|f|[/math] die Größe des kleinsten Schnitts erreicht hat, keinen augmentierenden Pfad mehr enthalten kann.

Beispiel

Sei das Flussnetzwerk mit den Knoten [math]V=\{s,o,p,q,r,t\}[/math] gegeben, und ein maximaler Fluss von der Quelle [math]s[/math] zur Senke [math]t[/math] der Größe 5.

Es gibt drei minimale Schnitte in diesem Netzwerk:

Schnitt Kapazität
[math]S_1=\{s,p\},T=\{o,q,r,t\}[/math] [math]c(s,o)+c(p,r)=3+2=5[/math]
[math]S_2=\{s,o,p\},T=\{q,r,t\}[/math] [math]c(o,q)+c(p,r)=3+2=5[/math]
[math]S_3=\{s,o,p,q,r\},T=\{t\}[/math] [math]c(q,t)+c(r,t)=2+3=5[/math]

Anmerkung: [math]S_4=\{s,o,p,r\},T=\{q,t\}[/math] ist kein minimaler Schnitt, obwohl [math](o,q)[/math] und [math](r,t)[/math] voll genutzt werden; denn es gibt im Residualnetzwerk [math]G_f[/math] noch eine Kante (r,q) der Restkapazität [math]c_f(r,q) = c(r,q)-f(r,q)=0-(-1)=1[/math].

Algorithmus zum Finden minimaler Schnitte

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.

[math]G=(V,E)[/math] ein endlicher gerichteter Graph mit einer Quelle [math]s[/math], einer Senke [math]t[/math] und jede Kante habe eine nichtnegative Kapazität.
findeKantenEinesMinCut([math]G[/math])
1  [math]G_f\leftarrow[/math]Residualnetzwerk([math]G[/math])
2  [math]S\leftarrow\emptyset[/math]
3  [math]T\leftarrow\emptyset[/math]
4  Für jeden Knoten [math]v\in V[/math]
5   Wenn Pfad([math]s,v[/math]) in [math]G_f[/math] existiert
6    dann [math]S\leftarrow S\cup \{v\}[/math]
7    ansonsten [math]T\leftarrow T\cup \{v\}[/math]
8  [math]C\leftarrow\emptyset[/math]
9  Für jede Kante [math]e\in E[/math]
10  Wenn startKnoten([math]e[/math])[math]\in S[/math] und endKnoten([math]e[/math])[math]\in T[/math] liegt
11   dann [math]C\leftarrow C\cup \{e\}[/math]
12 [math]C[/math] ist jetzt die Menge der Kanten für einen minimalen Schnitt

[math]C[/math] würde im oberen Beispiel die Schnittkanten von [math]S_1[/math] enthalten.

Weblinks

Literatur

Einzelnachweise

  1. L.R. Ford Jr., D.R Fulkerson: Maximal flow through a network. In: Canad. J. Math.. 8, 1956, S. 399-404. doi:10.4153/CJM-1956-045-5 .
  2. P. Elias, A. Feinstein, C.E. Shannon: Note on Maximum Flow Through a Network. In: IRE Trans. on Information Theory, IT. 2, Nr. 4, 1956, S. 117-119. doi:10.1109/TIT.1956.1056816 .

Kategorien: Satz (Graphentheorie)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Max-Flow-Min-Cut-Theorem (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.