Max-flow min-cut

From Algowiki
Jump to: navigation, search

Max-flow min-cut theorem

Let , , and for let and be real values such that and is a feasible -flow. Then the following three statements are equivalent:

  1. The flow value of is maximum among all feasible -flows.
  2. There is a saturated cut.
  3. There is no flow-augmenting path from to .

Proof

First suppose there is no flow-augmenting path from to . Let denote the set of all nodes reachable from via flow-augmenting paths, and let . Then we have and . Obviously, is saturated.

Next suppose there is a saturated cut. No flow can carry more units of flow value from to than the capacity of any -cut allows. Consequently, is maximum.

Finally suppose is maximum. Clearly, then a flow-augmenting path from to cannot exist.