资源预览内容
第1页 / 共30页
第2页 / 共30页
第3页 / 共30页
第4页 / 共30页
第5页 / 共30页
第6页 / 共30页
第7页 / 共30页
第8页 / 共30页
第9页 / 共30页
第10页 / 共30页
亲,该文档总共30页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第四节 最大流问题例:下图为v1到v6的一交通网,权表示相应运输线的最大通过能力,制定一方案,使从v1到v6的产品数量最多1、一般提法设有网络G=(V,E,C),其中C=cij,cij为弧(vi ,vj)上的容量,现在上要通过一个流f=fij, fij为弧(vi ,vj)上的流量问题:如何安排fij,可使网络上的总流量最大。称满足约束条件的流f为可行流:可行流中 fijcij 的弧叫做饱和弧,fijcij的弧叫做非饱和弧。fij0 的弧为非零流弧,fij0 的弧叫做零流弧。(2)平衡条件:对于发点vs,有对于收点vt ,有对于中间点,有(1)容量限制条件:对于每一条弧(vi ,vj)E 有 0 fij cij 。 、最大流问题的模型可行流中: fijcij 的弧叫做饱和弧,fijcij的弧叫做非饱和弧。fij0 的弧为非零流弧,fij0 的弧叫做零流弧。 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1) 图中 为零流弧,其余为非零流弧。3、f为一个可行流,若u为从vs到vt的一条链,给u定向为从vs到vt。 u上的弧:凡与u方向相同的称为正向弧;凡与u方向相反的称为反向弧;其集合分别用u+和u-表示。f 是一个可行流,如果满足: 则称 u为从vs到vt 的关于f 的一条增广链。 推论 可行流f 是最大流的充分必要条件是: 即+中的每一条弧都是非饱和弧即-中的每一条弧都是非零流弧不存在从vs到vt 的关于f 的一条可增广链。 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)是一个可增广链显然图中可增广链不止一条 4、容量网络D =(V,A,C),vs为始点,vt为终点。如果把V分成两个非空集合 使 ,则所有始点属于 ,而终点属于 的弧的集合,称为D的截集,记作 。截集 中所有弧的容量之和,称为这个截集的截量,记为 。 vsv1v2v4v3vt374556378 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)设 ,则截集为截量为24 13 (5)9 (3)4 (1)5 (3)6(3)5 (2)5 (2)5 (0)4 (2)4 (1)9 (5)10 (1)设 ,则截集为截量为20流量与截量的关系任一可行流的流量都不会超过任一截集的截量。 定理 最大流-最小截定理 任何一个网络G中,从vs到vt的最大流的流量等于最小截量。例:如图所示的网络中,弧旁数字为( cij ,fij ) (1)确定所有的截集 (2)求最小截集的流量 (3)证明图中的流为最大流例:如图所示的网络中,弧旁数字为( cij ,fij ) (1) 所有的截集例:如图所示的网络中,弧旁数字为( cij ,fij ) (2)最小截量 (3) 是最大流三、 求最大流的标号法理论依据:可行流是最大流不存在关于的增广链思路:从始点开始标号,寻找是否存在增广链。给vj标号为j, vi,其中j为调整量, vi为前一结点。求最大流的标号法 标号过程:1 给vs 标号(+,vs ),选与vs关联的流出未饱和弧(vs,vj ),给vj标号j, vs,其中j=csj-fsj。2 把节点集V分成VA :已标号点集 VB :未标号点集3考虑所有这样的弧(vi ,vj) 或(vj,vi ) ,其中 ,若该弧为(1)流出未饱弧,那么给vj标号(j, vi) ,其中: j=cij-fij(2)流入非零弧,那么给vj标号(j, -vi) ,其中: j=fij 4重复步骤2,3,直到vt被标号或标号过程无法进行下去,则标号结束。(1) 若vt被标号,则存在一条可增广链,转调整过程;(2)若vt未被标号,而标号过程无法进行下去,这时的可行流就是最大流,此时的截集为最小截。调整过程取1令 2去掉所有标号,回到第1步,对可行流重新标号。vsv5v2v4v1v3v6vt(3 , 3)(4 ,2)(2 , 2)(2 , 2)(5 , 2)(3 , 0)(5 , 4)(3 , 3)(4 , 2)(3 , 2)(5 ,5)+ ,vs2,vs3,v21,vs3,-v53,v12,v4vsv5v2v4v1v3v6vt(3 , 3)(4 ,2)(2 , 2)(2 , 2)(5 , 2)(3 , 0)(5 , 4)(3 , 3)(4 , 2)(3 , 2)(5 ,5)+ , vs2,vs3,v21,vs3,-v52,v12,v4vsv5v2v4v1v3v6vt(3 , 3)(4 ,2)(2 , 2)(2 , 2)(5 , 2)(3 , 0)(5 , 4)(3 , 3)(4 , 2)(3 , 2)(5 ,5)+,vs2,vs3,v21,vs3,-v53,v12,v4+2+2+2+2-2vsv5v2v4v1v3v6vt(3 , 1)(4 , 4)(2 , 2)(2 , 2)(5 , 4)(3 , 2)(5 , 4)(3 , 3)(4 , 4)(3 , 2)(5 ,5)vsv5v2v4v1v3v6vt(3 , 1)(4 , 4)(2 , 2)(2 , 2)(5 , 4)(3 , 2)(5 , 4)(3 , 3)(4 , 4)(3 , 2)(5 ,5)+ ,vs1,vsvsv5v2v4v1v3v6vt(3 , 1)(4 , 4)(2 , 2)(2 , 2)(5 , 4)(3 , 2)(5 , 4)(3 , 3)(4 , 4)(3 , 2)(5 ,5)+ , vs1,vsvsv5v2v4v1v3v6vt(3 , 1)(4 , 4)(2 , 2)(2 , 2)(5 , 4)(3 , 2)(5 , 4)(3 , 3)(4 , 4)(3 , 2)(5 ,5)+ ,vs1,vsvsv5v2v4v1v3v6vt(3 , 1)(4 , 4)(2 , 2)(2 , 2)(5 , 4)(3 , 2)(5 , 4)(3 , 3)(4 , 4)(3 , 2)(5 ,5)+ ,vs1,vsvsv5v2v4v1v3v6vt(3 , 1)(4 , 4)(2 , 2)(2 , 2)(5 , 4)(3 , 2)(5 , 4)(3 , 3)(4 , 4)(3 , 2)(5 ,5) ,+ +vs,1已经标号点集合:未标号点集合:截集为:截量为: 求下图所示网络中的最大流,弧旁数为(1 ,1)v2v1v4v3vsvt(3 , 3)(5 , 1)(1 , 1)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,1)+ ,vs 1,-v14,vs 1,-v2 1,v21, v3 (1 ,1)v2v1v4v3vsvt(3 , 3)(5 , 1)(1 , 1)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,1)+ ,vs 1,-v14, vs1, -v2 1 , v22, v3 (1 ,0v2v1v4v3vsvt(3 , 3)(5 , 2)(1 , 0)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,2)(1 ,0)v2v1v4v3vsvt(3 , 3)(5 , 2)(1 , 0)(4 ,3)(2 , 2)(3 ,0)(5 ,3)(2 ,2)+ , vs3,vs 当前的可行流为最大流最小截集
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号