Introduction to Algorithms, Lecture 22 December 5, 2001© 2001 by Charles E. Leiserson 1CS 445Flow NetworksAlon EfratSlides courtesy of Charles Leiserson with small changes by Carola WenkFlow networksDefinition. A flow network is a directed graph G = (V, E) with two distinguished vertices: a source s and a sink t. Each edge (u, v) ∈ E has a nonnegative capacity c(u, v). If (u, v) ∉ E, then c(u, v) = 0.Example:s t3233 2233121Flow networksDefinition. A positive flow on G is a function p : V × V → satisfying the following: • Capacity constraint: For all u, v ∈ V,0 ≤ p(u, v) ≤ c(u, v).• Flow conservation: For all u ∈ V – {s, t}, 0),(),(=−∈∈VvVvuvpvup.The value of a flow is the net flow out of the source:∈∈−VvVvsvpvsp ),(),(.A flow on a networks t1:32:22:31:12:3 1:21:22:31:30:12:2positive flowcapacityThe value of this flow is 1 – 0 + 2 = 3.Flow conservation• Flow into u is 2 + 1 = 3.• Flow out of u is 0 + 1 + 2 = 3.uThe maximum-flow problems t2:32:22:31:12:3 1:22:23:30:30:12:2The value of the maximum flow is 4.Maximum-flow problem: Given a flow network G, find a flow of maximum value on G.Application: Bipartite Matching. ABA graph G(V,E) is called bipartite if V can be partitioned into two sets V=A∪B, and each edge of E connects a vertex of A to a vertex of B.A matching is a set of edges M of E, where each vertex is adjacent to at most one vertexIntroduction to Algorithms, Lecture 22 December 5, 2001© 2001 by Charles E. Leiserson 2Matching and flow problem ABAdd a vertex s, and connect it to each vertex of A. Add a vertex t, and connect each vertex of B to t.The capacity of all edges is 1.Find max flow. Assume it is an integer flow, so the flow of each edge is either 0 or 1. Each edge of G that carries a flow is in the matching. st1:10:11:11:1Greedy is suboptimal. ABAssume we have already some edges in a (partial ) matching.In order to increase the matching, we might need to cancel edges already in the matching. stFlow cancellationWithout loss of generality, positive flow goes either from u to v, or from v to u, but not both.vu2:3 1:2vu1:3 0:2Net flow from u to v in both cases is 1.The capacity constraint and flow conservation are preserved by this transformation.INTUITION: View flow as a rate, not a quantity.One summation instead of two.A notational simplificationIDEA: Work with the net flow between two vertices, rather than with the positive flow.Definition. A (net) flow on G is a function f : V × V → satisfying the following: • Capacity constraint: For all u, v ∈ V,f(u, v) ≤ c(u, v).• Flow conservation: For all u ∈ V – {s, t}, 0),(=∈Vvvuf.• Skew symmetry: For all u, v ∈ V,f(u, v) = –f (v, u).Equivalence of definitionsTheorem. The two definitions are equivalent.Proof. () Let f(u, v) = p(u, v) – p(v, u).• Capacity constraint: Since p(u, v) ≤ c(u, v) and p(v, u) ≥ 0, we have f(u, v) ≤ c(u, v).• Flow conservation:()∈∈∈∈−=−=VvVvVvVvuvpvupuvpvupvuf),(),(),(),(),(• Skew symmetry:f(u, v) = p(u, v) – p(v, u) = – (p(v, u) – p(u, v))= – f (v, u).Proof (continued)(⇐) Letp(u, v) =f(u, v) if f(u, v) > 0,0 if f(u, v) ≤ 0.• Capacity constraint: By definition, p(u, v) ≥ 0. Since f(u, v) ≤ c(u, v), it follows that p(u, v) ≤ c(u, v).• Flow conservation: If f(u, v) > 0, then p(u, v) – p(v, u) = f (u, v). If f(u, v) ≤ 0, then p(u, v) – p(v, u) = –f(v, u) = f (u, v) by skew symmetry. Therefore,∈∈∈=−VvVvVvvufuvpvup ),(),(),(.Introduction to Algorithms, Lecture 22 December 5, 2001© 2001 by Charles E. Leiserson 3NotationDefinition. The value of a flow f, denoted by |f |, is given by),(),(VsfvsffVv==∈.Implicit summation notation: A set used in an arithmetic formula represents a sum over the elements of the set. • Example — flow conservation:f(u, V) = v∈V f(u,v)= 0 for all u ∈ V – {s, t}.More definitionsLemma f (X, Y) = u∈X v∈Y f(u,v)XYuvVMore properties of flowLemma:1. If X does not contain s nor t, then f (X, V) = 0Proof: f (X, V) = u∈X f(u,V) = u∈X 0.2. If A,B are disjoint sets of vertices, and X is another set, then f (A∪B, X) = f(A,X) +f(B,X) XABNote (property *): f(A,X) = f (A∪B, X) - f(B,X)And more properties of flow…Lemma (Property #):3. For every set X of vertices f (X,X)=0 Proof: f(X,X)= u∈Xv∈X f(u,v), and if f(u,v) appears in the summation, then f(v,u) also appears in the summation, and f(v,u) = -f(u,v). Simple properties of flowTheorem. | f | = f(V, t).Proof.| f | = f (s, V)= f (V, V) – f (V–s, V) (Property *)= f (V, V–s) (Property #)= f (V, t) + f (V, V–s–t) (Case 2)= f (V, t). (Case 1 )Recall: |f|=f(s,V)=v∈X f(s,v)Flow into the sinks t2:32:22:31:11:3 -1:22:23:30:3-2:12:2| f | = f (s, V) = 4 f (V, t) = 4Introduction to Algorithms, Lecture 22 December 5, 2001© 2001 by Charles E. Leiserson 4CutsDefinition. A cut (S, T) of a flow network G =(V, E) is a partition of V such that s ∈ S and t ∈ T. If f is a flow on G, then the flow across the cut isf(S, T).s t2:32:22:31:11:3 0:22:23:30:3-2:12:2∈ S∈ Tf(S, T) = (2 + 2) + (– 2 + 1 – 1 + 2)= 4stAnother characterization of flow valueLemma. For any flow f and any cut (S, T), we have | f | = f (S, T).Proof. f (S, T) = f (S, V) – f (S, S)= f (S, V)= f (s, V) + f (S–s, V)= f (s, V)= | f |.Recall: |f|=f(s,V)=v∈V f(s,v)Capacity of a cutDefinition. The capacity of a cut (S, T) is c(S, T)=u∈S v∈T c(u,v)s t2:32:22:31:11:3 0:22:23:30:30:12:2∈ S∈ Tc(S, T) = (3 + 2) + (1 + 2 + 3)= 11stUpper bound on the maximum flow valueTheorem. The value of any flow no larger than the capacity of any cut: |f| ≤c(S,T) ..),(),(),(),(TScvucvufTSffSu TvSu Tv=≤== ∈ ∈∈ ∈Proof.Residual networkDefinition. Let f be a flow on G = (V, E). The residual network Gf(V, Ef) is the graph with strictly positive residual capacitiescf(u, v) = c(u, v) – f (u, v) > 0.uvG:uv4Gf:Examples:Lemma. |Ef| ≤ 2|E|.0:4uvuv44:4uvuv311:4Augmenting pathsDefinition. Any path from s to t in Gfis an aug-menting path in G with respect to f. The flow value can be increased along an augmenting path p by)},({min)(),(vucpcfpvuf∈=.s3:5G:2:6-5:25:5 2:3t2:5s23Gf:427 21t32cf(p) = 2Ex.:s5:5G:4:6-3:23:50:3t4:5Introduction to Algorithms, Lecture 22 December 5, 2001© 2001 by Charles E. Leiserson 5Example – max matching.ABst.ABst1:10:10:1 0:10:11:11:11111 111Gf:G:Ford-Fulkerson max-flow alg•f [u,
View Full Document