网络最大流问题

问题 已知网络D=（V，A，C），其中V为顶点集，A为弧集，C=cij为容量集，cij 为弧（vi，vj）上的容量。现D上要通过一个流f=fij，其中fij 为弧（vi，vj）上的流量。问应如何安排流量fij可使D上通过的总流量v最大？例如：v4v2vsv1vtv3213145325第四节 网络最大流问题 7.4.1 网络的最大流的概念 网络流一般在有向图上讨论 定义网络上弧的容量为其最大通过能力，记为 cij，弧上的实际流量记为 fij 图中规定一个发点s，一个收点t 节点没有容量限制，流在节点不会存储 容量限制条件：0 fij cij 平衡条件：tifvtsisifvffijijvBvjivAvij)(,0)()()(满足上述条件的网络流称为满足上述条件的网络流称为可行流可行流，总存在，总存在最大可行流最大可行流viA(vi)B(vi)0 (1)ijijijijijfcfc f零流弧：未饱和弧：饱和弧：弧按流量分为如：在前面例举的网络流问题中，若已给定一个可行流（如括号中后一个数字所示），请指出相应的弧的类型。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（2）可增值链（增广链）一条可增值链。的中关于可行流为，则称中弧皆非零中弧皆未饱，若中的反向弧集：中的正向弧集：，记的链至中由fDvvDtsv4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（3）截集与截量）。的一个截集，记为（为）（称弧集。，使与分为二非空互补集截集（割集）：将11111111,VVDVvVvvvVvVvVVVjijits截量：截集上所有弧的容量和，记 。），（VVC例4 对于下图，若V1=vs，v1，请指出相应的截集与截量。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）解：，），（）（,vvvvVVs523,11）（VVC（4）流量与截量的关系）（）（11,VVCfv）（）（11,VVMinCfMaxv最大流最小割定理：v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（5）最大流的判别条件可增广链。的中不存在关于是最大流的充要条件是可行流fDf 最大流最小截的标号法步骤 第一步：标号过程，找一条增广链1、给源点 s 标号s+,q(s)=，表示从 s 点有无限流出潜力2、找出与已标号节点 i 相邻的所有未标号节点 j，若(1)(i,j)是前向弧且饱和，则节点 j 不标号；(2)(i,j)是前向弧且未饱和，则节点 j 标号为i+,q(j)，表示从节点 i 正向流出，可增广 q(j)=minq(i),cijfij；(3)(j,i)是后向弧，若 fji=0，则节点 j 不标号；(4)(j,i)是后向弧，若 fji0，则节点 j 标号为i,q(j)，表示从节点j 流向i，可增广 q(j)=minq(i),fji；7.4.2 确定网络最大流的标号法3、重复步骤 2，可能出现两种情况：(1)节点 t 尚未标号，但无法继续标记，说明网路中已不存在增广链，当前流 v(f)就是最大流；所有获标号的节点在 V 中，未获标号节点在 V 中，V 与 V 间的弧即为最小截集；算法结束(2)节点 t 获得标号，找到一条增广链，由节点 t 标号回溯可找出该增广链；到第二步第二步：增广过程1、对增广链中的前向弧，令 f=f+q(t)，q(t)为节点 t 的标记值2、对增广链中的后向弧，令 f=fq(t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步例1 用标号法求下面网络的最大流。解：第一次标号及所得可增值链如图，调量 =1，调后进行第二次标号如图。第二次标号未进行到底，得最大流如图，最大流量v=5，同时得最小截q。），（）（31211,vvvvVVsv4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）,sv,2v1,2v1,1v14,sv,3v1,sv3,sv2020例2 最大流最小截集的标号法举例st134256(14,14)(9,9)(15,9)(16,15)(3,1)(12,10)(6,6)(4,3)(5,5)(22,22)(13,12)(7,5)(6,3)(19,10)st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)(s+,)(s+,6)(2,6)(3+,1)(4+,1)(s+,)(s+,5)(2+,2)(5,2)(4+,2)123456tss123456t最大流最小截集的标号法举例st134256(14,14)(9,9)(15,10)(16,15)(3,1)(12,10)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)st134256(14,14)(9,9)(15,12)(16,15)(3,1)(12,12)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,1)(19,13)(s+,)(s+,3)(2,3)最小截集最小截集(4+,2)ttss112233445566例例.3：求下图中的最大流：求下图中的最大流：（3）xyv2v4447xyv4v3823xv2v3v4v5y8.04.02.02.04.06.07.04.01.09.04.4解：增广链：解：增广链：（1）4.47.4（2）8.22.27.66xy29v3v58.42.29.2Vf;最大流最大流 8 练习 用标号法求下面网络从s到t的最大流量,并找出该网络的最小割.st1v2v3v4v)8(8)5(7)4(5)4(9)0(2)9(9)1(6)5(5)8(10),0()2,(s)2,(2v)2,(1v)1,(3v)1,(4vst1v2v3v4v)8(8)6(7)3(5)5(9)0(2)9(9)0(6)5(5)9(10),0()1,(s)1,(2v)1,(1v)1,(3v)1,(4vkk.1495,)4,2(),3(),(最小割的容量为该网络的最小割为tVV6.5 中国邮递员问题中国邮递员问题一个邮递员从邮局出发分送邮件，要走完他负一个邮递员从邮局出发分送邮件，要走完他负责的所有街道，最后再返回邮局。应如何选择路线，责的所有街道，最后再返回邮局。应如何选择路线，才能使所走的路线最短，这就是中国邮递员问题。才能使所走的路线最短，这就是中国邮递员问题。1962年，管梅谷先生提出中国邮递员问题年，管梅谷先生提出中国邮递员问题。中国邮递员问题用图论的观点来看就是：中国邮递员问题用图论的观点来看就是：在在一个赋权连通图中，找一个过每边至少一次的闭链一个赋权连通图中，找一个过每边至少一次的闭链（圈），并且使闭链的权最小。它的算法与一笔画（圈），并且使闭链的权最小。它的算法与一笔画问题有关。问题有关。一、一笔画问题一、一笔画问题 有关一笔画问题有如下结论：有关一笔画问题有如下结论：1.一个连通图中的顶点都是偶点，一个连通图中的顶点都是偶点，没有奇点，没有奇点，则该图可以一笔画出。则该图可以一笔画出。2.一个连通图中的顶点恰有两个奇点，其余都一个连通图中的顶点恰有两个奇点，其余都是偶点，则从任一奇点出发，则可以一笔画出该图。是偶点，则从任一奇点出发，则可以一笔画出该图。3.一个连通图中的顶点有两个以上是奇点，则一个连通图中的顶点有两个以上是奇点，则该图不能一笔画出。该图不能一笔画出。图中的顶点都图中的顶点都是偶点，没有奇点，是偶点，没有奇点，则该图可以一笔画则该图可以一笔画出。出。图中的顶点都是图中的顶点都是奇点，没有偶点，则奇点，没有偶点，则该图不能一笔画出。该图不能一笔画出。图中的顶点有二图中的顶点有二个是奇点，其它是偶个是奇点，其它是偶点，则从任一奇点出点，则从任一奇点出发，则该图可以一笔发，则该图可以一笔画出。从任一偶点出画出。从任一偶点出发，则该图不能一笔发，则该图不能一笔画出。画出。二、中国邮递员问题。二、中国邮递员问题。解中国邮递员问题的奇偶点图上作业法：具体解中国邮递员问题的奇偶点图上作业法：具体步骤如下：步骤如下：1.通过加重复边，消灭图中的奇点。将奇点两通过加重复边，消灭图中的奇点。将奇点两两配对，在每一对奇点的通路上，均加上重复边。两配对，在每一对奇点的通路上，均加上重复边。2。删除过多的重复边。如果图中某条边的重复。删除过多的重复边。如果图中某条边的重复边多于一条，则可将它的重复边删除偶数条。边多于一条，则可将它的重复边删除偶数条。3。优化重复边。使所加的重复边的总长度最小。优化重复边。使所加的重复边的总长度最小。下面通过具体例子来说明具体计算过程：下面通过具体例子来说明具体计算过程：例例6.7 设有街道图如下：假如邮递员从设有街道图如下：假如邮递员从V1点出点出发，求他的最优投递路线。发，求他的最优投递路线。4444459655V132V9V4V3V2V8V7V6V5解：解：考虑加边的圈：考虑加边的圈：V1,V2,V9,V8 中，加边的长度是中，加边的长度是4+6=10，而不加边的长度是，而不加边的长度是4+5=9，故需改进如下。，故需改进如下。4444459655V132V9V4V3V2V8V7V6V5 考虑加边的圈：考虑加边的圈：v4,v5,v6,v9 中，加边的长度是中，加边的长度是3+5=8，而不加边的长度是，而不加边的长度是4+2=6，故需改进如下。，故需改进如下。图中已无奇点，可得最优投递路线：图中已无奇点，可得最优投递路线：奇偶点图作业法步骤 构造初始可行方案：由于奇点个数必为偶数，因此奇点必成对出现；同时由于图是连通的，因此每一对奇点之间必存在一条链，在这条链上的各边都加上重复边而成为新图，必定是无奇点的欧拉图。寻找改进可行方案：在两奇点间检查所有链，若某链的长度小于已加重复边的长度，则在该链的每边加上重复边，去掉原重复边。重复以上步骤，直到任意两奇点间加重复边的链是最短的为止。求解中国邮递员问题：例子例子的初始可行解例子的修正解