University:
Amherst College
Course:
COSC 311 | Algorithms
Academic year:

2023
Views:

200

Pages:

3
Author:

Pompanin8za

Part I: s-t Cuts An s-t cut in a graph G is a partition of the vertices in G into sets (A, B) such that s ∈ A and t ∈ B. The capacity of an s-t cut (A, B), denoted c(A, B), is the sum of the capacities of all edges out of A: X c(A, B) = c(e) e out of A Here is a graph (numbers in boxes represent the flow along an edge, “unadorned” numbers represent the edge capacity): 1) Let A = {s, w, y}, B = {x, z, t}. What is the capacity of the cut? We have defined the value of a flow f to be the total amount of flow leaving s: X v(f ) = f out (s) = f (s, u) (s,u) 2) In the above graph, what is the value of the flow leaving s? The flow across a cut (A, B) is defined to be the net amount of flow leaving A; that is, the total amount of flow leaving A minus the total amount of flow entering A, or f out (A) − f in (A). 3) Let A = {s, w, y}, B = {x, z, t}. What is the value of the flow across this cut? 4) Let A = {s, y, x}, B = {w, z, t}. What is the value of the flow across this cut? 5) What can you say, in general, about the value of a flow f with respect to the flow across any cut (A, B)? Why is this true? (F) (write an expression in this box that says something about v(f )) Make sure everyone in your group understands what is going on. At this point, ask me for the next page. Part II: An Idea for a Cut Claim 1. If f is any valid flow, and (A, B) is any s-t cut, then v(f ) ≤ c(A, B). 6) Prove this claim in five lines, starting with the expression you wrote in (F). We have now shown that every s-t cut gives an upper bound on the value of any valid flow. If we can show that Ford-Fulkerson returns a flow fˆ with value v(fˆ) = c(A∗ , B ∗ ) for some cut (A∗ , B ∗ ), then we will know that fˆ is a max flow. Suppose we have a graph G and a flow f for which there is no s-t path in the residual graph Gf . Consider the following idea for a cut: Let A∗ be the set of nodes v that are reachable from s in the residual graph, and let B ∗ = V − A∗ ). 7) How do we know that (A∗ , B ∗ ) is in fact an s-t cut? 8) Suppose edge e = (u, v) has u ∈ A∗ and v ∈ B ∗ . What must be the value of f (e)? Why? 9) Suppose edge e = (u, v) has u ∈ B ∗ and v ∈ A∗ . What must be the value of f (e)? Why? 10) Now use (F) to show in four lines that v(f ) = c(A∗ , B ∗ ). At this point, ask me for the next page. Part III: Proving Ford-Fulkerson Finds a Max Flow It’s time to put it all together and prove that Ford-Fulkerson successfully computes a max flow. 11) When does Ford-Fulkerson terminate? In answering this, review what Ford-Fulkerson does, and make sure everyone in your group understands what the algorithm is doing. 12) Consider the cut (A∗ , B ∗ ) as defined in Part II. What must be true about the value of the flow produced by Ford-Fulkerson, fˆ, with respect to (A∗ , B ∗ )? 13) So why is fˆ a max flow? What we have actually shown here is the following key theorem: Theorem 1. [Max-Flow Min-Cut] In every flow network, the maximum value of an s-t flow is equal to the minimum capacity of an s-t cut. This is important because when we solve applied problems, sometimes we are looking for a max flow and sometimes we are looking for a min cut. The Max-Flow Min-Cut Theorem tells us that these always have the same value. 14) Suppose we have computed a max s-t flow f using Ford-Fulkerson. How can we compute a min s-t cut in time O(m), where m is the number of edges in our graph?

Max-flow Min-cut

Related Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock