(0,10)
v0
(0,3)
(0,4)
(2,6) vn (0,10)
(2,5)
v3
(0,3)
增流路： v0v2vn 增流值=4
(4,5)
v1 (2,6) (0,3) (2,2) v5 (0,3) (0,4) v2
(0,10)
v0
(0,3)
(0,4)
(6,6) vn (0,10) v4 (0,5)
(2,5)
(2,5)
(0,3) v3
(4,5)
v1 (6,6) (0,3) (2,2) v5 (0,3) (0,4) v2
(4,10)
v0
(0,3)
(4,4)
(6,6) vn (4,10) v4 (0,5)
(2,5)
(0,3) v3
f =10
(4,5)
v1 (6,6) (0,3) (2,2) v5 (0,3) (0,4) v2
(0,10)
v0
(0,3)
(0,4)
(6,6) vn (0,10) v4 (0,5)
(2,5)
(0,3) v3
(4,5)
v1 (2,6) (0,3) (2,2) v5 (0,3) (0,4) v2
(0,10)
v0
(0,3)
(0,4)
(6,6) vn (0,10) v4 (0,5)
(2,5)
(0,3) v3
(4,10)
v0
(0,3)
(4,4)
(6,6) vn (4,10) v4 (3,5)
(5,5)
(0,3) v3
f =13
(4,5)
v1 (6,6) (0,3) (2,2) v5 (0,3) (0,4) v2
(4,10)
v0
(0,3)
(4,4)
(6,6) vn (4,10) v4 (3,5)
(5,5)
(4,5)
v1 (6,6) (3,3) (2,2) v5 (3,3) (0,4) v4 (3,5) v2
9-5
最大流问题
一、几个概念
定义（前向弧和后向弧）在任 意一顶点之处，凡离开vi的有 向弧称为vi的前向弧，凡进入 vi的有向弧称为vi的后向弧。
a vi vj
称有向弧a为vi点的前向弧， vj点的后向弧。
定义（道路或通路）在任意一 网络中，凡从始点v0（发点） 开始到终点vn（收点）结束的 一系列前向弧集合称为道路。 记为P。
(7,10)
v0
(0,3)
(4,4)
(6,6) vn (7,10) v4 (3,5)
(5,5)
(0,3) v3
(4,5)
v1 (6,6) (3,3) (2,2) v5 (3,3) (0,4) v2
(7,10)
v0
(0,3)
(4,4)
(6,6) vn (7,10) v4 (3,5)
(5,5)
(0,3) v3
v1 b
v0
v2
vn
截集b：v1vn，v2vn，v0vn
v1
v0
v2
vn
c
截集c：v1vn，v1v2，v2v1，v0v2 ，v0vn
d
v1
v0
v2
vn
截集d：v0v1，v1v2，v2v1，v2vn，v0vn
定义（截集的容量）从S中各 顶点到S中各顶点全部容量之 和称为截集的容量（截量）， 用（S，S）表示。
fij (vi,vj)是后向弧
其中Cij是边容量， f(i,j) 是流过边 vivj 的可行流， （ f(i,j) Cij） 定义：若 (P)=0 称P为f 的饱和的； 若 (P)>0 称P为f 的不饱和的。
定义：一条从发点到收点的 f不饱和通路称 为f 的增长道路（增流路）。
在一个网络中，f 的增长道路的存在 表示 f 不是最大流。所以。沿着P增 加一个值为 (P)的附加流，得到一个 新流：
(0,5)
v1 (0,6) (0,3) (0,2) v5 (0,3) (0,4) v2
(0,10)
v0
(0,3)
(0,4)
(0,6) vn (0,10) v4 (0,5)
(0,5)
(0,3) v3
(0,5)
v1 (0,6) (0,3) (0,2) v5 (0,3) (0,4) v2
(0,10)
v0
则称f为N的一个网络流，简称流。
定义（最大流）
若 f 为N的一个网络流，而 N中不存在流 f ，使得 f >f ， 则称 f 为一个最大流，记Max f 。
截量 C与流 f 的关系 任一有向网络流，如果 f 是从发点到收点的流量，C(S,S) 是任一个截集，则 f C(S,S) 。
等号什么时候成立？
(4,10)
v0
(0,3)
(4,4)
(6,6) vn (4,10) v4 (0,5)
(2,5)
(0,3) v3
(4,5)
v1 (6,6) (0,3) (2,2) v5 (0,3) (0,4) v4 (0,5) v2
(4,10)
v0
(0,3)
(4,4)
(6,6) vn (4,10)
(2,5)
v3
(0,3)
v1
v0
v2
vn
v1
v0
v2
vn
V0——V1——Vn
v1
v0
v2
vn
v1
v0
v2
vn
V0——V1——Vn
v1
v0
v2
vn
V0——Vn
v1
v0
Байду номын сангаас
v2
vn
v1
v0
v2
vn
v1
v0
v2
vn
V0——V1——V2——Vn
v1
v0
v2
vn
v1
v0
v2
vn
V0——V2——Vn
v1
v0
v2
vn
v1
定义（最小截量）
一个网络中，各种截集中容量 最小的称为最小截量，用min C(S,S)表示。
现在我们把一个网络看成 是一个自来水管网络，煤气管 网络，电力线网络或公路网络， 铁路网络，水运交通网络等， 都可以归纳成一个运输问题， 称为网络流，值得关心问题是 在这样一个网络中最大流为多 少？
定义（流）若对网络N，函数f满 足如下条件： （1）0 fij Cij (i,j)E(N) （2）f-(vi) = f+(vi) iV(N)
(0,10)
v0
(0,3)
(0,4)
(6,6) vn (0,10)
(2,5)
v3
(0,3)
增流路： v0v1v2v4vn
增流值=4
(4,5)
v1 (6,6) (0,3) (2,2) v5 (0,3) (0,4) v2
(4,10)
v0
(0,3)
(4,4)
(6,6) vn (4,10) v4 (0,5)
截集a: 截集c:
Ca=C01+C02+C0n Cc=C1n+C12+ C02+ C0n
截集b: Cb=C1n+C2n+C0n
截集d: Cd=C01+C21+ C2n+ C0n
S
v0
v1
v2
vn
c
S 在截集c中边v2v1是反向的，
其容量视为零。
d
v1
S
v0
v2
vn
S
在截集d中边v1v2是反向 的，其容量视为零。
(7,10)
v0
(0,3)
(4,4)
(6,6) vn (7,10) v4 (3,5)
(5,5)
(0,3) v3
f =16
(4,5)
v1 (6,6) (3,3) (2,2) v5 (3,3) (0,4) v2
(7,10)
v0
(0,3)
(4,4)
(6,6) vn (7,10) v4 (3,5)
(5,5)
定理（最小截量 最大流）
任一有向网络流，从发点到 收点的最大流量Max f 等于最 小截量Min C(S,S) 。
即： Max f = Min C(S,S)
最大流算法
设P=v0v1v2….vn为网络中的一条通路， 记E(P)=(所有P中的前向弧和后向弧) 令(P)=min (i,j) 其中
(i,j)= Cij-fij (vi,vj)是前向弧
(0,3) v3
(4,5)
v1 (6,6) (0,3) (2,2) v5 (0,3) (0,4) v2
(4,10)
v0
(0,3)
(4,4)
(6,6) vn (4,10) v4 (3,5)
(5,5)
(0,3) v3
(4,5)
v1 (6,6) (0,3) (2,2) v5 (0,3) (0,4) v2
算法：寻找增流路方法（标号法）
从v0开始，沿着边从已有标号vi出 发，对符合下列条件之一相邻顶点 vj作标记，直到vn；
1 如(vi,vj)是前向弧，条件是
f(i,j)< Cij 2 如(vi,vj)是后向弧，条件是
f(j, i) > 0
(0,5)
v1 (0,6) (0,3) (0,2) v5 (0,3) (0,4) v4 (0,5) v2
(0,3) v3
f=6
(4,5)
v1 (2,6) (0,3) (2,2) v5 (0,3) (0,4) v2
(0,10)
v0
(0,3)