《运筹学最大流问题》PPT课件

《《运筹学最大流问题》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§4最大流定义有向连通图G=(V,E),G的每条边(vi,vj)[称作弧]上有cij称为边的容量,仅有一个入次为0的点vi称为中间点,这样的网络G称为容量网络,常记为G=(V,E,C).对任一G中的边(vi,vj)有流量fij,称为集合f={fij}为网络G上的一个流。称满足下列条件的流f为可行流：(1)容量限制条件:对G中每条边(vi,vj),有0≤fij≤cij;jk(2)平衡条件:对中间点vi,∑fij=∑fkj(即中间点vi的输入量与输出量相等).(即从vs点发出总量等于vt与输入总量相等).i对收、发点

2、vi,vj,有∑fsi=∑fjtj一、最大流有关概念非负权,发点(源),一个入次为0的点vi称为收点(汇),其余的点称为定义容量网络G=(V,E,C),vi,vj收、发点,若有边集E’为E的子集,将G分为两个子图G1,G2,其顶点集合分别记S,②E’’为E’的真子集,而G(V,E-E’’)仍连通,①G(V,E-E’)不连通;则称E’为G的割集,记E’=(S,S).S,S∪S=V,S∩S=⊙,vi,vj分属S,S,满足割集(S,S)中所有始点在S,终点在S的边的容量之和,称为割集容量,记为C(S,S).一个流f={

3、fij},fij=cij,则称流f对边(vi,vj)是饱和的.列出图示网络全部割边上数字为cij(fij).9(4)sv3v4v1v27(5)2(0)9(9)10(8)8(8)5(5)tVVs,v1,v2,v3,v4ts,v1,v2,v4s,v1,v2,v3s,v2,v4s,v1,v3s,v1,v2s,v2s,v1sv1,v2,v3,v4,tv2,v3,v4,tv1,v3,v4,tv3,v4,tv2,v4,tv1,v3,tv4,tv3,t(s,1)(s,2)(s,2)(1,2)(s,1)(1,3)(s,1)(2,

4、4)(s,2)(4,t)(1,3)(2,4)(4,3)(1,2)(3,2)(3,t)(2,4)(3,t)(4,3)(4,t)(1,3)(3,t)15(4,t)2117181924142515割容量4-3、最大流-最小割定理定理定理2(最大流-最小割定理)任一网络G中,从vs到vt的定义设f为网络G=(V,E,C)的任一可行流,流量为W,(S,S)是分离vs,vt的任一割集,则有W≤C(S,S).容量网络G,若μ为网络中从vs到vt的一条链,给μ定向为从vs到vt,μ上的边凡与μ同向称为前向边,凡与μ反向的称为后向

5、边，其集合分别用μ+和μ-表示,f是一个可行流,如果满足0≤fij0(vi,vj)∈μ-则称μ为从vs到vt的(关于f)的可增广链.最大流的流量等于分离vs,vt的最小割的容量.推论可行流f是最大流的充要条件是不存在从vs到vt的(关于f的)可增广链.4-4、求最大流的标号算法若vt得到标号,说明存在一条可增广链,转(第2步)调整过程.⑴给发点vs以标号(0,+∞).⑵选择一个已标号的顶点vi,对于vi,的所有未给标号的邻(a)若边(vj,vi)∈E,且fji>0,则令

6、δj=min(fji,δj),并给vj以标号(-vi,δj).1.标号过程(b)若边(vi,vj)∈E,且fij

7、)不在可增广链上作业阅读p258-265p4315,17图边集{(vs,v1),(v1,v3),(v2,v3),(v3,vt),(v4,vt)}都是割集.911割集容量2v23434143222v1v4v3vtvs边集{(vs,v1),(vs,v3),(vs,v4)}例14_A图中一个网络及初始可行流,边上序数为(cij,fij)v2(5,2)v1v4v3vtvsv5v6(4,2)(5,5)(3,0)(3,3)(3,3)(5,4)(2,2)(4,2)(2,2)(3,2)先给vs标号(△,+∞).检查vs的邻接点v

8、1,v2,v3,边(vs,v2)∈E,且fs20,v1令δ=min[3,2]=2,给v2以标号[+vs,2].v4