网络最大流问题

问题已知网络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)ijijijijijfcfcf零流弧：未饱和弧：饱和弧：弧按流量分为如：在前面例举的网络流问题中，若已给定一个可行流（如括号中后一个数字所示），请指出相应的弧的类型。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（2）可增值链（增广链）一条可增值链。的中关于可行流为，则称中弧皆非零中弧皆未饱，若中的反向弧集：中的正向弧集：，记的链至中由fDvvDtsv4v2vsv1vtv3（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）解：，）），（（）（,,,vvvvVV523,）（VVC（4）流量与截量的关系）（）（11,VVCfv）（）（,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)=min[q(i),cijfij]；–(3)(j,i)是后向弧，若fji=0，则节点j不标号；–(4)(j,i)是后向弧，若fji0，则节点j标号为[i,q(j)]，表示从节点j流向i，可增广q(j)=min[q(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=fq(t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步例1用标号法求下面网络的最大流。解：第一次标号及所得可增值链如图，调量=1，调后进行第二次标号如图。第二次标号未进行到底，得最大流如图，最大流量v=5，同时得最小截q。）），（（）（31211,,,vvvvVVv4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）],[sv],[2v1],[2v1],[1v1][4,sv],[3v1••••••],[sv][3,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(),(最小割的容量为该网络的最小割为tVV§6.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，故需改进如下。图中已无奇点，可得最优投递路线：奇偶点图作业法步骤•构造初始可行方案：由于奇点个数必为偶数，因此奇点必成对出现；同时由于图是连通的，因此每一对奇点之间必存在一条链，在这条链上的各边都加上重复边而成为新图，必定是无奇点的欧拉图。•寻找改进可行方案：在两奇点间检查所有链，若某链的长度小于已加重复边的长度，则在该链的每边加上重复边，去掉原重复边。•重复以上步骤，直到任意两奇点间加重复边的链是最短的为止。求解中国邮递员问题：例子1v2v3v4v5v6v15412232236例子的初始可行解1v2v3v4v5v6v1541223223652例子的修正解1v2v3v4v5v6v1541223223612