最大流问题的增广路算法概要

1Themaxflowproblem5102-271945112Ford-FulkersonmethodFord-Fulkerson(G)

f=0

while(9simplepathpfromstotinGf)

f:=f+fp

output

f3STc(S,T)=26Acut4Lemma26.5+Corollary26.6LetfbeaflowinGandlet(S,T)beacutinG.Then|f|=f(S,T).LetfbeaflowinGandlet(S,T)beacutinG.Then|f|·c(S,T).Thisisaweakdualitytheorem.5MaxFlow–MinCutTheoremLetfbeaflowinG.Thefollowingthreeconditionsareequivalent:1.fisamaximumflow2.Gfcontainsnoaugmentingpath3.Thereisacut(S,T)sothat|f|=c(S,T)6MaxFlow–MinCutTheoremThevalueofthemaximumflowinGisequaltothecapacityoftheminimumcutinG.Thisisastrongdualitytheorem.7RemarksThesolutionvaluesagree,notthesolutionsthemselves–flowsandcutsarecompletelydifferentobjects.Givenamaxflowwecaneasilyfindamincut(followsfromproofofmaxflow-mincuttheorem).Goingtheotherwayislessobvious.8ConsequenceTheFord-Fulkersonmethodispartiallycorrect,i.e.,ifitterminatesitproducestheflowwiththemaximumvalue.9LocalsearchchecklistDesign:Howdowefindthefirstfeasiblesolution?Neighborhooddesign?Whichneighbortochoose?Analysis:Partialcorrectness?(termination)correctness)Termination?

Complexity?

٧٧٧10TerminationSupposeallcapacitiesareintegers.Westartwithaflowofvalue0.Ineachiteration,wegetanewflowwithhigherintegervalue.Wealwayshavealegalflow,i.e.,oneofvalueatmost|f|.Hencewecanhaveatmost|f|iterations.11CorrectnessofFord-FulkersonSinceFord-Fulkersonispartiallycorrectanditterminatesifcapacitiesareintegersitisacorrectalgorithmforfindingthemaximumflowifcapacitiesareintegers.Exercise:Itisalsocorrectifcapacitiesarerationals.12DoesFord-Fulkersonalwaysterminate?Incaseofirrationalcapacities,notnecessarily!(Exercise)Butwecan’tgiveirrationalcapacitiesasinputstodigitalcomputersanyway.Incaseoffloatingpointcapacities,whoknows?13IntegralityTheorem(26.11)Ifaflownetworkhasintegervaluedcapacities,thereisamaximumflowwithanintegervalueoneveryedge.TheFord-Fulkersonmethodwillyieldsuchamaximumflow.Theintegralitytheoremisoftenextremelyimportantwhen“programming”andmodelingusingthemaxflowformalism.14Reduction:

MaximumMatching!MaxFlowWhatisthemaximumcardinalitymatchinginG?15

G16

G’stAllcapacitiesare117FindingabalancedsetofRepresentativesAcityhasclubsC1,C2,…,Cnandparties

P1,P2,…,Pm.Acitizenmaybeamemberofseveralclubsbutmayonlybeamemberofoneparty.AbalancedcitycouncilmustbeformedbyincludingexactlyonememberfromeachclubandatmostukmembersfrompartyPk.(Ahuja,Application6.2)1819LocalsearchchecklistDesign:Howdowefindthefirstfeasiblesolution?Neighborhooddesign?Whichneighbortochoose?Analysis:Partialcorrectness?(termination)correctness)Termination?

Complexity?

٧٧٧٧20ComplexityofFord-FulkersonWehaveatmost|f|improvementsteps(iterationsofthewhile-loop).Isthisthebestpossiblebound?21ComplexityWehaveatmost|f|improvementsteps(iterationsofthewhile-loop)andthisboundcannotbeimprovedforthegeneralFord-Fulkersonmethod.Howfastcanweimplementasingleimprovementstep?22ComplexityAssume|V|-1·|E|.Otherwisethegraphisnotconnected.Then,Ford-FulkersoncanbeimplementedtorunintimeatmostO(|E||f|).Isthisfast?23PolynomialtimealgorithmsDefintion:Apolynomialtimealgorithmisanalgorithmthanrunsintimepolynomialinn,wherenisthenumberofbitsoftheinput.Howweintendtoencodetheinputinfluencesifwehaveapolynomialalgorithmornot.Usually,some“standardencoding”isimplied.Inthiscourse:Polynomial¼FastExponential¼Slow24javaMaxFlow??????????Howtoencodemaxflowinstance?25javaMaxFlow6#0|16|13|0|0|0#0|0|10|12|0|0#0|4|0|0|14|0#0|0|9|0|0|20#0|0|0|7|0|4|#0|0|0|0|0|0Howtoencodemaxflowinstance?26ComplexityofFord-FulkersonWithstandard(decimalorbinary)representationofintegers,Ford-Fulkersonisanexponentialtimealgorithm.27javaMaxFlow111111#|1111111111111111|1111111111111|||#||1111111111|111111111111||#|1111|||11111111111111|#||111111111|||11111111111111111111#|||1111111||1111#|||||28ComplexityofFord-FulkersonWithunary(4~1111)representationofintegers,Ford-Fulkersonisapolynomialtimealgorithm.Intuition:Whentheinputislongeritiseasiertobepolynomialtimeasafunctionoftheinputlength.Analgorithmwhichispolynomialifintegerinputsarerepresentedinunaryiscalledapseudo-polynomialalgorithm.Intuitively,apseudo-polynomialalgorithmisanalgorithmwhichisfastifallnumbersintheinputaresmall.29Edmonds-KarpEdmonds-KarpalgorithmforMaxFlow:ImplementFord-Fulkersonbyalwayschoosingtheshortestpossibleaugmentingpath,i.e.,theonewithfewestpossibleedges.30ComplexityofEdmonds-KarpEachiterat