最大流 标号法 PPT课件

使fij＝0的弧称为零流弧，使fij>0的弧称为非零
流弧。
若μ 是联结发点
v2 3,1
vs
1,0
5,2
4,1 1,0
v4 5,2
3,1 2,1 vt
vs和收点vt的一条链，
我们规定链的方向是
从vs到vt，则链上的
v1
2,2 v3
弧被分成两类：前向
弧、后向弧。
设f是一个可行流，μ是从vs到vt的一条链，若μ 满足前向弧都是非饱和弧,后向弧都是都是非零 流弧,则称μ是（可行流f的）一条增广链。
y2
y3
[y4,1]vs
[x2,1y4]
y5
vs
[-,+∞]
vs
[-,+∞]
x1
1
1
1 x2
[xv3 s,1] 1
x[4vs,1]
x5 [vs,1]
[x-1y1, 1] 1
1 1
x[2-y4, 1]
1
x3
1
[xv4 s,1] 1
x5
[vs,1]
y1 1
y2
y3 [x3,1]y4 1 [x3,1y]5
定义：对于二部图G=(X, Y, E)，M是边集E的一个 子集，如果M中的任意两条边没有公共端点，则称 M是图G的一个匹配（也称对集）。
M中任意一条边的端点v称为（关于M的）饱和点， G中的其他顶点称为非饱和点。
若不存在另一匹配M1使得| M1 | > | M |，则称M为最 大匹配。
下面的二部图表示了一个匹配问题
武
10
28
10 8
广
6
沈
京
18
发点vs =成都，收点vt =北京。前面已订购机票情况表中的数字即是 各边上的容量（允许通过的最大旅客量），当各边上的实际客流量为
零时略去不写，以零流作为初始可行流。
利用标号法（经5次迭代）可以得到从成都发送旅 客到北京的最大流量如图所示
0
西
6
郑
重
10 0 6
0
0
2
10 10
最大流问题
基本概念
v2 3
4
v4
5
vs
1
1
3
vt
5
2
v1
2
v3
给定一个有向图G＝(V,E)，其中仅有一个点的入次
为零称为发点（源），记为vs，仅有一个点的出次为 零称为收点（汇），记为vt，其余点称为中间点。
对于G中的每一个弧(vi,vj)，相应地给一个数cij （cij≥0），称为弧(vi,vj)的容量。我们把这样的D称 为网络（或容量网络），记为G＝(V,E,C)。
v2 (4,3) (3,3)
vs (5,1)
(1,1) (1,1)
v1 (2,2)
v4 (5,3)
(3,0) vt (2,1)
v3
在图中给出的可行 流的基础上，求vs 到vt的最大流。
(-vv21,1)(4,3)
(3,3)
(v2,1)
v4 (5,3)
(-,+∞)
vs
(5,1)
(1,1) (1,1)
(v3,1)
(3)重复步骤(2)，直到vt成为标号点或所有标号点 都检查过。若vt成为标号点，表明得到一条vs到vt的 增广链，转入调整过程；若所有标号点都检查过， 表明这时的可行流就是最大流，算法结束。
调整过程：在增广链上，前向弧流量增加l(vt)，后 向弧流量减少l(vt)。
下面用实例说明具体的操作方法：例
对最大流问题有下列定理：
定理1 容量网络中任一可行流的流量 不超过其任一割集的容量。
定理2（最大流-最小割定理）任一容 量网络中，最大流的流量等于最小割集 的割量。
推论1 可行流f*＝{fij*}是最大流，当且 仅当G中不存在关于f*的增广链。
求最大流的标号法
标号法思想是：先找一个可行流。 对于一个可行流，经过标号过程得到 从发点vs到收点vt的增广链；经过调整 过程沿增广链增加可行流的流量，得 新的可行流。重复这一过程，直到可 行流无增广链，得到最大流。
具有实际背景的例子
• 国庆大假期间旅游非常火爆，机票早已订购 一空。成都一家旅行社由于信誉好、服务好， 所策划的国庆首都游的行情看好，要求参加 的游客众多，游客甚至不惜多花机票钱辗转 取道它地也愿参加此游。旅行社只好紧急电 传他在全国各地的办事处要求协助解决此问 题。很快，各办事处将其已订购机票的情况 传到了总社。根据此资料，总社要作出计划， 最多能将多少游客从成都送往北京以及如何 取道转机。下面是各办事处已订购机票的详 细情况表：
网络的总流量。
可行流总是存在的，例如f={0}就是一个流量为0的可 行流。
所谓最大流问题就是在容量网络中寻找流量最大的可 行流。
一个流f={fij}，当fij=cij，则称f对边(vi, vj)是饱和的， 否则称f对边(vi, vj)不饱和。 最大流问题实际上是一个线性规划问题。
但利用它与图的密切关系，可以利用图直观简便地求 解。
8
12
昆
10 10
成
30
京
12 5
上 8
6
武
10
00
10
18
广
0
沈
W ( f* ) =10+6+12+30+12+10+5 = 85
多个发点多个收点的情形
对于多发点多收点的容量网络的最大流问题可 以通过添加两个新点vs与vt扩充为新的单发点与 单收点的容量网络的方式解决。
+∞ x1
vs
x2
...
xm
调整后的可行流如下图：
[vv2s, 1] (4, 3)
(4, 3)
[-, ∞] vs
(5, 2)
(1, 0) (1, 0)
v1
[vs, 3]
(2, 2)
[v2v, 41]
(5, 5)
vs [v5, 1]
(3, 2)
(2, 0)
(4, 0) v5[v3, 1] v3
[-v4, 1]
如图已经得到增广链，然后进行调整。
(3,0) vt (2,1)
v1 (2,2)
v3
(vs,4)
(-v2,1)
(3,3) v2 (4,3)
(-,+∞)
vs
(1,0) (1,0)
(5,2)
v1 (2,2)
(vs,3)
v4 (5,3)
(3,0) vt (2,2)
v3
得增广链，标号结束， 进入调整过程
无增广链，标号结束，得 最大流。同时得最小截。
标号过程: (1)给vs标号(-,+∞)，vs成为已标号未检查的点，其 余都是未标号点。
(2)取一个已标号未检查的点vi，对一切未标号点vj： 若有非饱和弧(vi,vj)，则vj标号(vi,l(vj))，其中l(vj)＝ min[l(vi),cij – fij]，vj成为已标号未检查的点；若有非 零弧(vj,vi)，则vj标号(-vi,l(vj))，其中l(vj)＝min[l(vi), fji]， vj成为已标号未检查的点。vi成为已标号已检查的点。
[-,+∞]
vs
x[v1 s,1] [xv2s,1] [xv3s,1] [xv4s,1]
x[v5 s,1]
[x1,1y1] [x1,1y]2 [x1,1]y3
y4
y5
[y1,1]vs
1
[v-,s+∞]
x1
1
x[2vs,1]
[xv3 s,1] x4 [vs,1] x5 [vs,1]
[x2,1y]1 1
所谓网络上的流，是指定义在弧集E 上的函数f＝{f(vi,vj)}，并称f(vi,vj)为弧 (vi,vj)上的流量，简记为fij。
v2 3,1
vs
1,0
5,2 v1
4,1 v4
5,2
1,0 3,1
vt
2,1
2,2 v3
标示方式：每条边上标示两个数字，第一个是容量，第二 是流量
可行流、可行流的流量、最大流。
下图中已经标示出了一个可行流，求最大流
v[2vs, 4] (4, 0)
(4, 0)
[-, ∞] vs
(1, 0) (1, 0)
[v2,v44]
(3, 2)
(5, 2)
vs [v4, 3]
(2, 0)
(5, 2)
v1
[vs, 3]
(2, 2)
v5
(4, 0)
v3
[-v4, 2]
如图已经得到增广链，然后进行调整。
成都 重庆 武汉 上海 西安 郑州 沈阳 昆明 广州
成都
重庆 10
武汉 5 5
上海 15 10 8
8
西安 8 6
2
郑州
15 6 8
沈阳
8 14 6
昆明 12 15
广州 10
北京 30 25
8 18 10 10
用图来描述就是
重
10 5
6
西
6
郑
25 1588 15 14 Nhomakorabea8
8
12
昆
10
成
30
15
上
5
10
给定容量网络G＝(V,A,E)，若点集V被剖分
为两个非空集合V1和V2，使 vs∈V1 ，vt∈V2， 则把弧集(V1,V2)称为（分离vs和vt的）割集。
v2 3
4
v4
5
vs
1
1
3
vt
5
2
v1
2
v3
显然，若把某一割集的弧从网络中去掉，