Chapter 7.2: Maximum Flows and Minimum Cuts in a Network

Sometimes, C, the sum of the capacities out of the source node s, is a useful upper bound, but often times it is not. We will now use the notion of a cut to develop a much more general means of placing upper bounds on a maximum-flow value. The capacity of a cut (A,B), is the sum of the capacity of all edges out of A.

Let f be any s-t flow, and (A,B) any s-t cut. Then v(f) = fout(A) - Fin(A).

The value of every flow is upper-bounded by the capacity of every cut. The flow f returned by the Ford-Fulkerson algorithm is a maximum flow. Given a flow f of maximum value, we can compute an s-t cut of minimum capacity in O(m) time.

This section is mostly proofs, so if I need help understanding how this algorithm works technically, I should visit page 350. This one was not so interesting for me. 7/10.