第08章网络流和匹配NetworkFlows.ppt

4/11/2019 10:12 AM,Network Flow,1,Chapter 8: Network Flow,w,s,v,u,t,z,3/3,1/9,1/1,3/3,4/7,4/6,3/5,1/1,3/5,2/2,c,4/11/2019 10:12 AM,Network Flow,2,Outline and Reading,Flow Networks Flow (§8.1.1) Cut (§8.1.2) Maximum flow Augmenting Path (§8.2.1) Maximum Flow and Minimum Cut (§8.2.1) Ford-Fulkersons Algorithm (§8.2.2-8.2.3) Sections §8.2.4-8.5 on Matching and Minimum Flow are optional.,4/11/2019 10:12 AM,Network Flow,3,Flow Network,A flow network (or just network) N consists of A weighted digraph G with nonnegative integer edge weights, where the weight of an edge e is called the capacity c(e) of e Two distinguished vertices, s and t of G, called the source and sink, respectively, such that s has no incoming edges and t has no outgoing edges. Example:,w,s,v,u,t,z,3,9,1,3,7,6,5,1,5,2,4/11/2019 10:12 AM,Network Flow,4,Flow,A flow f for a network N is is an assignment of an integer value f(e) to each edge e that satisfies the following properties: Capacity Rule: For each edge e, 0 f (e) c(e) Conservation Rule: For each vertex v s,t where E-(v) and E+(v) are the incoming and outgoing edges of v, resp. The value of a flow f , denoted |f|, is the total flow from the source, which is the same as the total flow into the sink Example:,w,s,v,u,t,z,3/3,2/9,1/1,1/3,3/7,2/6,4/5,1/1,3/5,2/2,4/11/2019 10:12 AM,Network Flow,5,Maximum Flow,A flow for a network N is said to be maximum if its value is the largest of all flows for N The maximum flow problem consists of finding a maximum flow for a given network N Applications Hydraulic systems Electrical circuits Traffic movements Freight transportation,w,s,v,u,t,z,3/3,2/9,1/1,1/3,3/7,2/6,4/5,1/1,3/5,2/2,w,s,v,u,t,z,3/3,2/9,1/1,3/3,3/7,4/6,4/5,1/1,3/5,2/2,Flow of value 8 = 2 + 3 + 3 = 1 + 3 + 4,Maximum flow of value 10 = 4 + 3 + 3 = 3 + 3 + 4,4/11/2019 10:12 AM,Network Flow,6,Cut,A cut of a network N with source s and sink t is a partition c = (Vs,Vt) of the vertices of N such that s Vs and t Vt Forward edge of cut c: origin in Vs and destination in Vt Backward edge of cut c: origin in Vt and destination in Vs Flow f(c) across a cut c: total flow of forward edges minus total flow of backward edges Capacity c(c) of a cut c: total capacity of forward edges Example: c(c) = 24 f(c) = 8,w,s,v,u,t,z,3,9,1,3,7,6,5,1,5,2,c,w,s,v,u,t,z,3/3,2/9,1/1,1/3,3/7,2/6,4/5,1/1,3/5,2/2,c,4/11/2019 10:12 AM,Network Flow,7,Flow and Cut,Lemma: The flow f(c) across any cut c is equal to the flow value |f| Lemma: The flow f(c) across a cut c is less than or equal to the capacity c(c) of the cut Theorem: The value of any flow is less than or equal to the capacity of any cut, i.e., for any flow f and any cut c, we have |f| c(c),w,s,v,u,t,z,3/3,2/9,1/1,1/3,3/7,2/6,4/5,1/1,3/5,2/2,c1,c2,c(c1) = 12 = 6 + 3 + 1 + 2 c(c2) = 21 = 3 + 7 + 9 + 2 |f| = 8,4/11/2019 10:12 AM,Network Flow,8,Augmenting Path,Consider a flow f for a network N Let e be an edge from u to v: Residual capacity of e from u to v: Df(u, v) = c(e) - f (e) Residual capacity of e from v to u: Df(v, u) = f (e) Let p be a path from s to t The residual capacity Df(p) of p is the smallest of the residual capacities of the edges of p in the direction from s to t A path p from s to t is an augmenting path if Df(p) 0,w,s,v,u,t,z,3/3,2/9,1/1,1/3,2/7,2/6,4/5,0/1,2/5,2/2,p,Df(s,u) = 3 Df(u,w) = 1 Df(w,v) = 1 Df(v,t) = 2 Df(p) = 1 |f| = 7,4/11/2019 10:12 AM,Network Flow,9,Flow Augmentation,Lemma: Let p be an augmenting path for flow f in network N. There exists a flow f for N of value | f | = |f | + Df(p) Proof: We compute flow f by modifying the flow on the edges of p Forward edge: f (e) = f(e) + Df(p) Backward edge: f (e) = f(e) - Df(p),Df(p) = 1,| f | = 7,| f | = 8,4/11/2019 10:12 AM,Network Flow,10,Ford-Fulkersons Algorithm,Initially, f(e) = 0 for each edge e Repeatedly Search for an augmenting path p Augment by Df(p) the flow along the edges of p A specialization of DFS (or BFS) searches for an augmenting path An edge e is traversed from u to v provided Df(u, v) 0,Algorithm FordFulkersonMaxFlow(N) for all e G.edges() setFlow(e, 0) while G has an augmenting path p compute residual capacity D of p D for all edges e p compute residual capacity d of e if e is a forward edge of p d getCapacity(e) - getFlow(e) else e is a backward edge d getFlow(e) if d D D d augment flow along p for all edges e p if e is a forward edge of p setFlow(e, getFlow(e) + D) else e is a backward edge setFlow(e, getFlow(e) - D),4/11/2019 10:12 AM,Network Flow,11,Max-Flow and Min-Cut,Termination of Ford-Fulkersons algorithm There is no augmenting path from s to t with respect to the current flow f Define Vs set of vertices reachable from s by augmenting paths Vt set of remaining vertices Cut c = (Vs,Vt) has capacity c(c) = |f| Forward edge: f(e) = c(e) Backward edge: f(e) = 0 Thus, flow f has maximum value and cut c has minimum capacity,w,s,v,u,t,z,3/3,1/9,1/1,3/3,4/7,4/6,3/5,1/1,3/5,2/2,c,Theorem: The value of a maximum flow is equal to the capacity of a minimum cut,c(c) = | f | = 10,4/11/2019 10:12 AM,Network Flow,12,Example (1),w,s,v,u,t,z,0/3,0/9,0/1,0/3,1/7,0/6,0/5,1/1,1/5,0/2,w,s,v,u,t,z,1/3,0/9,0/1,0/3,1/7,0/6,1/5,0/1,1/5,1/2,w,s,v,u,t,z,1/3,0/9,1/1,0/3,2/7,1/6,1/5,0/1,1/5,1/2,w,s,v,u,t,z,2/3,0/9,0/1,1/3,2/7,1/6,1/5,0/1,1/5,1/2,4/11/2019 10:12 AM,Network Flow,13,Example (2),w,s,v,u,t,z,2/3,0/9,0/1,3/3,2/7,3/6,1/5,0/1,1/5,1/2,w,s,v,u,t,z,3/3,1/9,0/1,3/3,2/7,3/6,2/5,0/1,1/5,1/2,w,s,v,u,t,z,3/3,1/9,1/1,3/3,3/7,4/6,2/5,0/1,1/5,1/2,w,s,v,u,t,z,3/3,1/9,1/1,3/3,4/7,4/6,3/5,1/1,3/5,2/2,two steps,4/11/2019 10:12 AM,Network Flow,14,Analysis,In the worst case, Ford-Fulkersons algorithm performs |f*| flow augmentations, where f* is a maximum flow Example The augmenting paths found alternate between p1 and p2 The algorithm performs 100 augmentations Finding an augmenting path and augmenting the flow takes O(n + m) time The running time of Ford-Fulkersons algorithm is O(|f*|(n + m),t,s,v,u,1/1,1/50,0/50,1/50,0/50,t,s,v,u,0/1,1/50,1/50,1/50,1/50,p1,p2,