2009-7-26 1
运 筹 学 Operations Research
在生产生活中有许多网络，如电网、供水网、原油管道运输网、交通运输网、通讯网、国际互联网等．以供水网络为例，设仅有一个出水口和一个进水口．网络每段管道都有一个容量（单位时间内通过管道的最大水量）．水由出水口流出经过水管网络后流入进水口，这就形成一个水的实际的稳定的有向的流动，称之为 流,
显然，流具有如下性质：
（ 1）每段管道中通过的流量不超过该管道的容量；
（ 2）网络的每个内部顶点处的流入量等于与流出量；
（ 3）出水口的总流出量等于进水口的流入量．因受自身网络结构的限制，通过水管网络的流必有一个最大界限，称之为最大流．
§ 6.6 最大流问题
2009-7-26 2
运 筹 学 Operations Research
网络（ network）：
Ie r m e d ia te
Y
X
acc a p a c it yAa
YXYIXV
AVD
:)( in t
:)s in k(
:)s o u r c e(
).()(
:),(
中间点汇，收点源，发点有容量弧；＝，
有向图
单发点单收点网络,
发点,s（ 只流出 ）
收点,t（ 只流入 ）
中间点,（中转）},{\ tsVI?
2009-7-26 3
运 筹 学 Operations Research
弧的容量,)(),( acvvcc
jiij
割（ cut）,},|),{(),( SvSvAvvSS
jiji
割是从 s到 t的必经之道 （ 桥 ）,而割的容量则为桥的最大通过能力,
2009-7-26 4
运 筹 学 Operations Research
割的容量：
),(),(
),(),(
SSvv
ji
ji
vvcSSc
最小割（ minimum cut）,容量最小的割,
如
12),(
},,{),(
},,{
312
31
SSc
tvtvsvSS
vvsS
2009-7-26 5
运 筹 学 Operations Research
弧的流量 （ flux）,)(),( afvvff
jiij
流 （ flow）,f
符号：
.)()(?
Ka
afKfAK,令对
})\{,(),(
),(}){\,()(
vVvvv
j
j
vvfvVvfvf
)},\{(),(
),()},{\()(
vvVvv
j
j
vvfvvVfvf
2009-7-26 6
运 筹 学 Operations Research
})\{,(),(
),(}){\,()(
sVsvs
j
j
vsfsVsfsf
)},\{(),(
),()},{\()(
ttVtv
j
j
tvfttVftf
可行流 （ feasible flow）：
)()(0)1( acafAa,有
)()()()()2( tfsfIvtfsf,有；
流值（ flow value）,)()()( tfsffv a l
2009-7-26 7
运 筹 学 Operations Research
零流（ zero flow）,弧的流量都是 0的流,
显然，零流是一个可行流，且流值为 0.
最大流（ maximum flow）,流值最大的可行流,
最大流 问题：在网络中找一个最大流,
弧的分类：
（ 1） 按流量和容量的大小关系分：
饱和弧（ saturated arc）：
不饱和弧（ unsaturated arc）：
)()( acaf?
)()( acaf?
2009-7-26 8
运 筹 学 Operations Research
（ 2） 按流量和 0的大小关系分：
零弧 （ zero arc）：
非零弧 （ nonzero arc,positive arc）：
0)(?af
0)(?af
（ 3）按流量和有向路的关系分：
设 P是一条有向 (s,t)-路,其方向为 s→ t.
前（正）向弧（ forward arc）,与 P的方向一致的弧后（反）向弧（ forward arc）,与 P的方向相反的弧
2009-7-26 9
运 筹 学 Operations Research
可增广路 （ augmenting path）,前向弧均为不饱和弧,后向弧均为非零弧的路,
.
),(),()()2(
),()()1(
),(1
后向弧均为零弧
，中的前向弧均为饱和弧是任一割，则是任一可行流，设
SSSScfv a l
SScfv a l
SSfTh
▌
.),(),()()3(
.)2(
).,()(),()1(
为最小割为最大流，，则若最大流和最小割必存在为最小割，则为最大流，若
SSfSScfv a l
SScfv a lSSfC o r
▌
2009-7-26 10
运 筹 学 Operations Research
.
e m m a 1
fP
fPL
来改进利用的可增广路，则可是一条关于可行流设
).()()()?(?
),(,
),(),(
),(),(
:?
fv a lPlfv a lfv a lf
Pvvf
PvvPlf
PvvPlf
f
jiij
jiij
jiij
ij
仍为可行流，且则的后向弧是的前向弧是
},m i n {)(
),(),( 的后向弧是的前向弧是证：令
Pvv
ij
Pvv
ijij
jiji
ffcPl
▌
2009-7-26 11
运 筹 学 Operations Research
Th2 设 f是网络 N的一个可行流,则 f是最大流 N中不存在关于 f的可增广路,▌
Th3（ 最大流最小割定理,max-flow,min-cut theorem） 网络的任一最大流的流值等于任一最小割的容量,▌
最大流算法理论依据,Lemma 1和 Th2.
算法的关键：找可增广路,
基本思想,流程
2009-7-26 12
运 筹 学 Operations Research
2009-7-26 13
运 筹 学 Operations Research
.)()(},{, slTVSsT,令计算过程：
}),(m in {)(
}{:,),(:
),(),(
ijijij
jjji
ji
fcvlvl
vSSvvvTT
SSvv
为前向不饱和弧，则令若
2009-7-26 14
运 筹 学 Operations Research
}),(m in {)(
}{:,),(:
)(),(
ijij
jjij
ij
fvlvl
vSSvvvTT
SSvv
为后向非零弧，则令，若若 T在到达 t之前停止生长,则不存在关于 f的可增广路,f即为最大流；
若 T生长到达 t（ breakthough）,则 T中的有向 (s,t)-路即为一条可增广路；此时,t被标号,且 l(P)=l(t).修改 f.
重复上述过程,直到得到最大流,
2009-7-26 15
运 筹 学 Operations Research
生长过程应遵循,先标号者，先检查,的原则，以尽可能地减少修改次数,
2009-7-26 16
运 筹 学 Operations Research
例 1 求解最大流问题：
解：
2009-7-26 17
运 筹 学 Operations Research
2009-7-26 18
运 筹 学 Operations Research
▌
2009-7-26 19
运 筹 学 Operations Research
例 2 求网络的最大流和最小割：
解：
▌
2009-7-26 20
运 筹 学 Operations Research
2009-7-26 21
运 筹 学 Operations Research
2009-7-26 22
运 筹 学 Operations Research
2009-7-26 23
运 筹 学 Operations Research
2009-7-26 24
运 筹 学 Operations Research
2009-7-26 25
运 筹 学 Operations Research
2009-7-26 26
运 筹 学 Operations Research
§ 6.6 over
运 筹 学 Operations Research
在生产生活中有许多网络，如电网、供水网、原油管道运输网、交通运输网、通讯网、国际互联网等．以供水网络为例，设仅有一个出水口和一个进水口．网络每段管道都有一个容量（单位时间内通过管道的最大水量）．水由出水口流出经过水管网络后流入进水口，这就形成一个水的实际的稳定的有向的流动，称之为 流,
显然，流具有如下性质：
（ 1）每段管道中通过的流量不超过该管道的容量；
（ 2）网络的每个内部顶点处的流入量等于与流出量；
（ 3）出水口的总流出量等于进水口的流入量．因受自身网络结构的限制，通过水管网络的流必有一个最大界限，称之为最大流．
§ 6.6 最大流问题
2009-7-26 2
运 筹 学 Operations Research
网络（ network）：
Ie r m e d ia te
Y
X
acc a p a c it yAa
YXYIXV
AVD
:)( in t
:)s in k(
:)s o u r c e(
).()(
:),(
中间点汇，收点源，发点有容量弧；＝，
有向图
单发点单收点网络,
发点,s（ 只流出 ）
收点,t（ 只流入 ）
中间点,（中转）},{\ tsVI?
2009-7-26 3
运 筹 学 Operations Research
弧的容量,)(),( acvvcc
jiij
割（ cut）,},|),{(),( SvSvAvvSS
jiji
割是从 s到 t的必经之道 （ 桥 ）,而割的容量则为桥的最大通过能力,
2009-7-26 4
运 筹 学 Operations Research
割的容量：
),(),(
),(),(
SSvv
ji
ji
vvcSSc
最小割（ minimum cut）,容量最小的割,
如
12),(
},,{),(
},,{
312
31
SSc
tvtvsvSS
vvsS
2009-7-26 5
运 筹 学 Operations Research
弧的流量 （ flux）,)(),( afvvff
jiij
流 （ flow）,f
符号：
.)()(?
Ka
afKfAK,令对
})\{,(),(
),(}){\,()(
vVvvv
j
j
vvfvVvfvf
)},\{(),(
),()},{\()(
vvVvv
j
j
vvfvvVfvf
2009-7-26 6
运 筹 学 Operations Research
})\{,(),(
),(}){\,()(
sVsvs
j
j
vsfsVsfsf
)},\{(),(
),()},{\()(
ttVtv
j
j
tvfttVftf
可行流 （ feasible flow）：
)()(0)1( acafAa,有
)()()()()2( tfsfIvtfsf,有；
流值（ flow value）,)()()( tfsffv a l
2009-7-26 7
运 筹 学 Operations Research
零流（ zero flow）,弧的流量都是 0的流,
显然，零流是一个可行流，且流值为 0.
最大流（ maximum flow）,流值最大的可行流,
最大流 问题：在网络中找一个最大流,
弧的分类：
（ 1） 按流量和容量的大小关系分：
饱和弧（ saturated arc）：
不饱和弧（ unsaturated arc）：
)()( acaf?
)()( acaf?
2009-7-26 8
运 筹 学 Operations Research
（ 2） 按流量和 0的大小关系分：
零弧 （ zero arc）：
非零弧 （ nonzero arc,positive arc）：
0)(?af
0)(?af
（ 3）按流量和有向路的关系分：
设 P是一条有向 (s,t)-路,其方向为 s→ t.
前（正）向弧（ forward arc）,与 P的方向一致的弧后（反）向弧（ forward arc）,与 P的方向相反的弧
2009-7-26 9
运 筹 学 Operations Research
可增广路 （ augmenting path）,前向弧均为不饱和弧,后向弧均为非零弧的路,
.
),(),()()2(
),()()1(
),(1
后向弧均为零弧
，中的前向弧均为饱和弧是任一割，则是任一可行流，设
SSSScfv a l
SScfv a l
SSfTh
▌
.),(),()()3(
.)2(
).,()(),()1(
为最小割为最大流，，则若最大流和最小割必存在为最小割，则为最大流，若
SSfSScfv a l
SScfv a lSSfC o r
▌
2009-7-26 10
运 筹 学 Operations Research
.
e m m a 1
fP
fPL
来改进利用的可增广路，则可是一条关于可行流设
).()()()?(?
),(,
),(),(
),(),(
:?
fv a lPlfv a lfv a lf
Pvvf
PvvPlf
PvvPlf
f
jiij
jiij
jiij
ij
仍为可行流，且则的后向弧是的前向弧是
},m i n {)(
),(),( 的后向弧是的前向弧是证：令
Pvv
ij
Pvv
ijij
jiji
ffcPl
▌
2009-7-26 11
运 筹 学 Operations Research
Th2 设 f是网络 N的一个可行流,则 f是最大流 N中不存在关于 f的可增广路,▌
Th3（ 最大流最小割定理,max-flow,min-cut theorem） 网络的任一最大流的流值等于任一最小割的容量,▌
最大流算法理论依据,Lemma 1和 Th2.
算法的关键：找可增广路,
基本思想,流程
2009-7-26 12
运 筹 学 Operations Research
2009-7-26 13
运 筹 学 Operations Research
.)()(},{, slTVSsT,令计算过程：
}),(m in {)(
}{:,),(:
),(),(
ijijij
jjji
ji
fcvlvl
vSSvvvTT
SSvv
为前向不饱和弧，则令若
2009-7-26 14
运 筹 学 Operations Research
}),(m in {)(
}{:,),(:
)(),(
ijij
jjij
ij
fvlvl
vSSvvvTT
SSvv
为后向非零弧，则令，若若 T在到达 t之前停止生长,则不存在关于 f的可增广路,f即为最大流；
若 T生长到达 t（ breakthough）,则 T中的有向 (s,t)-路即为一条可增广路；此时,t被标号,且 l(P)=l(t).修改 f.
重复上述过程,直到得到最大流,
2009-7-26 15
运 筹 学 Operations Research
生长过程应遵循,先标号者，先检查,的原则，以尽可能地减少修改次数,
2009-7-26 16
运 筹 学 Operations Research
例 1 求解最大流问题：
解：
2009-7-26 17
运 筹 学 Operations Research
2009-7-26 18
运 筹 学 Operations Research
▌
2009-7-26 19
运 筹 学 Operations Research
例 2 求网络的最大流和最小割：
解：
▌
2009-7-26 20
运 筹 学 Operations Research
2009-7-26 21
运 筹 学 Operations Research
2009-7-26 22
运 筹 学 Operations Research
2009-7-26 23
运 筹 学 Operations Research
2009-7-26 24
运 筹 学 Operations Research
2009-7-26 25
运 筹 学 Operations Research
2009-7-26 26
运 筹 学 Operations Research
§ 6.6 over
