网络最大流问题ppt课件.ppt

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

1、问题已知网络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平衡条件：满足上述条件的网络流称为可

2、行流，总存在最大可行流viA(vi)B(vi)如：在前面例举的网络流问题中，若已给定一个可行流（如括号中后一个数字所示），请指出相应的弧的类型。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（2）可增值链（增广链）v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（3）截集与截量截量：截集上所有弧的容量和，记。例4对于下图，若V1={vs，v1}，请指出相应的截集与截量。v4v2vsv1vtv3（2，2）（1，1）（3，3）（

3、1，1）（4，3）（5，1）（3，0）（2，1）（5，3）解：（4）流量与截量的关系最大流最小割定理：v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（5）最大流的判别条件最大流最小截的标号法步骤第一步：标号过程，找一条增广链1、给源点s标号[s+,q(s)=]，表示从s点有无限流出潜力2、找出与已标号节点i相邻的所有未标号节点j，若(1)(i,j)是前向弧且饱和，则节点j不标号；(2)(i,j)是前向弧且未饱和，则节点j标号为[i+,q(j)]，表示从节点i正向流出，可增广q(j)=mi

4、n[q(i),cijfij]；(3)(j,i)是后向弧，若fji=0，则节点j不标号；(4)(j,i)是后向弧，若fji>0，则节点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、对增

5、广链中的前向弧，令f=f+q(t)，q(t)为节点t的标记值2、对增广链中的后向弧，令f=fq(t)3、非增广链上的所有支路流量保持不变第三步：抹除图上所有标号，回到第一步例1用标号法求下面网络的最大流。解：第一次标号及所得可增值链如图，调量=1，调后进行第二次标号如图。第二次标号未进行到底，得最大流如图，最大流量v=5，同时得最小截v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）••••••2020例2最大流最小截集的标号法举例(s+,)(s+,6)(2,6)(3+,1)(4+,

6、1)(s+,)(s+,5)(2+,2)(5,2)(4+,2)123456tss123456t最大流最小截集的标号法举例(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的最大流量,并找出该网络的最小割.6.5中国邮

7、递员问题一个邮递员从邮局出发分送邮件，要走完他负责的所有街道，最后再返回邮局。应如何选择路线，才能使所走的路线最短，这就是中国邮递员问题。1962年，管梅谷先生提出中国邮递员问题。中国邮递员问题用图论的观点来看就是：在一个赋权连通图中，找一个过每边至少一次的闭链（圈），并且使闭链的权最小。它的算法与一笔画问题有关。一、一笔画问题有关一笔画问题有如下结论：1.一个连通图中的顶点都是偶点，没有奇点，则该图可以一笔画出。2.一个连通图中的顶点恰有两个奇点，其余都是偶点，则从任一奇点出发，则可以一笔画出该图。3.一个连通图中的顶点有两个以上是奇点，则该图不能一笔画

8、出。图中的顶点都是偶点，没有奇点，则该图可以一笔画出。图中的顶点都