网络流的增广路算法和预流推进算法.ppt

网络流的增广路算法和预流推进算法
第一页，课件共92页
一些符号和定义
V表示整个图中的所有结点的集合.
E表示整个图中所有边的集合.
G = (V,E) ,表示整个图.
s表示网络的源点,t表示网络的汇点.
对于每条边(u,v),有一个容量c(u,v) (c(u,v)>=0)
如果c(u,v)=0，则表示(u,v)不存在在网络中。
如果原网络中不存在边(u,v)，则令c(u,v)=0
对于每条边(u,v),有一个流量f(u,v).
第二页，课件共92页
v1
t
s
v2
(2,2)
(4,4)
(2,4)
(0,3)
(2,2)
,左边的数字表示这条管道的当前流量.
第三页，课件共92页
网络流的三个性质
1、容量限制: f[u,v]<=c[u,v]
2、反对称性：f[u,v] = - f[v,u]
3、流量平衡: 对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。
结合反对称性,流量平衡也可以写成:

只要满足这三个性质,就是一个合法的网络流.
第四页，课件共92页
最大流问题
定义一个网络的流量（记为|f|）=
最大流问题，就是求在满足网络流性质的情况下，|f|的最大值。
第五页，课件共92页
残量网络
为了更方便算法的实现，一般根据原网络定义一个残量网络。其中r(u,v)为残量网络的容量。
r(u,v) = c(u,v) – f(u,v)
通俗地讲：就是对于某一条边（也称弧），还能再有多少流量经过。
Gf残量网络,Ef表示残量网络的边集.
第六页，课件共92页
例1
v1
t
s
v2
(2,2)
(4,4)
(2,4)
(0,3)
(2,2)
v1
t
s
v2
2
3
2
4
2
2
原网络 (a,b)表示(流量f,容量c)
残量网络（如果网络中一条边的容量为0,则认为这条边不在残量网络中。r(s,v1)=0,所以就不画出来了。另外举个例子：r(v1,s) = c(v1,s) – f(v1,s) = 0 – (-f(s,v1)) = f(s,v1) = 4.
图1
图2
第七页，课件共92页
例1
从残量网络中可以清楚地看到：
因为存在边(s,v2) = 3,我们知道从S到v2还可以再增加2单位的流量；
因为存在边(v1,t) = 2,我们知道从v1到t还可以再增加2单位的流量。
v1
t
s
v2
2
3
2
4
2
2
第八页，课件共92页
后向弧
其中像(v1,s)这样的边称为后向弧,它表示从v1到s还可以增加4单位的流量。
但是从v1到s不是和原网络中的弧的方向相反吗？显然“从v1到s还可以增加4单位流量”这条信息毫无意义。那么，有必要建立这些后向弧吗？
v1
t
s
v2
2
3
2
4
2
2
第九页，课件共92页
为什么要建立后向弧
显然，例1中的画出来的不是一个最大流。
但是，如果我们把s -> v2 -> v1 -> t这条路径经过的弧的流量都增加2,就得到了该网络的最大流。
注意到这条路径经过了一条后向弧:(v2,v1)。
如果不设立后向弧，算法就不能发现这条路径。
从本质上说，后向弧为算法纠正自己所犯的错误提供了可能性，它允许算法取消先前的错误的行为（让2单位的流从v1流到v2)
第十页，课件共92页