资源描述：
《maximum flow-算法导论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、26MaximumFlowJustaswecanmodelaroadmapasadirectedgraphinordertofindtheshortestpathfromonepointtoanother,wecanalsointerpretadirectedgraphasa“flownetwork”anduseittoanswerquestionsaboutmaterialflows.Imagineamate-rialcoursingthroughasystemfromasource,wherethematerialisproduced,toasink,where
2、itisconsumed.Thesourceproducesthematerialatsomesteadyrate,andthesinkconsumesthematerialatthesamerate.The“flow”ofthemate-rialatanypointinthesystemisintuitivelytherateatwhichthematerialmoves.Flownetworkscanmodelmanyproblems,includingliquidsflowingthroughpipes,partsthroughassemblylines,c
3、urrentthroughelectricalnetworks,andinformationthroughcommunicationnetworks.Wecanthinkofeachdirectededgeinaflownetworkasaconduitforthemate-rial.Eachconduithasastatedcapacity,givenasamaximumrateatwhichthema-terialcanflowthroughtheconduit,suchas200gallonsofliquidperhourthroughapipeor20am
4、peresofelectricalcurrentthroughawire.Verticesareconduitjunctions,andotherthanthesourceandsink,materialflowsthroughtheverticeswithoutcollectinginthem.Inotherwords,therateatwhichmaterialentersaver-texmustequaltherateatwhichitleavesthevertex.Wecallthisproperty“flowconservation,”anditiseq
5、uivalenttoKirchhoff’scurrentlawwhenthematerialiselectricalcurrent.Inthemaximum-flowproblem,wewishtocomputethegreatestrateatwhichwecanshipmaterialfromthesourcetothesinkwithoutviolatinganycapacityconstraints.Itisoneofthesimplestproblemsconcerningflownetworksand,asweshallseeinthischapter
6、,thisproblemcanbesolvedbyefficientalgorithms.Moreover,wecanadaptthebasictechniquesusedinmaximum-flowalgorithmstosolveothernetwork-flowproblems.Thischapterpresentstwogeneralmethodsforsolvingthemaximum-flowprob-lem.Section26.1formalizesthenotionsofflownetworksandflows,formallydefiningthemaxi
7、mum-flowproblem.Section26.2describestheclassicalmethodofFordandFulkersonforfindingmaximumflows.Anapplicationofthismethod,26.1Flownetworks709findingamaximummatchinginanundirectedbipartitegraph,appearsinSec-tion26.3.Section26.4presentsthepush-relabelmethod,whichunderliesmanyofthefastestal
8、gorithmsfornetwork-
