Unformatted text preview:

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∈Xv∈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

UA CSC 445 - Network Flow

Download Network Flow
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Network Flow and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Network Flow 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?