大学精品课件：第八章 图论（第5节）.ppt

1、第第1页页输油管道网如下图所示，输油管道网如下图所示，vs 为起点，为起点，vt 为终点，为终点，v1、v2、v3、v4为中转站，边上的数表示该管道的最为中转站，边上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使大输油能力，问应如何安排各管道输油量，才能使从从 vs 到到 vt 的总输油量最大？的总输油量最大？第第2页页1058435631117vsv1v2v3v4vt第第3页页管道网络中，每边的最大通过能力是有限的，实际管道网络中，每边的最大通过能力是有限的，实际流量也并不一定等于容量，上述问题就是要讨论如流量也并不一定等于容量，上述问题就是要讨论如何利用装置的能力，以使得流

2、量最大，这类问题通何利用装置的能力，以使得流量最大，这类问题通常称为最大流问题。常称为最大流问题。第第4页页网络最大流问题是一类应用极为广泛的问题，例如网络最大流问题是一类应用极为广泛的问题，例如交通运输网络中有人流、车流、货物流，供水网络交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中现金流，通讯系统中有信息中有水流，金融系统中现金流，通讯系统中有信息流等等。流等等。50年代福特（年代福特（Ford）、富克逊（）、富克逊（Fulkerson）建立）建立了了“网络流理论网络流理论”，是网络应用的重要组成部分。，是网络应用的重要组成部分。第第5页页1.容量网络容量网络设有一个有向

3、图设有一个有向图 D=(V,A)，D 中每条弧（中每条弧（vi,vj）上均）上均有非负数：有非负数：V 中有一个入次为中有一个入次为 0 的点的点 vi 指称为发点；指称为发点；V 中有一个出次为中有一个出次为 0 的点的点 vj 指称为收点；指称为收点；除了发点和收点之外的其余点称为中间点；除了发点和收点之外的其余点称为中间点；D 中每一条弧（中每一条弧（vi,vj）上均有一个非负数）上均有一个非负数 cij 0，称，称为弧的容量。为弧的容量。第第6页页称具有上述特征的有向图称具有上述特征的有向图 D 称为容量网络称为容量网络，记为，记为 D=(V,A,C)。例：例：105843563111

4、7v1v2v3v4v5v6第第7页页v1 为收点；为收点；v6 为发点；为发点；v2、v3、v4、v5为中间点；为中间点；c12=10，c13=8，c23=4，c24=5，c25=3，c34=5，c35=6，c46=11，c54=3，c56=17。第第8页页2.弧上的流量弧上的流量 在容量网络在容量网络 D 中的任一弧中的任一弧(vi,vj)上均有一个数上均有一个数 fij，称为弧，称为弧(vi,vj)上的流量。上的流量。3.流流 容量网络容量网络 D 中所有弧上的流量的集合中所有弧上的流量的集合 f=fij，称为网络称为网络 D 上的一个流。上的一个流。第第9页页5231213362v1v2

5、v3v4v5v6弧上数字为流量，而非容量弧上数字为流量，而非容量第第10页页弧上的流量分别为：弧上的流量分别为：f12=5，f13=3，f23=1，f24=2，f25=2，f34=1，f35=3，f46=3，f54=3，f56=2。流为：流为：f=f12=5，f13=3，f23=1，f24=2，f25=2，f34=1，f35=3，f46=3，f54=3，f56=2第第11页页4.可行流可行流 满足如下条件的流满足如下条件的流 f 称为可行流：称为可行流：（1）容量限制条件：）容量限制条件：对对 D 中每条弧中每条弧(vi,vj)，有，有 0fijcij。第第12页页(10,5)(5,2)(8,

6、3)(4,1)(3,2)(5,1)(6,3)(3,3)(11,6)(17,2)v1v2v3v4v5v6每条弧每条弧(vi,vj)上的流均上的流均 0fijcij，满足容量限，满足容量限制条件。制条件。第第13页页 对对 D 中的发点中的发点 vs 和收点和收点 vt：有：有 iitjsjff（即从发点（即从发点 vs 发出的流的总量等于发出的流的总量等于 vi 点输入的流的总量）点输入的流的总量）（2）平衡条件：）平衡条件：对对 D 中任一中间点中任一中间点 vi：有：有 kkijijff（即中间点（即中间点 vi 的流的输入量和输出量相等）的流的输入量和输出量相等）第第14页页(10,5)(

7、5,2)(8,3)(4,1)(3,2)(5,1)(6,3)(3,3)(11,6)(17,2)v1v2v3v4v5v6对任意节点均满足对任意节点均满足 平衡条件。平衡条件。第第15页页5.可行流的总流量可行流的总流量 容量网络容量网络 D 中发点中发点 vs 的净输出量或收点的净输出量或收点 vt 的净输的净输入量，称为可行流的总流量，记为入量，称为可行流的总流量，记为 W，即，即 Wffiitjsj 第第16页页例：例：(10,5)(5,2)(8,3)(4,1)(3,2)(5,1)(6,3)(3,3)(11,6)(17,2)v1v2v4v6v3v5第第17页页弧上的流量分别为：弧上的流量分别为

