最大流问题614343.ppt

网络最大流问题
例连接某产品产地vs和销地vt的交通网如下:
v1
v4
1
1
5
v2
vs
v3
vt
3
2
5
2
2
4
弧(vi,vj):从vi到vj的运输线,
弧旁数字:这条运输线的最大通过能力,
制定一个运输方案,使从vs到vt的产品数量最多。
弧旁数字:
运输能力。
问题:这个运输网络中,从vs到vt的最大输送量是多少?
v1
v4
1
1
5
v2
vs
v3
vt
3
2
5
2
2
4
一、基本概念与定理
1. 网络流
定义1 对于网络G=(V,A,C) ,定义在弧集合
A上的一个函数f = {f(vi ,vj)} 称为网络流,
f(vi ,vj) (简称fij)为弧aij ∈A上的流。
弧旁数字:
容量
(a)图是一个网络
v2
v5
3
4
8
v3
v1
v4
v6
5
10
6
11
17
3
5
v2
v5
3
1
3
v3
v1
v4
v6
1
5
3
6
2
2
2
弧旁数字:
流量
cij fij
vi
vj
v2
v5



v3
v1
v4
v6







2. 可行流
定义2 满足下述条件的流 f 称为可行流:
1)容量限制条件: 对每一弧(vi , vj )∈A
0≤fij ≤cij
2)平衡条件: 对中间点vi (i≠s,t ),有
V( f ) 称为可行流 f 的流量,即发点的净输出量。
如所有fij=0,
零流。
可行流总是存在的
3. 最大流
若为网络可行流,且满足:
V(f *)=max{V(f )∣f }为网络D中的任意
一个可行流,则称f *为网络的最大流。
例 1 下图中,从三口油井①、②、③经管道将油输至脱水处理厂⑦和⑧,中间经④、⑤、⑥三个泵站。已知图中弧旁数字为各管道通过的最大能力(吨/小时),求从油井每小时能输送到处理厂的最大流量。
8
7
6
5
4
3
2
1
20
10
30
10
20
15
30
20
50
10
20
50
多源、多汇的最大流问题
单源、单汇。
s
20
80
15
t
60
50
例2 某产品从仓库运往市场销售。已知各仓库的可供量、各市场的需求量及从i仓库至 j仓库的路径的运输能力如下表(表中0代表无路可通),试求从仓库可运往市场的最大流量?
市场j
仓库i
1
2
3
4
可供量
A
B
C
30
0
20
10
0
10
0
10
40
40
50
5
20
20
100
需求量
20
20
60
20
多源、多汇的最大流问题。
30
10
40
10
50
A
B
C
4
3
2
1
5
10
40
10
20
s
100
20
20
t
60
20
20
20