资源描述：
《Notes-network-flow》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、SHEN’SCLASSNOTESChapter26MaximumFlow26.1FlowNetworksDefinition1AflownetworkG=(V,E,C)isadirectedgraphinwhicheveryedge(u,v)ÎEhasanonnegativecapacityc(u,v)³0.Itisassumedthatc(u,v)=0if(u,v)ÏE.Moreover,twovertices,sandt,aredistinguishedinaflownetworktobethesourceandthesinkrespectively.D
2、efinition2LetG=(V,E,C)beaflownetwork.LetsandtbethesourceandsinkofG.AflowinGisareal-valuedfunctionf:V´V®Rthatsatisfiesthefollowingthreeproperties:(1)f(u,v)£c(u,v)forallu,vÎV.(2)f(u,v)=-f(v,u)forallu,vÎV.(3)=0foralluÎV–{s,t}.ThevalueofaflowfisdefinedasF=
3、f
4、=.Definition3Themaximum-flo
5、wproblemistofindaflowforagivenflownetworkthathasthemaximumvalue.Notethat=0meansthatthesumofalloutgoingflowsfromavertexu,eitherpositiveornegative,iszero.22SHEN’SCLASSNOTESObservation1ItiseasytoseethatallincomingflowstoavertexvÎV–{s,t},eitherpositiveornegative,isalsozero.Thisisbecaus
6、e==-=0.Definition4ThetotalpositiveflowenteringvertexvisdefinedasF+(v)=.Similarly,ThetotalpositiveflowleavingvertexvisdefinedasF-(v)=.Example1Fig.26-1showsaflownetworkandaflowinthenetworkwhichisnotamaximumflow.Fig.26-1Theflownetworksareusedtomodelmanyapplications.Forexample,itmodels
7、atransportationsystemwherewewishtotransportasmuchproductsfromnodestonodet.Maximum22SHEN’SCLASSNOTESflowproblemisanimportantgraphoptimizationproblem.Realnetworkflowproblemmayhavemultiplesourcesandmultiplesinks.WecanmodelsuchanetworkbyaddingasupersourceandasupersinkasillustratedbyFig
8、.26-2.Thus,wecanconvertthesenetworksintoourstandardnetworkflowproblem.Example2Fig.26-2showshowtoconvertanetworkflowproblemwithmultiplesourcesandmultiplesinkstoanetworkflowproblemwithasinglesourceandasinglesink.Fig.26-2Definition5LetXandYbetwosetsofvertices.WedefinetheflowfromsetXto
9、setYtobethefollowingsummation:f(X,Y)==.Forsimplicity,weuseutodenotetheset{u}foravertexu.Wehavef(u,V)=0foranyuÎV–{s,t}.22SHEN’SCLASSNOTESLemma26.1LetG=(V,E)beaflownetworkandfbeaflowinG.Then,thefollowingequalitieshold:(1)f(X,X)=0foranyXÍV.(2)f(X,Y)=-f(Y,X)foranyX,YÍV.(3)f(XÈY,Z)=f(X,
10、Z)+f(Y,Z),andf(Z,XÈY)=f(Z,