8、：f12=5，f13=3，f23=1，f24=2，f25=2，f34=1，f35=3，f46=3，f54=3，f56=2。流为：流为：f=f12=5，f13=3，f23=1，f24=2，f25=2，f34=1，f35=3，f46=3，f54=3，f56=2由可行流的两个条件可以判断出该流为可行流。由可行流的两个条件可以判断出该流为可行流。该可行流的总流量为：该可行流的总流量为：W=8 第第18页页6.可行流的性质可行流的性质 可行流总是存在的。可行流总是存在的。如如 f=0 就是一个总流量为就是一个总流量为 0 的可行流。的可行流。7.最大流最大流 最大流问题就是在容量网络最大流问题就是在容量

9、网络 D=(V,A,C)中中寻找流量寻找流量 W 最大的可行流最大的可行流 f=fij 。第第19页页8.零流弧、非零流弧、饱和弧、非饱和弧零流弧、非零流弧、饱和弧、非饱和弧 若给出一个可行流若给出一个可行流 f=fij ：（1）使使 fij=0 的弧称为零流弧；的弧称为零流弧；（2）使使 fij 0 的弧称为非零流弧；的弧称为非零流弧；（3）使使 fij=cij 的弧称为饱和弧；的弧称为饱和弧；（4）使使 fij 0。),(,),(,),(,*jiijjiijjiijijvvfvvfvvff令令第第29页页不难验证不难验证 f*f*ij 仍满足容量限制条件和仍满足容量限制条件和平衡条件，故平

10、衡条件，故 f*仍为一可行流，其流量仍为一可行流，其流量 W*=W*+，这与，这与 f*是最大流的假设矛盾。是最大流的假设矛盾。第第30页页2.标号算法流程标号算法流程 算法步骤采用了为各顶点标号的方式。每个顶点的算法步骤采用了为各顶点标号的方式。每个顶点的标号包含两部分：标号包含两部分：第一部分：该顶点的标号是从哪一个顶点得到的。第一部分：该顶点的标号是从哪一个顶点得到的。第二部分：调整量。第二部分：调整量。第第31页页（1）标号过程（通过标号来寻找增广链）标号过程（通过标号来寻找增广链）给发点给发点 vs 标上标上 ss ),0(任取一个已标号的顶点任取一个已标号的顶点 vi 进行检查：进

11、行检查：对以对以 vi 为始点的所有关联弧为始点的所有关联弧(vi,vj)：若终点：若终点vj 未标号，且未标号，且 fij 0，则给，则给 vj 标号标号,min ),(ijijjifv 重复，直到收点重复，直到收点 vt 被标号或不再有顶点可被标号或不再有顶点可标号为止。标号为止。第第33页页 若收点若收点 vt 被标号，说明存在一条增广链，从被标号，说明存在一条增广链，从 vt开始，利用反向追踪的方法可以找出一条增广链开始，利用反向追踪的方法可以找出一条增广链，转步骤（，转步骤（2）；）；若收点若收点 vt 未被标号，而标号过程无法进行时，说未被标号，而标号过程无法进行时，说明明 f 已

12、经是最大流了。已经是最大流了。第第34页页（2）调整过程（沿增广链调整各段弧上的流量）调整过程（沿增广链调整各段弧上的流量）不不在在增增广广链链上上若若为为增增广广链链上上的的后后向向弧弧若若为为增增广广链链上上的的前前向向弧弧若若),(,),(,),(,jiijjitijjitijijvvfvvfvvff 去掉所有标号，回到步骤（去掉所有标号，回到步骤（1），对可行流），对可行流f 重新标号重新标号 令令第第35页页v2vsv1v3v4vt(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(2,1)(5,3)例：例：求下列网络的最大流求下列网络的最大流 第第36页页（1）

13、标号过程）标号过程 给发点给发点 vs 标上标上 ),0(s 检查发点检查发点 vs：弧弧(vs,v1)：终点：终点 v1 未标号，且未标号，且 fs1=1 0，给，给 v2 标号标号 11,4min1,min ),(1221 v弧弧(v1,v3)：终点：终点 v3 未标号，且未标号，且 f13=2=c13=2，不给，不给 v3 标号标号 第第38页页 检查顶点检查顶点 v2：弧弧(v3,v2)：始点：始点 v3 未标号，且未标号，且 f32=1 0，给，给 v3 标号标号 11,1min1,min ),(2332 v弧弧(v2,v4)：终点：终点 v4 未标号，且未标号，且 f24=3 c2

14、4=4，给，给 v4 标号标号 11,1min34,min ),(2442 v第第39页页 任选一个顶点任选一个顶点 v4，检查顶点，检查顶点 v4：弧弧(v4,vt)：终点：终点 vt 未标号，且未标号，且 f4t=3 c4t=5，给给 vt 标号标号 12,1min35,min ),(44 ttv vt 已标号，按反向追踪法寻找增广链为：已标号，按反向追踪法寻找增广链为：（vs,v1,v2,v4,vt）第第40页页v2vsv1v3v4vt(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(2,1)(5,3)(0,+)(vs,4)(-v1,1)(v2,1)(v4,1)利用

15、反向追踪法寻找最短路利用反向追踪法寻找最短路(-v2,1)第第41页页v2vsv1v3v4vt(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(2,1)(5,3)(0,+)(vs,4)(-v1,1)(v2,1)(v3,1)利用反向追踪法寻找最短路利用反向追踪法寻找最短路(-v2,1)第第42页页（2）调整过程）调整过程 v2vsv1v3v4vt(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(2,1)(5,3)2111 ssff012121 ff412424 ff4144 ttff第第43页页其余弧上的流量保持不变，从而得到如下流量图：其余弧上的流量

16、保持不变，从而得到如下流量图：v2vsv1v3v4vt(3,3)(5,2)(1,0)(4,4)(1,1)(2,2)(3,0)(2,1)(5,4)第第44页页v2vsv1v3v4vt(3,3)(5,2)(1,0)(4,4)(1,1)(2,2)(3,0)(2,1)(5,4)对上述新得到的流量图，进行重新标号对上述新得到的流量图，进行重新标号第第45页页（3）标号过程）标号过程 给发点给发点 vs 标上标上 ),0(s 检查发点检查发点 vs：弧弧(vs,v1)：终点：终点 v1 未标号，且未标号，且 fs1=2 M 中的弧数，则称中的弧数，则称 M 为为 D 的最大匹配。的最大匹配。第第86页页工

17、作分配问题可以转化为求二部图的最大匹配问题：工作分配问题可以转化为求二部图的最大匹配问题：点集点集 X=x1、x2、xm 表示：表示：m 个工人个工人点集点集 Y=y1、y2、yn 表示：表示：n 件工作件工作弧集弧集Y=(xi,yj)表示：第表示：第 xi 个工人能做第个工人能做第 yj 件工作。件工作。从而，工作分配问题就转化为求二部图从而，工作分配问题就转化为求二部图 D=(X,Y,A)的最大匹配问题。的最大匹配问题。第第87页页3.最大匹配问题的求解方法最大匹配问题的求解方法 求解二部图中的最大匹配可以转化为多发点多收求解二部图中的最大匹配可以转化为多发点多收点最大流问题，进而进行求解

18、。点最大流问题，进而进行求解。转化步骤：转化步骤：（1）在二部图中增加两个新点）在二部图中增加两个新点 vs 和和 vt 分别做为发分别做为发点和收点；点和收点；第第88页页（2）用弧把）用弧把 vs 与原二部图中的顶点与原二部图中的顶点 x1、x2、xm 相连；把相连；把 vt 与原二部图中的顶点与原二部图中的顶点 y1、y2、yn 相连；相连；（3）令全部弧上的容量均为）令全部弧上的容量均为 1。（4）从而构造出一个容量网络。求出该容量网络）从而构造出一个容量网络。求出该容量网络的最大流，如果弧的最大流，如果弧(xi,yj)上的流量为上的流量为 1，就让，就让 xi 做做yj，这样得到的方

19、案就是最大匹配方案。，这样得到的方案就是最大匹配方案。第第89页页例：有例：有 5 位待业者，位待业者，5 项工作，他们各自能胜任项工作，他们各自能胜任工作情况如下图所示，要求设计一个就业方案，工作情况如下图所示，要求设计一个就业方案，使尽量多的人能就业。使尽量多的人能就业。x1x2vsvtx3x4x5y1y2y3y4y5第第90页页解：初始可行流为解：初始可行流为 0 流。流。(1,0)(1,0)x1x2vsvtx3x4x5y1y2y3y4y5(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)

20、(1,0)(1,0)(1,0)第第91页页（1）寻找增广链并调整量。）寻找增广链并调整量。(1,0)(1,0)x1x2vsvtx3x4x5y1y2y3y4y5(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(0,+)(vs,1)(x1,1)(y1,1)(1,1)(1,1)(1,1)第第92页页(1,0)(1,0)x1x2vsvtx3x4x5y1y2y3y4y5(1,1)(1,1)(1,0)(1,0)(1,0)(1,1)(1,0)(1,0)(1,0)(1,0)(1,

21、0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(0,+)(vs,1)(x2,1)(y4,1)(1,1)(1,1)(1,1)（2）寻找增广链并调整量。）寻找增广链并调整量。第第93页页(1,1)(1,0)x1x2vsvtx3x4x5y1y2y3y4y5(1,1)(1,1)(1,1)(1,0)(1,0)(1,1)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,0)(1,1)(1,0)(1,0)(1,0)(1,0)(0,+)(vs,1)(x3,1)(y5,1)(1,1)(1,1)(1,1)（3）寻找增广链并调整量。）寻找增广链并调整量。第第94页页(1,

22、1)(1,1)x1x2vsvtx3x4x5y1y2y3y4y5(1,1)(1,1)(1,1)(1,0)(1,0)(1,1)(1,0)(1,0)(1,1)(1,0)(1,0)(1,0)(1,1)(1,1)(1,0)(1,0)(1,0)(1,0)（4）寻找增广链并调整量。）寻找增广链并调整量。(1,1)(1,1)(1,1)(1,0)(1,1)(1,0)(1,1)(1,0)(1,1)第第95页页(1,1)(1,1)x1x2vsvtx3x4x5y1y2y3y4y5(1,0)(1,1)(1,1)(1,1)(1,0)(1,1)(1,1)(1,0)(1,1)(1,0)(1,0)(1,1)(1,0)(1,0)(1,1)(1,0)(1,1)(1,1)（5）寻找增广链并调整量。）寻找增广链并调整量。无法找到增广链，当前流即是最大流。无法找到增广链，当前流即是最大流。第第96页页无法找到增广链，可标号的点有无法找到增广链，可标号的点有 vs、x5、x4、x3、y4、y5，割集为，割集为 (vs,x1),(vs,x2),(y4,vt),(y5,vt)，割量为，割量为 4。x1、x2、x3、x4 分别干分别干 y2、y1、y4、y5 工作。工作。