[prev] 43 [next]

Sidetrack: Maxflow and Mincut (cont)

Max-flow Min-cut Theorem.
In a flow network G the following conditions are equivalent:

  1. f is a maximum flow in G
  2. the residual network G relative to f contains no augmenting path
  3. value of flow f = weight of some minimum cut (S,T) of G