第4节 网络最大流问题

1、公路系统中的车辆流公路系统中的车辆流 控制系统中的信息流控制系统中的信息流 供水系统中的水流供水系统中的水流 金融系统中的现金流金融系统中的现金流 问题背景问题背景 网络最大流问题问题的提出 n网络中存在流量限制时，求解一条线路使网络中存在流量限制时，求解一条线路使 得从得从起点起点与与终点终点之间可通过的之间可通过的流量最大流量最大。 v1 v2 v3 v4 v5 v6 10 8 4 6 5 3 5 3 11 17 例：上图为例：上图为v1到到v6的一交通网，权表示相应运输线的最大的一交通网，权表示相应运输线的最大 通过能力，制定一方案，使从通过能力，制定一方案，使从v1运到运到v6的运输产

2、品数量最的运输产品数量最 多。多。 设有网络设有网络d=(v, a, c)，其中，其中c=cij， cij为弧为弧(vi,vj) 上的上的容量容量，现在，现在d上要通过一个流上要通过一个流f=fij， fij为弧为弧 (vi,vj)上的上的流量流量。 问题：问题：如何安排如何安排fij，可使网络，可使网络d上的总流量最大？上的总流量最大？ v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 一、一般提法：一、一般提法： max v=v（f） ijij cf 0 tsi tifv sifv ff jj jiij ,0 )( )

3、( 容量约束容量约束 平衡约束平衡约束 s.t. v2 vs v3 v4 v5 vt 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 注：满足两约束条件的流注：满足两约束条件的流f称为可行流，称为可行流，v(f)称为该可行流的流量称为该可行流的流量 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 1 1 3 3 6 2 饱和弧饱和弧 fij=cij 非饱和弧非饱和弧 fijcij 零流弧零流弧 fij=0 非零流弧非零流弧 fij0 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11

4、6 3 5 3 1 2 2 1 3 3 6 2 f为一可行流，为一可行流，u为为vs至至vt的链，令的链，令 u+=正向弧正向弧， u-=反向弧反向弧。若。若u+中弧中弧 皆非饱和皆非饱和，且，且u-中弧皆非零，则称中弧皆非零，则称u为关于为关于f 的一条的一条增广链增广链。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 f为一可行流，为一可行流，u为为vs至至vt的链，令的链，令 u+=正向弧正向弧， u-=反向弧反向弧。若。若u+中弧中弧 皆非饱，且皆非饱，且u-中弧皆非零，则称中弧皆非零，则称u为关于为关于f的的

5、 一条一条增广链增广链。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 2 f为一可行流，为一可行流，u为为vs至至vt的链，令的链，令 u+=正向弧正向弧， u-=反向弧反向弧。若。若u+中弧中弧 皆非饱，且皆非饱，且u-中弧皆非零，则称中弧皆非零，则称u为关于为关于f的的 一条一条增广链增广链。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 1 2 2 1 3 3 6 1 f为一可行流，为一可行流，u为为vs至至vt的链，令的链，令 u+=正向弧正向弧， u-=反向弧反向弧。

6、若。若u+中弧中弧 皆非饱，且皆非饱，且u-中弧皆非零，则称中弧皆非零，则称u为关于为关于f的的 一条一条增广链增广链。 v2 v1 v3 v4 v5 v6 8 10 4 17 5 5 3 11 6 3 5 3 3 2 0 1 5 3 6 2 把把v分成两部分：分成两部分：va和和vb(va vb= , va vb= v) 且且vs va、 vt vb，则弧集，则弧集(va,vb)称为称为d的的截集（割集）截集（割集）。 截集上的容量截集上的容量和称为和称为截量（割集容量），记为截量（割集容量），记为c(va,vb) 。 v1 vs v2 v3 v4 vt 8 10 4 17 5 5 3 11

7、 6 3 5 3 1 2 2 1 3 3 6 2 (vs,v2), (v1,v2), (v1,v3), (v1,v4)； 截量为：截量为： c(va,vb) =8+4+5+3=20 例例 若若va=vs,v1，则，则 截集为：截集为： 任一可行流的流量都不会超过任一截集的截量任一可行流的流量都不会超过任一截集的截量 即：即：v(f) c (va,vb) 。 v1 vs v2v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） 最大流最小截定理：最大流最小截定理：网络的最大流量等于最小截量。网络的最大流量等于最小截量。 (cijfij) v1 vs v2

8、v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） v1 vs v2v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） va=vs， (vs,v1), (vs,v2)，截量为：，截量为：6 v1 vs v2v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） va=vs，(vs,v1), (vs,v2)，截量为：，截量为：6 va=vs ,v1，(vs,v2), (v1,vt)，截量为：，截量为：7 v1 vs v2v3 vt （2，2） （4，3） （3，1） （

9、1，0） （3，3） （5，2） （2，2） va=vs，(vs,v1), (vs,v2)，截量为：，截量为：6 va=vs ,v1，(vs,v2), (v1,vt)，截量为：，截量为：7 va=vs ,v2，截量为：，截量为：7 v1 vs v2v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） va=vs，(vs,v1), (vs,v2)，截量为：，截量为：6 va=vs ,v1，(vs,v2), (v1,vt)，截量为：，截量为：7 va=vs ,v2，截量为：，截量为：7 va=vs ,v3，截量为：，截量为：12 v1 vs v2v3 vt

10、 （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） va=vs，(vs,v1), (vs,v2)，截量为：，截量为：6 va=vs ,v1，(vs,v2), (v1,vt)，截量为：，截量为：7 va=vs ,v2，截量为：，截量为：7 va=vs ,v3，截量为：，截量为：12 va=vs ,v1,v2，截量为：，截量为：5 v1 vs v2v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） （1）所有的截集：）所有的截集： va=vs，(vs,v1), (vs,v2)，截量为：，截量为：6 va=vs ,v1，(

11、vs,v2), (v1,vt)，截量为：，截量为：7 va=vs ,v2，截量为：，截量为：7 va=vs ,v3，截量为：，截量为：12 va=vs ,v1,v2，截量为：，截量为：5 v1 vs v2v3 vt （2，2） （4，3） （3，1） （1，0） （3，3） （5，2） （2，2） （2）最小截量最小截量min c (va,vb)= 5； （3）v(f*)=5= min c (va,vb) f*是最大流。是最大流。 理论依据：理论依据：p261,p261,推论推论 不存在关于不存在关于f的增广链的增广链可行流可行流f是最大流是最大流 网络中的所有点：网络中的所有点：标号点和未标

12、号点。标号点和未标号点。 标号点：标号点：已检查和未检查点。已检查和未检查点。 标号点包括两部分标号点包括两部分：第一个标号表明它的标第一个标号表明它的标 号的来源，以便找出增广链；第二个标号是号的来源，以便找出增广链；第二个标号是 为确定增广链的调整量。为确定增广链的调整量。 标号法的思路 所有点所有点 未标号未标号 未检查未检查 所有所有 标号点标号点 检查检查 注注: 给发点给发点vs标上（标上（0，），则），则vs成为标号未检查成为标号未检查 vi 标号标号 未检查未检查 vi 标号标号 检查检查 vj 标号标号 未检查未检查 考查考查 （vi, vj) 网络最大流问题网络最大流问题标

