《网络流和匹配》ppt课件

《《网络流和匹配》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

Chapter8:NetworkFlowwsvutz3/31/91/13/34/74/63/51/13/52/2c10/4/20211NetworkFlow OutlineandReadingFlowNetworksFlow(§8.1.1)Cut(§8.1.2)MaximumflowAugmentingPath(§8.2.1)MaximumFlowandMinimumCut(§8.2.1)Ford-Fulkerson’sAlgorithm(§8.2.2-8.2.3)Sections§8.2.4-8.5onMatchingandMinimumFlowareoptional.10/4/20212NetworkFlow FlowNetworkAflownetwork(orjustnetwork)NconsistsofAweighteddigraphGwithnonnegativeintegeredgeweights,wheretheweightofanedgeeiscalledthecapacityc(e)ofeTwodistinguishedvertices,sandtofG,calledthesourceandsink,respectively,suchthatshasnoincomingedgesandthasnooutgoingedges.Example:wsvutz391376515210/4/20213NetworkFlow FlowAflowfforanetworkNisisanassignmentofanintegervaluef(e)toeachedgeethatsatisfiesthefollowingproperties:CapacityRule:Foreachedgee,0f(e)c(e)ConservationRule:Foreachvertexvs,twhereE-(v)andE+(v)aretheincomingandoutgoingedgesofv,resp.Thevalueofaflowf,denoted|f|,isthetotalflowfromthesource,whichisthesameasthetotalflowintothesinkExample:wsvutz3/32/91/11/33/72/64/51/13/52/210/4/20214NetworkFlow MaximumFlowAflowforanetworkNissaidtobemaximumifitsvalueisthelargestofallflowsforNThemaximumflowproblemconsistsoffindingamaximumflowforagivennetworkNApplicationsHydraulicsystemsElectricalcircuitsTrafficmovementsFreighttransportationwsvutz3/32/91/11/33/72/64/51/13/52/2wsvutz3/32/91/13/33/74/64/51/13/52/2Flowofvalue8=2+3+3=1+3+4Maximumflowofvalue10=4+3+3=3+3+410/4/20215NetworkFlow CutAcutofanetworkNwithsourcesandsinktisapartitionc=(Vs,Vt)oftheverticesofNsuchthatsVsandtVtForwardedgeofcutc:origininVsanddestinationinVtBackwardedgeofcutc:origininVtanddestinationinVsFlowf(c)acrossacutc:totalflowofforwardedgesminustotalflowofbackwardedgesCapacityc(c)ofacutc:totalcapacityofforwardedgesExample:c(c)=24f(c)=8wsvutz3913765152cwsvutz3/32/91/11/33/72/64/51/13/52/2c10/4/20216NetworkFlow FlowandCutLemma:Theflowf(c)acrossanycutcisequaltotheflowvalue|f|Lemma:Theflowf(c)acrossacutcislessthanorequaltothecapacityc(c)ofthecutTheorem:Thevalueofanyflowislessthanorequaltothecapacityofanycut,i.e.,foranyflowfandanycutc,wehave|f|c(c)wsvutz3/32/91/11/33/72/64/51/13/52/2c1c2c(c1)=12=6+3+1+2c(c2)=21=3+7+9+2|f|=810/4/20217NetworkFlow AugmentingPathConsideraflowfforanetworkNLetebeanedgefromutov:Residualcapacityofefromutov:Df(u,v)=c(e)-f(e)Residualcapacityofefromvtou:Df(v,u)=f(e)LetpbeapathfromstotTheresidualcapacityDf(p)ofpisthesmallestoftheresidualcapacitiesoftheedgesofpinthedirectionfromstotApathpfromstotisanaugmentingpathifDf(p)>0wsvutz3/32/91/11/32/72/64/50/12/52/2pDf(s,u)=3Df(u,w)=1Df(w,v)=1Df(v,t)=2Df(p)=1|f|=710/4/20218NetworkFlow FlowAugmentationLemma:LetpbeanaugmentingpathforflowfinnetworkN.ThereexistsaflowfforNofvalue|f|=|f|+Df(p)Proof:WecomputeflowfbymodifyingtheflowontheedgesofpForwardedge:f(e)=f(e)+Df(p)Backwardedge:f(e)=f(e)-Df(p)wsvutz3/32/91/11/32/72/64/50/12/52/2pDf(p)=1wsvutz3/32/90/12/32/72/64/51/13/52/2p|f|=7|f|=810/4/20219NetworkFlow Ford-Fulkerson’sAlgorithmInitially,f(e)=0foreachedgeeRepeatedlySearchforanaugmentingpathpAugmentbyDf(p)theflowalongtheedgesofpAspecializationofDFS(orBFS)searchesforanaugmentingpathAnedgeeistraversedfromutovprovidedDf(u,v)>0AlgorithmFordFulkersonMaxFlow(N)foralleG.edges()setFlow(e,0)whileGhasanaugmentingpathp{computeresidualcapacityDofp}Dforalledgesep{computeresidualcapacitydofe}ifeisaforwardedgeofpdgetCapacity(e)-getFlow(e)else{eisabackwardedge}dgetFlow(e)ifd