MAX-FLOW MIN-CUT THEOREM

(Redirected from Max flow min cut theorem)
The 'max-flow min-cut theorem' is a statement in optimization theory about maximal flows in flow networks. It derives from Menger's theorem. It states that:
:''The maximal amount of flow is equal to the capacity of a minimal cut.''
In layman terms, the theorem states that the maximum flow in a network is dictated by its bottleneck. Between any two nodes, the quantity of material flowing from one to the other cannot be greater than the weakest set of links somewhere between the two nodes.

Contents

Definition

Example

History

See also

External links

References

Definition

Suppose $G(V,E)$ is a finite directed graph and every edge $(u,v)$ has a capacity $c(u,v)$ (a non-negative real number). Further assume two vertices, the source $s$ and the sink $t$, have been distinguished.
Main articles: Cut (graph theory)

A 'cut' is a split of the nodes into two sets $S$ and $T$, such that $s$ is in $S$ and $t$ is in $T$. Hence there are
:$2^\{|V|-2\},$
possible cuts in a graph. The capacity of a cut $(S,T)$ is
:$c(S,T)\; =\; sum\_\{u\; in\; S,\; v\; in\; T\; |\; (u,v)\; in\; E\}\; c(u,v)$,
the sum of the capacity of all the edges crossing the cut, from the region $S$ to the region $T$.
The following three conditions are equivalent:
# $f$ is a maximum flow in $G$
# The residual network $G\_f$ contains no augmenting paths.
# $|f|\; =\; c(S,T)$ for some cut $(S,T)$.
Proof Sketch: If there is an augmenting path, we can send flow along it, and get a greater flow, hence it cannot be maximal, and vice versa. If there is no augmenting path, divide the graph into $S$, the nodes reachable from $s$ in the residual network, and $T$, those not reachable. Then $c(S,T)$ must be 0. If it is not, there is an edge $(u,v)$ with $c(u,v)\; >\; 0$. But then $v$ is reachable from $s$, and cannot be in $T$.
In particular this proves that $mathrm\{max\; flow\}\; geq\; mathrm\{min\; cut\}$, because a minimal cut is smaller or equal to the cut corresponding to our $mathrm\{max\; flow\}$.
Then we have $mathrm\{min\; cut\}\; geq\; mathrm\{max\; flow\}$. If we have a flow $f$ for a given graph $G$, removing an edge $(u,\; v)$ of capacity $c$ changes $f$ in at least $f\; -\; c$, because no more than a capacity of $c$ can be used by the flow $f$. But if we remove all edges cut by a given minimal cut $c0$, we get a flow $0$, whatever the flow $f$ we have at first. So for any flow $f$, in particular if $f$ is a max flow. Which shows .

Example

Given to the right is a network with nodes $V=\{s,o,p,q,r,t\}$, and a total flow from the source $s$ to the sink $t$ of 5, which is maximal in this network. (Incidentally, this is the only maximal flow you can assign to this network.)
There are three minimal cuts in this network:
:{|class="wikitable"
! Cut || Capacity
|-
| $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$
|}
Notice that $S=\{s,o,p,r\},T=\{q,t\}$ is not a minimal cut, even though both $(o,q)$ and $(r,t)$ are saturated in the given flow. This is because in the residual network $G\_f$, there is an edge (r,q) with capacity $c\_f(r,q)\; =\; c(r,q)-f(r,q)=0-(-1)=1$.

History

The theorem was proved by P. Elias, A. Feinstein, and C.E. Shannon in 1956, and independently also by L.R. Ford, Jr. and D.R. Fulkerson in the same year. Determining maximum flows is a special kind of linear programming problem, and the max flow min cut theorem can be seen as a special case of the duality theorem for linear programming.

See also

★ Ford-Fulkerson algorithm

★ Karger's algorithm

External links

★ A review of current literature on computing maximum flows

★ Max-Flow Min-Cut Animation

★ Max-Flow Problem: Ford-Fulkerson Algorithm

References

★ P. Elias, A. Feinstein, and C. E. Shannon. Note on maximum flow through a network. IRE Transactions on Information Theory IT-2, 117--119, 1956.

★ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 26: Maximum Flow, pp.643–700.