资源描述：
《麻省理工大学算法导论lecture22》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、IntroductiontoAlgorithms6.046J/18.401J/SMA5503Lecture22Prof.CharlesE.LeisersonFlownetworksDefinition.AflownetworkisadirectedgraphG=(V,E)withtwodistinguishedvertices:asourcesandasinkt.Eachedge(u,v)∈Ehasanonnegativecapacityc(u,v).If(u,v)∉E,thenc(u,v)=0.Example:233113ss32tt223©2001byCharlesE.
2、LeisersonIntroductiontoAlgorithmsDay38L22.2FlownetworksDefinition.ApositiveflowonGisafunctionp:V×V→Rsatisfyingthefollowing:•Capacityconstraint:Forallu,v∈V,0≤p(u,v)≤c(u,v).•Flowconservation:Forallu∈V–{s,t},∑p(u,v)−∑p(v,u)=0.v∈Vv∈VThevalueofaflowisthenetflowoutofthesource:∑p(s,v)−∑p(v,s).v∈V
3、v∈V©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay38L22.3Aflowonanetworkpositivecapacityflow2:21:32:30:11:31:1ss2:31:2tt1:22:2u2:3Flowconservation(likeKirchoff’scurrentlaw):•Flowintouis2+1=3.•Flowoutofuis0+1+2=3.Thevalueofthisflowis1–0+2=3.©2001byCharlesE.LeisersonIntroductiontoAlgori
4、thmsDay38L22.4Themaximum-flowproblemMaximum-flowproblem:GivenaflownetworkG,findaflowofmaximumvalueonG.2:22:32:30:10:31:1ss2:31:2tt2:22:23:3Thevalueofthemaximumflowis4.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay38L22.5FlowcancellationWithoutlossofgenerality,positiveflowgoeseitherfr
5、omutov,orfromvtou,butnotboth.vvvvNetflowfrom2:31:21:30:2utovinbothcasesis1.uuuuThecapacityconstraintandflowconservationarepreservedbythistransformation.INTUITION:Viewflowasarate,notaquantity.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay38L22.6AnotationalsimplificationIDEA:Workwithth
6、enetflowbetweentwovertices,ratherthanwiththepositiveflow.Definition.A(net)flowonGisafunctionf:V×V→Rsatisfyingthefollowing:•Capacityconstraint:Forallu,v∈V,f(u,v)≤c(u,v).•Flowconservation:Forallu∈V–{s,t},∑f(u,v)=0.Onesummationv∈Vinsteadoftwo.•Skewsymmetry:Forallu,v∈V,f(u,v)=–f(v,u).©2001byCh
7、arlesE.LeisersonIntroductiontoAlgorithmsDay38L22.7EquivalenceofdefinitionsTheorem.Thetwodefinitionsareequivalent.Proof.(⇒)Letf(u,v)=p(u,v)–p(v,u).•Capacityconstraint:Sincep(u,v)≤c(u,v)andp(v,u)≥0,wehavef(u,v)≤c(u,v).•Flowconservation:∑f(u,v)=∑(p(u,v)−p(v,u))v∈
