资源描述：
《算法分析与设计2004春.课件.第09讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Lecture9.MaximumFlow极大流1.流网实例：1.例1：管道中的流体2.例2：电网中的电流3.例3：通信网络中的信息流4.例4：装配线上的零件流2.概念抽象：1.有向边：传输物质的管道2.容量：每条管道有静态容量：单位时间内可以通过物质的最大数量，如每天可以通过100万立方米的石油管道3.点：管道连接点，满足流量守恒律清华大学软件学院宋斌恒112st34清华大学软件学院宋斌恒21Kirchhoff’s电流定律1.流量守恒定律：1.流入同一节点的总流量等于流出同一节点总流量2.对于电流就是Kirchhof
2、f’s定律3.极大流问题：计算流网中满足约束（上述守恒律）的从源到汇的最大流量。清华大学软件学院宋斌恒3流网的定义1.流网G=(V,E)是一个具有非负边权的有向图，边权c(u,v)叫做容量，如果(u,v)不属于E，我们约定其容量c(u,v)＝0。2.在流网上有两个特殊点源s和汇t。3.对于每个点v，都有一条从s经过v到达t的路径4.流Flow：G上的一个流是一个实函数f：V×VÆR,它满足1.容量约束：对所有u,v,f(u,v)≤c(u,v)2.反对称：对所有u,v,f(u,v)＝－f(v,u)3.流守恒：对所有u∈
3、V-{s,t}∑v∈Vf(u,v)=04.流f的值：
4、f
5、=∑v∈Vf(s,v)5.f(u,v)叫做从u到v的流清华大学软件学院宋斌恒，其值可正可负42极大流问题1.给定流网G=(V,E)、流网上的容量c(u,v)，和源s、汇t，求流f使得其流值取得极大2.相关概念扩充1.一个顶点v的总流入量：∑u∈V，f(u,v)>0f(u,v)2.一个顶点v的总流出量：∑u∈V，f(v,u)>0f(v,u)3.总净流量＝总流出量－总流入量4.守恒律的另一种表述：在非源非汇点，总流出量＝总流入量清华大学软件学院宋斌恒5多源多汇问题
6、•许多实际问题是多源多汇问题【见下页图】，也就是说流网中有多个源，有多个汇，这样的问题如何解决？•我们通过添加人工源和汇的方法将多源多汇问题转化为单源单汇的标准问题：【见下下页图】1.添加人工源s和人工汇t两个节点，2.添加s到原问题所有源对应的顶点的有向边，并赋予∞权，3.添加原问题所有汇对应顶点到t到有向边，并赋予∞权，4.于是原问题就变成了标准单源单汇问题。Whyequivalent？清华大学软件学院宋斌恒63s1s2t1s3t2s4t3s5清华大学软件学院宋斌恒7s1s2t1ss3t2ts4t3s5清华大学软
7、件学院宋斌恒84流的运算•设f是流函数，X和Y是V[G]的子集，•定义：f(X,Y)=∑x∈X,y∈Yf(x,y)•那么我们有：1.守恒律：对任意u属于V-{s,t}有f(u,V)=0【如何证？】2.f(s,V-s)=f(s,V)3.f(X,X)=04.f(X,Y)=-f(Y,X)5.如果X∩Y=φ，我们有：1.f(X,Z)+f(Y,Z)=f(X∪Y,Z)2.f(Z,X)+f(Z,Y)=f(Z,X∪Y)清华大学软件学院宋斌恒9流的值•
8、f
9、=f(s,V)•=f(V,V)-f(V-s,V)•=f(V,V-s)•=f(V
10、,t)+f(V,V-s-t)•=f(V,t)•课堂练习：•如果(u,v)和(v,u)都不属于E，利用定义证明f(u,v)=f(v,u)=0清华大学软件学院宋斌恒105Residualnetworks•Definitionofresidualnetworks–LetfbeaflowinG,aresidualnetworkinducedbyfisaflownetworkGf=(V,Ef),suchthat•Cf(u,v)=c(u,v)-f(u,v)•Ef={(u,v):Cf(u,v)>0}–Wecall(u,v)inEf
11、istheresidualedgeandCfistheresidualcapacity清华大学软件学院宋斌恒11Computearesidualnetworkfromaflownetworkandaflowf12st34清华大学软件学院宋斌恒12612st34清华大学软件学院宋斌恒1312st34清华大学软件学院宋斌恒14712st34清华大学软件学院宋斌恒1512st34清华大学软件学院宋斌恒168Lemma26.2•LetG=(V,E)beaflownetworkwithsourcesandsinkt,andfb
12、eaflowinG.LetGbeftheresidualnetworkofGinduced(诱导)byf.Letf’beaflowinG,thenf+f’isaflowfinGwith•
13、f+f’
14、=
15、f
16、+
17、f’
18、清华大学软件学院宋斌恒17Proof.•Skewsymmetry•Capacityconstrain•Valueoff+f’清华大
