Max-flow min-cut

From Algowiki
Jump to: navigation, search

Max-flow min-cut theorem

Let [math]G=(V,A)[/math], [math]s,t\in V[/math], and for [math]a\in A[/math] let [math]u(a)[/math] and [math]f(a)[/math] be real values such that [math]0\leq f(a)\leq u(a)[/math] and [math]f[/math] is a feasible [math](s,t)[/math]-flow. Then the following three statements are equivalent:

  1. The flow value of [math]f[/math] is maximum among all feasible [math](s,t)[/math]-flows.
  2. There is a saturated cut.
  3. There is no flow-augmenting path from [math]s[/math] to [math]t[/math].

Proof

First suppose there is no flow-augmenting path from [math]s[/math] to [math]t[/math]. Let [math]S[/math] denote the set of all nodes reachable from [math]s[/math] via flow-augmenting paths, and let [math]T:=V\setminus S[/math]. Then we have [math]s\in S[/math] and [math]t\in T[/math]. Obviously, [math](S,T)[/math] is saturated.

Next suppose there is a saturated cut. No flow [math]f'[/math] can carry more units of flow value from [math]s[/math] to [math]t[/math] than the capacity of any [math](s,t)[/math]-cut allows. Consequently, [math]f[/math] is maximum.

Finally suppose [math]f[/math] is maximum. Clearly, then a flow-augmenting path from [math]s[/math] to [math]t[/math] cannot exist.