文档介绍：图论算法 ---最大流问题
整理ppt
1
运输网络
现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。
每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？
4
2
4
8
4
7
3
6
2
1
S
T
V1
V2
V3
V4
公路运输图
整理ppt
2
基本概念
这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。
若有向图G=(V,E)满足下列条件：
有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。
有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。
每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。
则称之为网络流图，记为G = (V, E, C)
整理ppt
3
可行流
可行流
对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。
1. 每一条弧(i,j)有fij≤Cij
2. 流量平衡
除源点S和汇点T以外的所有的点vi，恒有：
∑j(fij)= ∑k(fjk)
该等式说明中间点vi的流量守恒，输入与输出量相等。
3. 对于源点S和汇点T有，
∑i(fSi)= ∑j(fjT)= V(f)
整理ppt
4
可增广路
给定一个可行流f={fij}。若fij = Cij，称<vi, vj>为饱和弧；否则称<vi, vj>为非饱和弧。若fij = 0，称<vi, vj>为零流弧；否则称<vi, vj>为非零流弧。
定义一条道路P，起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。
譬如在图中，P = (S, V1, V2, V3, V4, T)，那么
P+ = {<S, V1>, <V1, V2>, <V2, V3>, <V4, T>}
P- = {<V4, V3>}
给定一个可行流f，P是从S到T的一条道路，如果满足：
fij是非饱和流，并且<i,j>∈ P+ , fij是非零流，并且<i,j>∈ P-
那么就称P是f的一条可增广路。之所以称作“可增广”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。
整理ppt
5
剩余图(残余网络)
剩余图G’=(V,E’)
流量网络G=(V,E)中，对于任意一条边(a,b)，若
flow(a,b)<capacity(a,b) or flow(b,a)>0
则(a,b)∈ E’
可以沿着a--->b方向增广
整理ppt
6
剩余图中，从源点到汇点的每一条路径都对应一条增广路
Capacity=5
Capacity=6
Capacity=2
Flow=2
Flow=2
Flow=2
有向图
3
2
2
2
4
剩余图
剩余图中，每条边都可以沿其方向增广
剩余图的权值代表能沿边增广的大小
整理ppt
7
G = (V, E, C)是已知的网络流图，设U是V的一个子集，W = V\U，满足S ∈ U，T∈W。即U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合。
对于弧尾在U，弧头在W的弧所构成的集合称之为割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，记为C（U，W），即：
割切
整理ppt
8
割切示例
上例中，令U = {S, V1}，则W = {V2, V3, V4, T}，那么，
C(U, W) = <S, V2> + <V1, V2> + <V1, V3>+<V1, V4> =8+4+4+1=17
整理ppt
9
流量算法的基本理论
定理1：对于已知的网络流图，设任意一可行流为f，任意一割切为(U, W)，必有：V(f) ≤ C(U, W)。
定理2：可行流f是最大流的充分必要条件是：f中不存在可改进路。
定理3：整流定理。
如果网络中所有的弧的容量是整数，则存在整数值的最大流。
定理4：最大流最小割定理。
最大流等于最小割，即max V(f) = min C(U, W)。
整理ppt
10