13、号法标号法 1.标号过程标号过程 n给vs标上(0，+)，这时vs是标号而未检查点，其余为 未标号点。 n若在弧(vi，vj)上，fij0，则给vj标(-vi，l(vj)， 其中 n于是于是vi成为标号而已检查过的点，重复上述步骤，成为标号而已检查过的点，重复上述步骤， 一旦一旦vt被标号，表明得到一条从被标号，表明得到一条从vs到到vt的增广链，转入的增广链，转入 2.调整过程调整过程 n如果所有标号已检查过，而标号不能进行下去，则算法如果所有标号已检查过，而标号不能进行下去，则算法 结束，这时可行流为最大流。结束，这时可行流为最大流。 min, jiijij l vl vcf min, j

14、iji l vl vf 网络最大流问题标号法 n1.标号过程标号过程 n2.调整过程调整过程 * * * , , , ij ij ijijijt ij ij v v f ffv vl v f v v 利用反向追踪法找出增广链。调整量为利用反向追踪法找出增广链。调整量为 = l(vt) 去掉所有的标号，对新的可行流去掉所有的标号，对新的可行流f*重新进行标号过程。重新进行标号过程。 步骤：步骤： (1)给给vs标号为标号为0,+， 流出未饱和弧流出未饱和弧(vs , vj) ,给给vj标号标号vs ,j,其中其中j=csj- fsj 或或流入非零弧流入非零弧 (vj , vs) ,给给vj标号标

15、号-vs, j ,其中其中j=fsj (cijfij)，用标号法求最大流。，用标号法求最大流。 0,+ vs, 4 选与选与vs关联的关联的 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） （3,0） (2)把节点集把节点集v分为分为 va：已标号点集：已标号点集 vb：未标号点集：未标号点集 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0 , + vs, 4 （3,0） 考虑所有弧考虑所有弧(vi , vj)或或(vj ,

16、 vi) ,其中其中vi va, vj vb，若该弧为，若该弧为 流出未饱弧流出未饱弧,则给则给vj标号标号vi , j,其中其中j=mini, cij- fij 流入非零弧流入非零弧,则给则给vj标号标号-vi , j ,其中其中j= mini, fij (3) -v1 , 1 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0 , + vs , 4 （3,0） (4) v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0 ,

17、+ vs , 4 -v1 , 1 重复（重复（2）,（3），依次进行的结局可能为），依次进行的结局可能为 vt已标号，得到一条增广链已标号，得到一条增广链u(反向追踪反向追踪)，转（，转（5）；）； vt未标号未标号,且无法再标号且无法再标号,此时的流为此时的流为最大流最大流,此时的截集此时的截集为为最小截最小截。 （3,0） v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0 , + vs, 4 -v1, 1 (4) 重复（重复（2）,（3），依次进行的结局可能为），依次进行的结局可能为 vt已标号，得到一条

18、增广链已标号，得到一条增广链u(反向追踪反向追踪)，转（，转（5）；）； vt未标号未标号,且无法再标号且无法再标号,此时的流为此时的流为最大流最大流,此时的截集此时的截集为为最小截最小截。 v2 , 1 （3,0） v3 (4) 重复（重复（2）,（3），依次进行的结局可能为），依次进行的结局可能为 vt已标号，得到一条增广链已标号，得到一条增广链u(反向追踪反向追踪)，转（，转（5）；）； vt未标号未标号,且无法再标号且无法再标号,此时的流为此时的流为最大流最大流,此时的截集此时的截集为为最小截最小截。 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2）

19、（1,1） （5,3） （2,1） （4,3） 0, + vs, 4 -v1, 1v2, 1 （3,0） v4, 1 (4) 重复（重复（2）,（3），依次进行的结局可能为），依次进行的结局可能为 vt已标号，得到一条增广链已标号，得到一条增广链u(反向追踪反向追踪)，转（，转（5）；）； vt未标号未标号,且无法再标号且无法再标号,此时的流为此时的流为最大流最大流,此时的截集此时的截集为为最小截最小截。 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0, + vs, 4 -v1, 1v2 , 1 （3,0）

20、 v4 , 1 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0, + vs, 4 -v1, 1v2, 1 （3,0） -v2, 1 v4 , 1 (5) 调整。取调整。取( ) min j tj vu l v ，令，令 uvvf uvvf uvvf f jiij jiij jiij ij ),( ),( ),( ，得新流，得新流 ij f,转转(1)。 v2 vs v1 v4 v3 vt （3,3） （5,1） （1,1） （2,2） （1,1） （5,3） （2,1） （4,3） 0, + vs, 4 -

21、v1, 1-v2, 1 （3,0） -v2, 1 v4, 1 v2 vs v1 v4 v3 vt （3,3） （5,2） （1,0） （2,2） （1,1） （5,4） （2,1） （4,4） （3,0） 调整调整 v2 vs v1 v4 v3 vt （3,3） （5,2） （1,0） （2,2） （1,1） （5,4） （2,1） （4,4） （3,0） 0 ,+ vs, 3 v2 vs v1 v4 v3 vt （3,3） （5,2） （1,0） （2,2） （1,1） （5,4） （2,1） （4,4） （3,0） 0, + vs , 3 此时标号无法进行，当前流为最大流，最大流量为此时标

22、号无法进行，当前流为最大流，最大流量为5； 最小截为最小截为(vs,v2), (v1,v3)，截量为：，截量为：5 有三个发电站有三个发电站v1,v2,v3，发电能力分别为，发电能力分别为15、10和和 40兆瓦，经输电网可把电力送到兆瓦，经输电网可把电力送到8号地区，电网能力如号地区，电网能力如 图所示。求三个发电站输到该地区的最大电力。图所示。求三个发电站输到该地区的最大电力。 v2 v1 v3 v4 v5 v6 v7 v8 40 15 30 15 45 10 15 10 20 v0 10 15 40 10 10 15 15 15 0 10 10 10 10 15 25 课堂练习课堂练习

23、例例1、图中图中a、b、c、d、e、f分别表示陆地和岛屿，分别表示陆地和岛屿， 表示桥梁及其编号。河两岸分别互为敌对的双表示桥梁及其编号。河两岸分别互为敌对的双 方部队占领，问至少应切断几座桥梁（具体指出编号）才方部队占领，问至少应切断几座桥梁（具体指出编号）才 能达到阻止对方部队过河的目的。试用图论方法进行分析。能达到阻止对方部队过河的目的。试用图论方法进行分析。 a b d e f c 实际应用实际应用 分析：转化为一分析：转化为一 个网络图，弧的个网络图，弧的 容量为两点间的容量为两点间的 桥梁数。桥梁数。 则问题为求最则问题为求最 小截。小截。 a b d e f c a b c d

24、e f 2 1 1 1 1 1 2 2 2 2 2 2 分析：转化为一分析：转化为一 个网络图，弧的个网络图，弧的 容量为两点间的容量为两点间的 桥梁数。桥梁数。 则问题为求最则问题为求最 小截。小截。 答案：答案：最小截为最小截为ae、 cd、cf a b d e f c a b c d e f 2 1 1 1 1 1 2 2 2 2 2 2 例例2、有一批人从我国有一批人从我国a城赴俄罗斯城赴俄罗斯b城，可能的旅城，可能的旅 行路线如图：行路线如图： 边防队拟建立足够数量检查站以便使每辆汽车至少边防队拟建立足够数量检查站以便使每辆汽车至少 必经过一个检查站，建立检查站的费用根据各路段条必经过一个检查站，建立检查站的费用根据各路段条 件有所不同（如图数字所示），