7.2 Maximum Flows and Minimum Cuts in a Network

• Cuts: An s-t cut is a partition (A, B) of V with s ∈ A and t ∈ B
• The Capacity of a cut(A,B) is: The sum of all the capacities of all edges out of A: c(A,B) = ∑_{e out of A} C(e)
• v(f) = f^out(A) - fⁱⁿ(A)
• v(f) ≤ c(A,B)
  

• Let f‾ denote the flow returned by the Ford-Fulkerson Algorithm
• Let an s-t cut (A^*,B^*) for which v(f^- = c(A^*,B^*)
• Thus f^- has the maximum value of any flow, and (A^*,B^*) has the minimum capacity of any s-t cut in G.
  
• The flow f^- returned by the Ford-Fulkerson Algorithm is a maximum flow
• Given a flow f of maximum value, an s-t cut can be computed of minimum capacity can be computed in O(m) time
• In every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut
• 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
  

I give this section an 8/10