最大流 标号法[优质ppt]

9
6 统筹法 （PERT+CPM） ）
• 一种组织管理技术 • PERT (Program Evaluation and Review Technique) + CPM (Critical Path Method) • 20世纪40年代产生; 20世纪40年代产生 世纪40年代产生; • 20世纪50年代, 美国海军武器局1958年研制“北极星” 20世纪50年代 美国海军武器局1958年研制“北极星” 世纪50年代, 1958年研制 导弹时使用PERT 节约时间2 1956美国杜邦公司 导弹时使用PERT ，节约时间2年；1956美国杜邦公司 制订企业不同部门的系统规划创立CPM Apolo登月 CPM； 登月； 制订企业不同部门的系统规划创立CPM；Apolo登月； • 1963年起得到推广和发展。 1963年起得到推广和发展。 年起得到推广和发展 • 我国：华罗庚1964开始，1970 s推广；1979 南京军区 我国：华罗庚1964开始，1970’s推广； 1964开始
3、重复步骤 2，可能出现两种情况： 、 ，可能出现两种情况：
(1) 顶点 t 尚未标号，但无法继续标记，说明网路中已不存在增广链， 尚未标号，但无法继续标记，说明网路中已不存在增广链， 就是最大流； 当前流 v(f) 就是最大流；所有获标号的顶点在 V 中，未获标号顶 间的弧即为最小截集； 点在 V 中，V 与 V 间的弧即为最小截集；算法结束 (2)顶点 t 获得标号，找到一条增广链，由顶点 t 标号回溯可找出该增 顶点 获得标号，找到一条增广链， 4 广链； 广链；到第二步
) 14 4,
1
(16,15)
(3,1 )
(1 ) 6 2 3,1 ( 22 ,22 )
(1

货物从vs运送到vt.要求指定一个运输方案，使得从vs到vt
的货运量最大，这个问题就是寻求网络系统的最大流问
题。
3
定义20 设一个赋权有向图G=（V,E）,对于G中的 每一个边（弧）（vi ,vj）∈E,都有一个非负数cij叫 做边的容量。在V 中一个入次为零的点称为发点vs， 一个出次为零的点称为收点vt ,其它的点叫做中间点。
为: S , S , S S V , S S ,发点vs∈S,收点vt∈ /S ,满足
1.G=（V，E- E'）不连通； 2. E''为 E' 的真子集，而G=（V，E- E'）' 连通； 那么 E' 为G的割集，记为 E' =(S,S )。
割集 (S, S )所有始点在S，终点在S 的容量之和，称为(S, S )的 割集容量，记为C(S, S) 。
13
1． 标号过程 在标号过程中，网络中的每个标号点的标号包
含两部分：第一个标号表示这个标号是从那一点得 到的，以便找出增广链；第二个标号是为了用来确 定增广链上的调整量δ 。
标号过程开始，先给vs 标号（ ∆ ，+∞），一般
地，取一个标号顶点vi，对vi所有未标号的邻接点vj
按照下面条件进行处理：
2
v1
5
v3
Cij
一、最大10流有关概念3
11
vs 连通网络4G(V, E) 有 m 个节3点, n条弧, v弧t eij 上
的流量上界为
量。 8
cij,
求5从起始节点 vs 到终点 vt 的最大流 17
v2
6
v4
图是联结某个起始地vs和目的地vt的交通运输网，每

第i年 价格 ai 使用寿命 费用 bi 1 11 0－1 b1 5 2 11 1－2 b2 6 3 12 2－3 b3 8 4 12 3－4 b4 11 5 13 4－5 b5 18
最短路径问题的应用

例 设备更新问题
把求总费用最小问题化为最短路径问题。用点 i (i=1,2,3,4,5)表示第 i 年买进一台新 设备。增设一点 6 表示第五年末。从i点到i+1,……, 6 各画一条弧，弧（i , j）表示在 第 i 年买进的设备一直使用到第 j 年年初（第 j －1年年末）。求1点到6点的最短路径。 路径的权数为购买和维修费用。 弧（i , j）的权数为第i年的购置费ai＋从第i年使用至第j-1年末的维修费之和。 从第i年使用至第j-1年末的维修费：b1+…+bj-i
1 1 2 3 4 5 2 16 3 22 16
（使用寿命为j-i年） 具体权数计算结果如下：
5 41 30 23 17 6 59 41 31 23 18
如：（2－4）权数为：a2+b1+b2=11＋5＋6=22
4 30 22 17
通过一个网络的最短路径

例 设备更新问题 ：
2 16 30 22 41 4 23

最大流问题
两个重要结论： 1、任何一个可行流的流量都不会超过任一截集的容量。 2、若对于一个可行流f *，网络中有一个截集（ V1*，V1*）， 使v（ f *）=C(V1*，V1 *)，则f *必是最大流，而（ V1*， V1 *）必是所有截集中容量最小的一个，即最小截集。
定理：可行流f *是最大流，当且仅当不存在关于f *的增广链。 于是有如下结论：最大流量最小截量定理：任一个网络中，从vs 到vt的最大流量等于分离vs，vt的最小截集的容量。

割是分离A和F的弧的集合,若切断一个割的所有弧对应的桥梁, 就可切断A和F之间的线路。切断最小割包含的弧对应的桥 梁，是切断A和F之间线路的桥梁数最少的方法。
由最大流最小割定理，分离A和F的最小割容量等于由A到F的 最大流量 A(0,+) 1,1 2 ,1 1 1, 1,0 2,1 D 2,0 B E C 1,1 2,0 (B,1) (A,1) 1 2, 2,1 F 由上图得知：已标号点为A，B，C，而D，E，F不能获得标 号，从而知道该最大流对应的最小割为{（A，E），（C， D），（C，F）}因此，切断AE，CD，CF三座桥梁，即可阻 止对方部队过河。
3 3 2 v4
割 集 容量 6 7 7 5 11 8 最小割 { (v1, v2) , ( v1, v3) } { (v1, v3) , ( v2, v5) } { (v1, v2 ) , ( v3, v2) , (v3,v4 ) } { (v2, v5) , ( v3, v4) } {(v1, v2) , ( v3, v2),(v4,v2) , (v4,v5)} { (v2 , v5 ) , ( v4 , v5 ) }
• 割中所有弧的容量之和称为该割的容量
C (V1 ,V2 )
( v i , v j )(V1 ,V2 )

c ij
所有割中容量最小的称为最小割
v2 2 v1 4 v3
V1 {v1} {v1,v2} {v1,v3} { v1,v2,v3 } {v1,v3 ,v4 } {v1 ,v2 ,v3, v4} V2 { v2 ,v3 ,v4 , v5 } { v3 ,v4 ,v5 } {v2 ,v4, v5} { v4, v5 } { v2 ,v5 } { v5 }
1,1