Sidetrack: Maxflow and Mincut (cont)
Max-flow Min-cut Theorem.
In a flow network G the following conditions are equivalent:
- f is a maximum flow in G
- the residual network G relative to f contains no augmenting path
- value of flow f = weight of some minimum cut (S,T) of G
|