《网络流和匹配》.ppt

该【《网络流和匹配》 】是由【文库姐姐】上传分享，文档一共【14】页，该文档可以免费在线阅读，需要了解更多关于【《网络流和匹配》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。Chapter8:NetworkFlow
w
s
v
u
t
z
3/3
1/9
1/1
3/3
4/7
4/6
3/5
1/1
3/5
2/2
c
*
1
.
OutlineandReading
FlowNetworks
Flow(§)
Cut(§)
Maximumflow
AugmentingPath(§)
MaximumFlowandMinimumCut(§)
Ford-Fulkerson’sAlgorithm(§-)
Sections§-.
Date
2
.
FlowNetwork
Aflownetwork(orjustnetwork)Nconsistsof
AweighteddigraphGwithnonnegativeintegeredgeweights,wheretheweightofanedgeeiscalledthecapacityc(e)ofe
Twodistinguishedvertices,sandtofG,calledthesourceandsink,respectively,suchthatshasnoincomingedgesandthasnooutgoingedges.
Example:
w
s
v
u
t
z
3
9
1
3
7
6
5
1
5
2
Date
3
.
Flow
AflowfforanetworkNisisanassignmentofanintegervaluef(e)toeachedgeethatsatisfiesthefollowingproperties:
CapacityRule:Foreachedgee,0f(e)c(e)
ConservationRule:Foreachvertexvs,twhereE-(v)andE+(v)aretheincomingandoutgoingedgesofv,resp.
Thevalueofaflowf,denoted|f|,isthetotalflowfromthesource,whichisthesameasthetotalflowintothesink
Example:
w
s
v
u
t
z
3/3
2/9
1/1
1/3
3/7
2/6
4/5
1/1
3/5
2/2
Date
4
.
MaximumFlow
AflowforanetworkNissaidtobemaximumifitsvalueisthelargestofallflowsforN
ThemaximumflowproblemconsistsoffindingamaximumflowforagivennetworkN
Applications
Hydraulicsystems
Electricalcircuits
Trafficmovements
Freighttransportation
w
s
v
u
t
z
3/3
2/9
1/1
1/3
3/7
2/6
4/5
1/1
3/5
2/2
w
s
v
u
t
z
3/3
2/9
1/1
3/3
3/7
4/6
4/5
1/1
3/5
2/2
Flowofvalue8=2+3+3=1+3+4
Maximumflowofvalue10=4+3+3=3+3+4
Date
5
.
Cut
AcutofanetworkNwithsourcesandsinktisapartitionc=(Vs,Vt)oftheverticesofNsuchthatsVsandtVt
Forwardedgeofcutc:origininVsanddestinationinVt
Backwardedgeofcutc:origininVtanddestinationinVs
Flowf(c)acrossacutc:totalflowofforwardedgesminustotalflowofbackwardedges
Capacityc(c)ofacutc:totalcapacityofforwardedges
Example:
c(c)=24
f(c)=8
w
s
v
u
t
z
3
9
1
3
7
6
5
1
5
2
c
w
s
v
u
t
z
3/3
2/9
1/1
1/3
3/7
2/6
4/5
1/1
3/5
2/2
c
Date
6
.
FlowandCut
Lemma:
Theflowf(c)acrossanycutcisequaltotheflowvalue|f|
Lemma:
Theflowf(c)acrossacutcislessthanorequaltothecapacityc(c)ofthecut
Theorem:
Thevalueofanyflowislessthanorequaltothecapacityofanycut,.,foranyflowfandanycutc,wehave |f|c(c)
w
s
v
u
t
z
3/3
2/9
1/1
1/3
3/7
2/6
4/5
1/1
3/5
2/2
c1
c2
c(c1)=12=6+3+1+2
c(c2)=21=3+7+9+2
|f|=8
Date
7
.
AugmentingPath
ConsideraflowfforanetworkN
Letebeanedgefromutov:
Residualcapacityofefromutov:Df(u,v)=c(e)-f(e)
Residualcapacityofefromvtou:Df(v,u)=f(e)
Letpbeapathfromstot
TheresidualcapacityDf(p)ofpisthesmallestoftheresidualcapacitiesoftheedgesofpinthedirectionfromstot
ApathpfromstotisanaugmentingpathifDf(p)>0
w
s
v
u
t
z
3/3
2/9
1/1
1/3
2/7
2/6
4/5
0/1
2/5
2/2
p
Df(s,u)=3
Df(u,w)=1
Df(w,v)=1
Df(v,t)=2
Df(p)=1
|f|=7
Date
8
.
FlowAugmentation
Lemma:
forNofvalue |f|=|f|+Df(p)
Proof:
Wecomputeflowfbymodifyingtheflowontheedgesofp
Forwardedge: f(e)=f(e)+Df(p)
Backwardedge: f(e)=f(e)-Df(p)
w
s
v
u
t
z
3/3
2/9
1/1
1/3
2/7
2/6
4/5
0/1
2/5
2/2
p
Df(p)=1
w
s
v
u
t
z
3/3
2/9
0/1
2/3
2/7
2/6
4/5
1/1
3/5
2/2
p
|f|=7
|f|=8
Date
9
.
Ford-Fulkerson’sAlgorithm
Initially,f(e)=0foreachedgee
Repeatedly
Searchforanaugmentingpathp
AugmentbyDf(p)theflowalongtheedgesofp
AspecializationofDFS(orBFS)searchesforanaugmentingpath
AnedgeeistraversedfromutovprovidedDf(u,v)>0
AlgorithmFordFulkersonMaxFlow(N)
foralle()
setFlow(e,0)
whileGhasanaugmentingpathp
{computeresidualcapacityDofp}
D
foralledgesep
{computeresidualcapacitydofe}
ifeisaforwardedgeofp
dgetCapacity(e)-getFlow(e)
else{eisabackwardedge}
dgetFlow(e)
ifd<D
Dd
{augmentflowalongp}
foralledgesep
ifeisaforwardedgeofp
setFlow(e,getFlow(e)+D)
else{eisabackwardedge}
setFlow(e,getFlow(e)-D)
Date
10
.