====== 7.2 Maximum Flows and Minimum Cuts in a Network ====== \\ ===== Analyzing the Algorithm: Flows and Cuts ===== * **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)\\ \\ ===== Analyzing the Algorithm:Max-Flow Equals Min-Cut ===== \\ * 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