网络流和匹配NetworkFlows

网络流和匹配NetworkFlows3/20/2023NetworkFlow2OutlineandReadingFlowNetworksFlow(§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.3/20/2023NetworkFlow3FlowNetworkAflownetwork(orjustnetwork)NconsistsofAweighteddigraphGwithnonnegativeintegeredgeweights,wheretheweightofanedgeeiscalledthecapacityc(e)ofe

Twodistinguishedvertices,sandtofG,calledthesourceandsink,respectively,suchthatshasnoincomingedgesandthasnooutgoingedges.Example:wsvutz39137651523/20/2023NetworkFlow4FlowAflowfforanetworkNisisanassignmentofanintegervaluef(e)toeachedgeethatsatisfiesthefollowingproperties:CapacityRule:Foreachedgee,0

f(e)

c(e)ConservationRule:Foreachvertexvs,t

whereE-(v)andE+(v)aretheincomingandoutgoingedgesofv,resp.Thevalueofaflowf,denoted|f|,isthetotalflowfromthesource,whichisthesameasthetotalflowintothesinkExample:wsvutz3/32/91/11/33/72/64/51/13/52/23/20/2023NetworkFlow5MaximumFlowAflowforanetworkNissaidtobemaximumifitsvalueisthelargestofallflowsforNThemaximumflowproblemconsistsoffindingamaximumflowforagivennetworkNApplicationsHydraulicsystemsElectricalcircuitsTrafficmovementsFreighttransportationwsvutz3/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+43/20/2023NetworkFlow6CutAcutofanetworkNwithsourcesandsinktisapartitionc

=(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/2c3/20/2023NetworkFlow7FlowandCutLemma: 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|=83/20/2023NetworkFlow8AugmentingPathConsideraflowfforanetworkNLetebeanedgefromutov:Residualcapacityofefromutov:Df(u,v)=c(e)-

f(e)Residualcapacityofefromvtou:Df(v,u)=f(e)LetpbeapathfromstotTheresidualcapacityDf(p)of

p

isthesmallestoftheresidualcapacitiesoftheedgesofpinthedirectionfromstotApathpfromstotisanaugmentingpathifDf(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|=73/20/2023NetworkFlow9FlowAugmentationLemma: LetpbeanaugmentingpathforflowfinnetworkN.ThereexistsaflowfforNofvalue

|f|=|f|+

Df(p) Proof: WecomputeflowfbymodifyingtheflowontheedgesofpForwardedge:

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

|=83/20/2023NetworkFlow10Ford-Fulkerson’sAlgorithmInitially,f(e)=0foreachedgeeRepeatedlySearchforanaugmentingpathpAugmentbyDf(p)theflowalongtheedgesofpAspecializationofDFS(orBFS)searchesforanaugmentingpathAnedgeeistraversedfromutovprovidedDf(u,v)>0Algorithm

FordFulkersonMaxFlow(N)

forall

eG.edges()

setFlow(e,0)while

G

hasanaugmentingpathp

{computeresidualcapacityDofp} D

foralledges

ep

{computeresidualcapacitydofe} if

eisaforwardedgeofp

d

getCapacity(e)-getFlow(e) else{eisabackwardedge}

d

getFlow(e) if

d

<

D

D

d

{augmentflowalongp} foralledges

ep if

eisaforwardedgeofp setFlow(e,getFlow(e)+D)

else{eisabackwardedge}

setFlow(e,getFlow(e)-D)

3/20/2023NetworkFlow11Max-FlowandMin-CutTerminationofFord-Fulkerson’salgorithmThereisnoaugmentingpathfromstotwithrespecttothecurrentflowfDefineVs setofverticesreachablefromsbyaugmentingpathsVt setofremainingverticesCutc

=(Vs,Vt)hascapacity

c(c)=|f|Forwardedge:f(e)=c(e)Backwardedge:f(e)=0Thus,flowfhasmaximumvalueandcutchasminimumcapacitywsvutz3/31/91/13/34/74/63/51/13/52/2cTheorem:Thevalueofamaximumflowisequaltothecapacityofaminimum