Analyzing the Algorithm. Flows and Cuts. Our next goal is to show that the flow that is returned by the Ford-Fulkerson Algorithm, has the maximum possible value of any flow in G. To make progress toward this goal, we look at the way in which the structure of the flow network places upper bounds on the maximum value of an s-t flow. We use the notion of a cut to develop a much more general means of placing upper bounds on the maximum-flow value. An s-t cut is a partition (A,B) of the vertex set V, so that s in A, t in B. Its capacity which will be denoted by c(A,B), is simply the sum of the capacities of all the edges out of A. The flow value is the total amount that leaves A minus the total amount that “swirls back” into A.

Analyzing the Algorithm: Max-Flow Equals Min-Cut We want to show that the flow returned by the Algorithm has the maximum possible value of any flow in G. We exhibit an s-t cut for which the maximum flow is equal to the minimum capacity for that cut. The Ford-Fulkerson Algorithm terminates when the flow f has no s-t path in the residual graph Gf. If f is an s-t flow such that there is no s-t path in the residual graph Gf, then there is an s-t cut in G for which the maximum value of flow equals the minimum capacity of its cut. Proof on page 349.

The flow returned by the Ford-Fulkerson Algorithm is a maximum flow and we can compute an s-t cut of minimum capacity in O(m) time. the Max-Flow Min-Cut Theorem states that in every flow netwrok, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut.

Further Analysis: Integer-valued Flows. If all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer. This does not claim that every maximum flow is integer-valued, only some. we used crucially the fact that capacities should be integers. The value of our flow keeps increasing by atleast 1 in every step. With real numbers as our capacities, we should be concerned that the value of our flow keeps increasing, but in increments that become arbitrarily smaller and smaller, hence we have no guarantee of the While loop terminating. With pathological choices for the augmenting path, the Ford-Fulkerson Algorithm with real-valued capacities can run forever. But real-valued capacities do not make the Max-Flow Min-Cut Theorem false.

This section was not as conceptual difficult as the previous one, and it was easy to read through. I give it a scale of 8/10.