《《网络流和匹配》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《网络流和匹配》PPT课件.ppt（14页珍藏版）》请在三一办公上搜索。
1、7/29/2023,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,7/29/2023,Network Flow,2,Outline and Reading,Flow NetworksFlow(8.1.1)Cut(8.1.2)Maximum flowAugmenting Path(8.2.1)Maximum Flow and Minimum Cut(8.2.1)Ford-Fulkersons Algorithm()Sections 8.2.4-8.5 on M
2、atching and Minimum Flow are optional.,7/29/2023,Network Flow,3,Flow Network,A flow network(or just network)N consists ofA 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
3、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,7/29/2023,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 eac
4、h 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
5、/2,7/29/2023,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 NThe maximum flow problem consists of finding a maximum flow for a given network NApplicationsHydraulic systemsElectrical circuitsTraffic movementsFreight transportation
6、,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,7/29/2023,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
7、s Vs and t VtForward edge of cut c:origin in Vs and destination in VtBackward edge of cut c:origin in Vt and destination in VsFlow f(c)across a cut c:total flow of forward edges minus total flow of backward edgesCapacity c(c)of a cut c:total capacity of forward edgesExample:c(c)=24f(c)=8,w,s,v,u,t,z
8、,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,7/29/2023,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 cutTheorem:The value of any flow is l
9、ess 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+2c(c2)=21=3+7+9+2|f|=8,7/29/2023,Network Flow,8,Augmenting Path,Consider a flow f for a network NLet e be an edge from u to v:Residua
10、l 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 tThe residual capacity Df(p)of p is the smallest of the residual capacities of the edges of p in the direction from s to tA path p from s to t is an augmenting path if Df(p)0,w,s,v,u
11、,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)=3Df(u,w)=1Df(w,v)=1Df(v,t)=2Df(p)=1|f|=7,7/29/2023,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 e
12、dges of pForward edge:f(e)=f(e)+Df(p)Backward edge:f(e)=f(e)-Df(p),Df(p)=1,|f|=7,|f|=8,7/29/2023,Network Flow,10,Ford-Fulkersons Algorithm,Initially,f(e)=0 for each edge eRepeatedlySearch for an augmenting path pAugment by Df(p)the flow along the edges of pA specialization of DFS(or BFS)searches for
13、 an augmenting pathAn 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 pd getCapacity(e)-g
14、etFlow(e)else e is a backward edge d getFlow(e)if d DD d augment flow along p for all edges e pif e is a forward edge of psetFlow(e,getFlow(e)+D)else e is a backward edge setFlow(e,getFlow(e)-D),7/29/2023,Network Flow,11,Max-Flow and Min-Cut,Termination of Ford-Fulkersons algorithmThere is no augmen
15、ting path from s to t with respect to the current flow fDefineVsset of vertices reachable from s by augmenting pathsVt set of remaining vertices Cut c=(Vs,Vt)has capacityc(c)=|f|Forward edge:f(e)=c(e)Backward edge:f(e)=0Thus,flow f has maximum value and cut c has minimum capacity,w,s,v,u,t,z,3/3,1/9
16、,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,7/29/2023,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/
17、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,7/29/2023,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
18、/5,1/1,3/5,2/2,two steps,7/29/2023,Network Flow,14,Analysis,In the worst case,Ford-Fulkersons algorithm performs|f*|flow augmentations,where f*is a maximum flowExampleThe augmenting paths found alternate between p1 and p2The algorithm performs 100 augmentationsFinding an augmenting path and augmenting the flow takes O(n+m)timeThe 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,
