发布时间 : 星期三 文章流的概念及算法-Read更新完毕开始阅读
第一讲 流的概念及算法
一、概念 1. 什么是流
将目标由一个地点运送至另一个地点叫流。 从图的角度：流是一条途径。 2. 发点，收点，单位
3. 有容量的弧：通过弧的单位流量的数量是有限的。
最大容量：c(x, y) 费用：a (x, y)
网络：图中的每条弧都带有一个容量。 4. 弧的流：f (x, y)
分类：N, I, R 二、几个问题和算法 i (x, y)=c (x, y)-f (x, y) r (x, y)=f (x, y)
1. 可以追加的单位流量 I1? 例
min{i{x,y)}
(x,y)?Ps 1 2 t i (s,1)=5 i (1,2)=3 i (2,t)=1 I1?min(i(s,1),i(1,2),i(2,t))?min5,(3,1)?1
2. 可以减少的单位流量 I2? 例
min{r(x,y}
(x,y)?P's 1 2 t
r (1, s)=1 r (2, 1)=3 r (t, 2)=5 I2?min{r(1,s),r(2,1),r(t,2)}?min1,{3,5}?1
3. 如何增加从s至t的净流
前向弧，后向弧
I3?min{min[i(x,y):(x,y)为前向弧]，min[r(x,y):(x,y)为后向弧
s 1 2 3 4 t
i (s, 1)=4 i (1, 2)=3 r (3, 2)=5 r (4, 3)=2 i (4, t)=3
I3=min{min[i (s, 1), i (1, 2), i (4, t)], min[r (3, 2), r (4, 3) ]}
=min{min[4, 3, 3], min[5, 2]}=2
流的增值链：可以运送追加单位流量的弧称为流的增值链。 4. 算法
a) 主要思想：从发点s生长出一棵由已着色的弧组成的树，追加的单位流量可以沿着
这些弧从s运出。 b) 增值算法：
I. 确定集合N、I、R中的元素，对s着色。
II. 按下列规则，对弧和顶点着色，直至t被着色或不可能再进行着色为止：如果
顶点x已着色，y未着色，则在下列情况之一时，可对顶点y和弧(x, y)着色： 1) 如果弧(x, y)?I，则对顶点y和弧(x, y)着色；如果(x, y)?I，则对y和弧(x,
y)不着色。
2) 如果弧(x, y)?R，则对顶点y和弧(y, x)着色。
如果t被着色，则从s至t存在一条由已着色弧组成的唯一链，此链即流的增值链。否则，如在算法终止以后，t仍未被着色，则从s至t不存在流的增值链。终止。
c) 例
a b s t c
d
i (s, a)=4, r (s, c)=1, i (a, c)=3, r (a, b)=7, i (b, t)=2, r (c, d)=5, r (b, d)=3, r (s, a)=6, r (b, c)=2
最大流的增值链为：
a b s t c
d
最大流的增值为
min{ i (s, a), i (a, c), r(b, c), i (b, t)} =min{4,3,2,2}=2 d) 证明
I. 引理7-3 如果算法对t已着色，则从s至t存在一条流的增值链。
II. 引理7-4 如果算法不能对t着色，则从s至t不存在任一条流的增值链。 III. 引理7-5 算法在有限步内可终止。
IV. 定理7-3 对于给定的图，算法可以找到（如果存在的话）一条流的增值链。
第二讲 最大流算法
1．最大流问题 (maximum flow problem）
在一个有容量的图中，从发点s到收点t，找到一条可以运送最大数量的单位流量的途径，并且不超过弧的容量。
从s至t的每一个流都必须满足下列三个条件：
(1) 在从s至t的任一个流中，从每个顶点x (x≠ s, x≠ t) 出去的单位数量必须等于 到达x的单位数量，即
y?X?f(x,y)-?f(y,x)=0 （x≠s,x≠t) (1)
y?X其中X是G中所有顶点的集合，f(x, y)表示经弧(x, y)运输的单位数量。
（2）经弧(x, y)运输的流的单位数量不大于弧(x, y)的容量c(x, y),即 0≤f(x, y) ≤ c(x, y) (x, y) ∈ E (2) 其中E是所有弧的集合。
(3)从发点流出的单位流量的净数V必等于流入收点的单位流量的净数，即
y?X?f(s,y)-?f(y,s)=V (3)
y?Xy?X?f(y,t)-?f(t,y)=V (4)
y?X 满足这三个条件的数值f(x, y)的集合必对应于从s至t的流。
如果可以找到一个满足这四个条件的数值f(x, y)的集合，(x, y)∈E，则这些数值对应于从s至t的流。因此，当(x, y)∈E时，数值f(x, y)的集合是一个流，当且仅当这个集合满足关系式（1）へ（4）时。
上面提到的最大流问题就是求V的最大植。也就是V在关系式（1）へ（4）的约束条件下，求V的最大植。这是一个线性规划问题，这里不用单纯形方法，而用一个比较直观的方法求解，称为最大流算法。
2. 最大流的算法 (1) 算法的思路
从s至t的任一个流（可以是零流）开始，用流的增值算法寻找流的增值链。如果找一条s至t的流的增值链，则沿着这条链运送尽可能多的单位流量。然后再找另一条流的增值链，…。如果再也找不到流的增值链，则算法终止。现有的从s至t的流就是从s至t的最大流。
(2) 算法7-8 最大流的算法
第1步 选择任一个从s至t的起始流，即选择满足式（1）へ式（4）的f(x, y)数值的任一个集合。对所有(x, y)也可以选择f(x, y)=0作为起始流/
第2步 如果f(x, y) i(x, y)=c(x, y)-f(x, y), (x, y) ∈I 如果f(x, y)>0，则令 r(x, y)=f(x, y), (x, y) ∈R 第3步 对于第2步确定的集合I和R，执行算法7-7。执行算法7-7后如找不到流的增值链，则算法7-8终止；现有的流就是最大流。否则，沿着算法7-7所发现的流的增值链，做出最大可能流的增值。返回第二步。 3. 实例 [例] 给定有弧容量的图如图7-20所示，用算法7-8找出从s至t的最大流。 c 4 1 2 3 2 s a b t 3 图 7-20 有弧容量的图