Max-Flow-Min-Cut-Theorem

Max-Flow-Min-Cut-Theorem

Das Max-Flow-Min-Cut-Theorem ist ein Satz der Graphentheorie über den maximalen Fluss in Flussnetzwerken. Er leitet sich aus Mengers Theorem ab. Er besagt:

Der maximale Fluss im Netzwerk hat genau den Wert dessen minimalen Schnitts.

Anders gesagt, wird der Fluss durch ein Netzwerk durch dessen Flaschenhals beschränkt - auch wenn an anderen Stellen ein größerer Fluss möglich wäre, so ist der Gesamtfluss durch die Engstelle limitiert.

Inhaltsverzeichnis

Definitionen

Sei G(V,E) ein endlicher gerichteter Graph und jede Kante (u,v) habe eine zugewiesene nichtnegative Kapazität c(u,v). Des Weiteren gibt es eine Quelle s, in der der Fluss beginnt, und eine Senke t, in der er endet.

Ein Schnitt ist eine Aufteilung der Knoten in zwei disjunkte Teilmengen S und T. Die Kapazität eines Schnittes (S,T) ist die Summe aller Kantenkapazitäten von S nach T, also c(S,T) = \sum_{u \in S, v \in T | (u,v) \in E} c(u,v).

Satz

Die folgenden drei Aussagen sind äquivalent:

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

Beweisskizze

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

Beispiel

Ein Netzwerk mit maximalem Fluss und drei minimalen Schnitten

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

Es gibt drei minimale Schnitte in diesem Netzwerk:

Schnitt Kapazität
S = {s,p},T = {o,q,r,t} c(s,o) + c(p,r) = 3 + 2 = 5
S = {s,o,p},T = {q,r,t} c(o,q) + c(p,r) = 3 + 2 = 5
S = {s,o,p,q,r},T = {t} c(q,t) + c(r,t) = 2 + 3 = 5

Anmerkung: S = {s,o,p,r},T = {q,t} ist kein minimaler Schnitt, obwohl (o,q) und (r,t) voll genutzt werden; denn es gibt im Residualnetzwerk Gf noch eine Kante (r,q) der Restkapazität cf(r,q) = c(r,q) − f(r,q) = 0 − ( − 1) = 1.

Geschichte

Das Theorem wurde 1956 von Peter Elias, Amiel Feinstein und Claude Elwood Shannon bewiesen, und unabhängig davon auch von Lester Randolph Ford junior und Delbert Ray Fulkerson im selben Jahr.

Siehe auch

Weblinks

Einzelnachweise


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Max-flow min-cut theorem — In optimization theory, the max flow min cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the minimum capacity which when removed in a specific way from the network causes the… …   Wikipedia

  • Cut (graph theory) — In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are… …   Wikipedia

  • Flow network — In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a… …   Wikipedia

  • Menger's theorem — In the mathematical discipline of graph theory and related areas, Menger s theorem is a basic result about connectivity in finite undirected graphs. It was proved for edge connectivity and vertex connectivity by Karl Menger in 1927. The edge… …   Wikipedia

  • Maximum flow problem — An example of a flow network with a maximum flow. The source is s, and the sink t. The numbers denote flow and capacity. In optimization theory, the maximum flow problem is to find a feasible flow through a single source, single sink flow network …   Wikipedia

  • König's theorem (graph theory) — In the mathematical area of graph theory, König s theorem describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. Setting A graph is bipartite if its vertices can be partitioned into …   Wikipedia

  • Marriage theorem — In mathematics, the marriage theorem (1935), usually credited to mathematician Philip Hall, is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of subsets.Formally, let S = { S …   Wikipedia

  • Minimum cut — In graph theory, a minimum cut of a graph is a cut whose cutset has the smallest number of elements (unweighted case) or smallest sum of weights possible. Several algorithms exist to find minimum cuts. For a graph G = (V, E), the problem can be… …   Wikipedia

  • Hall's marriage theorem — In mathematics, Hall s marriage theorem is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of finite sets. It was proved by Philip Hall (1935). Contents 1 Definitions and …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”