前向弧集：与同向 后向弧集：与反向，
第11页
•可增广链
非饱和弧 f 是可行流，
f1 c1 f2 c2
非0流弧
8(8) v1 vfs3 05(4)
9(4) 2(0)
7(5)
v2 fn1 0
9(9)
若
0 0
fij fij
cij cij
每一个(vi , v j ) 每一个(vi , v 3
v2
（v1，v2）是不饱和的 间隙为12=c12-f12=5-3=2 第9页
弧关于流的分类
设f { fij}是网络D=（V，A，C）的一个可行流
3、如果fij=0，该弧是0流弧；
v1
cij=5 fij=0
v2
（v1，v2）是0流弧
4、如果fij>0，该弧是非0弧；
v1
cij=5 fij>0
则称为关于可行流f 的从vs到vt的可增广链。
v3 5(5)
6(1) vt
fn cn
v4 10(8)
ij
cij
fij
fij
(vi , v j ) (vi , v j )
min{ij} 0
f
'
fij fij
fij
v( f ') v( f )
(vi , v j ) (vi , v j )
的A中弧的集合记为 (V1 ,V1 )
则称这个弧的集合是分离点vs与点vt的割集（又称截集）。
割集的容量是割集中各弧的容量之和，用 c(V1,表V1示) 。
V1 {s, v1, v2},V1 {v3, v4, vt} V18(8)
K 9(4)
v1
v3 5(5)V1
割集 {(v1, v3), (v2 , v4 )}
9(4)
8(8) v1
v3 5(5)
2(0)
vs 5(4)
6(1) vt
7(5)
v2
v4 10(8)
9(9)
网络最大流问题
在容量网络中，寻求一个流 fij 使其流量v( f )最大
且满足 0 fij cij
(vt , vj ) A
v( f )
fi j
f ji
0
v( f )
(i s) (i s,t) (i t)
v2
（v1，v2）是非0弧
第10页
链及可增广链
9(4)
8(8) v1
v3 5(5)
•链
2(0)
vs 5(4)
6(1) vt
在的最方大 法流中问，题则中要，使研用究无的向是网有络向中7(5网的) 络链图。v。2 但是在求最v4大流10(8)
9(9)
D中，若为从vs到vt的一条链，给定向为从vs到vt ,
9
v1
5
2
v3 5
6
vt
容量 发点（源）
7
v2
v4 10
c D的每条弧(vi , v j )上有9 非负数 ij
一个入次为0的点 vs
收点（汇） 一个出次为0的点 vt
中间点
其余点
容量网络 D (V , A,C) 第6页
流
对D中任一弧(vi , v j )都给定一个实际流量fij
集合f { fij }
第八章 图与网络分析
• 图的基本概念与模型 • 树图和图的最小部分树 • 最短路问题 • 网络最大流问题 • 最小费用最大流问题
第1页
第八章 图与网络分析
• 图的基本概念与模型 • 树图和图的最小部分树 • 最短路问题 • 网络最大流问题 • 最小费用最大流问题
第2页
网络最大流问题
如同我们可以把一个实际的道路地图抽象成一个有向 图来计算两点之间的最短路径，我们也可以将一个有向图 看作一个流网络来解决另一类型的问题。
非增广链上的弧
割集的意义：若把某一割集的弧从网络中丢去，则 从vs到vt便割不集存和路割，集即的割容集量是从vs到vt的必经之道！ 这里设(v有3,v网2)络不D=属{V于，此A，割C}集，点vs与点vt的是集合V中的任意
两点，若点集V被剖分成两个非空集合V1和V1( V \，V1使) vs V1 ,vt V1，记以 V1 中的点为始点，V1 中的点为终点
分析：就输油管网络问题，可用顶点表示油井、油 库和中间泵站，用有向边表示输油管，用有向边上 的权表示单位时间沿相应的输油管可以输送石油的 最大数量（容量）。
第4页
管道网络中每边的最大通过能力即容量是有限的，实际流
量也不一问定等题于的容提量，出上述问题就是要讨论如何充分利用
装置的能力，以取得最好效果（流量最大），这类问题通
2(0)
vs 5(4)
6(1) vt
割集的容量为 9+9=18
7(5)
v2 K
v4 10(8)
9(9)
第13页
考虑KK的不同画法
9(4)
8(8) v1
v3 5(5)
2(0)
vs 5(4)
6(1) vt
由合于C(有V1,限V1)网是络有的限割的集实只数有集有合7限(5，)多令个v，C2 0则 m截9(i9n)集{C容(Vv量14,V的1)1}0集(8)
常称为如最果大我流们问把题图。看做输油管道网，v为t 起点， v为s 终点，
为中v转1, v站2,，v3,边v4上的数表示该管道的最
大输油能力，问应该如何安排各管道输油量，才能
使从 v到s 的vt总输油量最大？
9
8
v1
2
vs 5
v3 5
6
vt
7
v2
v4 10
9
第5页
网络上流的基本概念
8
网络有向图D=（V，A，C） vs
此为一个特殊的线性规划问题，将会看到利用图的特点， 解决这个问题的方法要比单纯形法较为直观方便。
第8页
弧关于流的分类
设f { fij}是网络D=（V，A，C）的一个可行流
1、如果fij=cij，该弧是饱和弧；
v1
cij=5 fij=5
v2
（v1，v2）是饱和的
2、如果0≤fij<cij，该弧是非饱和弧；
流网络比较适合用来模拟液体流经管道、电流在电路 网络中的运动、信息网络中信息的传递等等类似的过程。
50年代福特（Ford）、富克逊（Fulkerson）建立 的“网络流理论”，是网络应用的重要组成部分。
第3页
问题的提出
在一个输油管网中，有生产石油的油井、储存石油的油库、 转运石油的中间泵站，同时，还有各种口径不同的输油管。 当一个输油管网给定后，单位时间内最多可把多少石油从油 井输送到油库？具体方案如何？
运输问题中，每个运
可行流 满足下面条件的流：
输方案就是一个流
(1)容量限制条件
0 fij cij
(2)中间点平衡条件 fki fij
k
j
用v( f )表示网络中从s 中t间的流 点量的输v(入f ) 量 输fsj 出 量f jt
j
j
任何网络必存在可行流，如流量为0的可行流：f {0}