§ 1．图的基本概念与模型
§ 2．树图和图的最小部分树
§ 3．最短路问题
§ 4．网络的最大流
§ 5．最小费用流
第六章 图与网络分析
§ 1．图的基本概念与模型
一个 图 （ graph） 是由一些 结点或顶点 （ nodes or
vertices ） 以及连接点的 边 （ edges） 构成。记做 G = {V,E}，
其中 V 是顶点的集合,E 是边的集合。
给图中的点和边赋以具体的含义和权值，我们称这样
的图为 网络图 （赋权图）
图中的点用 v 表示，边用 e 表示，对每条边可用它所
联结的点表示，如图，则有,
e1 = [v1,v1],
e2 = [v1,v2]或 e2= [v2,v1]
端点，关联边，相邻
若边 e 可表示为 e = [vi,vj],称 vi 和 vj 是边 e 的 端点,
同时称边 e 为点 vi 和 vj 的 关联边,若点 vi,vj 与同一条
边关联，称点 vi 和 vj 相邻 ；若边 ei 与 ej 有公共端点，称
边 ei 和 ej 相邻 ；
环，多重边，简单图
如果边 e 的两个端点相重，称该
边为 环,如果两个点之间的边多于
一条，称为具有 多重边,对无环、
无多重边的图称为 简单图 。
次，奇点，偶点，孤立点
与某个点相关联的边的数目，称为该点的 次 （或 度、
线度 ），记作 d(v)。 次为奇数的点称为 奇点,次为偶数
的点称为 偶点,次为零的点称为 孤立点 。
如图,
奇点为 v5, v3
偶点为 v1,v2,v4,v6
孤立点为 v6
链，圈，路，回路，连通图
图中有些点和边的交替序列 μ={v0,e1,v1,e2,…,ek,
vk},若其各边 e1,e2,…,ek 各不相同，且任意 vi,t-1,vit (2
≤ t ≤ k)都相邻，称 μ 为 链,如果链中所有的顶点 v0,v1,
…,vk也不相同，这样的链成为 路,起点和终点重合的
链称为 圈,起点和终点重合的路称为 回路,若在一个图
中，每一对顶点之间至少存在一条链，称这样的图为 连
通图,否则称该图为不连通的。
完全图，偶图
一个简单图中若任意两点之间均有边相连，称这样的
图为完全图，含有 n 个顶点的 完全图,其边数有
1/2[n(n-1)] 条。
如果图的顶点能分成两个互不相交的非空集合 V1 和
V2,使在同一集合中任意两个顶点均不相邻，称这样的图
为 偶图 （也称 二分图 ），如果偶图的顶点集合 V1 和 V2 之
间的每一对顶点都有一条边相连，称这样的图为完全偶图，
完全偶图中 V1 含 m 个顶点,V2 含有 n 个顶点，则其边数
共 m · n 条。
子图，部分图
图 G1={V1,E1} 和 G2={V2,E2},如果有 和
,称 G1 是 G2 的一个 子图,若有
则称 G1 是 G2 的一个 部分图 。注意部分图也是子图，但
子图不一定是部分图。
21 VV ?
21 EE ? 2121,EEVV ??
子图,部分图
§ 2．树图和最小部分树
树图 （简称 树,记作 T(V,E)） 是简单连通图。（无
圈，无重边）
一, 树的性质
性质 1,任何树中必存在次为 1 的点。
次为 1的点称为 悬挂点,与之关联的边称为 悬挂边 。
性质 2,具有 n 个顶点的树恰有（ n-1） 条边。
性质 3,任何具有 n 个点,(n - 1)条边连通图是树。
说明,
1,树中只要任意再加一条边，必出现圈。
2,树中任意两点之间有且只有一条通路，从树中任
意删掉一条边，就不再连通。
二, 图的最小部分树
如果 G1 是 G2 的部分图，又是树图，则称 G1 是 G2 的
部分树 （或 支撑树 ）。树图的各条边称为树枝 (假定各边
均有权重 )，一般图 G2 含有多个部分树，其中树枝总长
最小的部分树，称为该图的 最小部分树 (也称 最小支撑
树 )。
定理 1,图中任一个点 i, 若 j 是与 i 相邻点中距离最
近的，则边 [ i,j ] 一定包含在该图的最小部分树中。
推论, 把图的所有点分成 V 和 两个集合，则两集
合之间连线的最短边一定包含在最小部分树内。
V
三, 避圈法和破圈法
寻找最小部分树的方法主要有避圈法和破圈法两种。
避圈法步骤,
1,从图中任选一点 vi, 让 vi ∈ V, 图中其余点均包
含在 中； V
2,从 V 与 的连线中找出最小边，这条边一定包含
在最小部分树中，不妨设这条边为 [vi,vj]将其加粗，标记
为最小部分树中的边。
V
3,令 V∪ vj→ V,- vj→ ； V V
4,重复 2,3两步，一直到图中所有点均包含在 V 中。
避圈法另一种做法,
1,在所有各边中找到边权最小的一条，将其作为最
小部分树中的第一边；在剩余的边中，仍然找到边权最小
的作为最小部分树的第二条边；
2,在剩余的边中，找到边权最小的边，查看其是否
与前面的边形成圈，如果没有，则在最小部分树中添加该
边，如果形成了圈，则不再考虑该边；
3,重复进行第二步，直到找到第 n-1 条边为止。
（因为有 n 个顶点的树中一定有 n-1 条边）
例：分别用两种避圈法构造下图的最小部分树。
第一种解法,
1,在点集中任选一点，不妨取 S,令 V={S}
2,找到和 S 相邻的边中，权值最小的 [S,A] 。
3,V={S,A}
4,重复第 2,3步，找到下一个点。
第二种做法求解过程,
破圈法求解步骤,
1,从图 N 中任取一回路，去掉这个回路中边权最大
的边，得到原图的一个子图 N1。
2,从剩余的子图中任找一回路，同样去掉回路中边
权最大的一条边，得一新的子图；
3,重复第 2 步，直到图中不再含有回路为止。
用破圈法求解上例,
1,任意找到一回路，不妨取 DETD,去掉边权最大
的边 [T,E];
2,从剩余的子图中任找一回路，同样去掉回路中边
权最大的一条边，得一新的子图；依次类推。
破圈法的另一种解法,
1,从剩余图中找到边权最大的一条边，如果将其删
除后图仍然是连通的，则删除此边，否则不再考虑此边；
2,重复上述步骤，直到剩余边数为 n-1 为止。
用此法求解上述问题,
注意,
1,一个图的最小部分树不唯一，该题中用几种解法
得到的结果都是相同的，是特殊情况；
2,不同解法得到的最小部分树所包含的边虽然可能
不相同，但是，每个最小部分树中所有边权的总和一定都
是相同的，即都达到了最小。
§ 3．最短路问题
最短路问题 是指从给定的网络图中找出任意两点
之间距离最短（权值和最小）的一条路。
某些整数规划和动态规划问题可以归结为求最短路的
问题。
如选址问题、管道铺设选线问题、设备更新、投资等
问题。
最短路的求法,
1,从某一点至其它各点之间最短距离的狄克斯屈拉
( Dijksrta )算法 ;
2,求网络图中任意两点之间的最短距离的矩阵算法。
一, Dijkstra 算法
1,设 dij 表示图中两相邻点 i 与 j 的距离，若 i 与 j 不
相邻，令 dij =∞，显然 dii =0。
Dijkstra 算法假设,
基本思路,如果 v1→ v2→ v3→ v4 是 v1→ v4 的最短路
径，则 v1→ v2→ v3 一定是 v1→ v3 的最短路径。 v2→ v3→
v4 一定是 v2→ v4 的最短路径。
2,设 Lsi 表示从 s 点到 i 点的最短距离。
Dijkstra 算法步骤,
1,对起始点 s,因 Lss =0,将 0 标注在 s 旁的小方框
内，表示 s 点已标号；
2,从点 s 出发，找出与 s 相邻的点中距离最小的一个，
设为 r, 将 Lsr = Lss+ dsr 的值标注在 r 旁的小方框内，表
明点 r 也已标号；
3,从已标号的点出发，找出与这些点相邻的所有未
标号点 p, 若有 Lsp =min { Lss+ dsp,Lsr+ drp }，则对 p 点
标号，并将 Lsp 的值标注在 p 点旁的小方框内；
4,重复第 3 步，直到 t 点得到标号为止。
求从起始点 s 到终止点 t 的最短路径。
例, 求下图中从 v1 到 v7 的最短路。
解,(1) 从 v1 点出发，对 v1 点标号，将 L11=0 标注在
旁的小方框内，令 v1∈ V,其余点属于 ； V
L1r = min { 0+d12,0+ d13 }
=min{5,2}=2= L13
(2) 同 v1 相邻的未标号点有 v2, v3,
对 v3 标号，将 L13 的值标
注在 v3 旁的小方框内； 将 ( v1,v3) 加粗，并令 V∪ v3 → V,
VvV ?? 3 。
L1p = min { L11+d12,L13+d34,
L13+d36 }
=min{0+5,2+7,2+4}=5= L12
对 v2 标号，将 L12 的值标
注在 v2 旁的小方框内； 将 ( v1,v2) 加粗，并令 V∪ v2 → V,
VvV ?? 2 。
(3) 同 v1,v3 相邻的未标号点有 v2, v4, v6,
L1p = min { L12+d25,L12+d24,
L13+d34,L13+d36 }
=min{5+7,5+2,2+7,2+4}
=6= L16
对 v6 标号，将 L16 的值标注在 v6 旁的小方框内；将
( v3,v6) 加粗，并令 V∪ v6 → V,VvV ??
6
。
(4) 同 v1,v2,v3 相邻的未标号点有 v4, v5,v6,
L1p = min { L12+d25,L12+d24,
L13+d34,L16+d64,
L16+d65,L16+d67 }
=min{5+7,5+2,2+7,6+2,6+1,6+6}
=7= L14 = L15
对 v4,v5 同时标号，将 L14 = L15 的值标注在 v4,v5 旁
的小方框内；将 ( v2,v4),( v6,v5) 加粗，并令 V∪ v4∪ v5→ V,
? ? VvvV ?? 54,。
(5) 同 v1,v2,v3,v6 相邻的未标号点有 v4, v5,v7,
L1p = min { L15+d57,L16+d67 }
=min{7+3,6+6}=10= L17
对 v7 标号，将 L17 的值标注在 v7 旁的小方框内；将
( v5,v7) 加粗。图中粗线表明从点 v1 到网络中其它各点的
最短路，各点旁的数字就是点 v1 到各点的最短距离。
(6) 同 v1,v2,v3,v4,v5,v6 相邻的未标号点只有 v7,
二, 求任意两点间最短距离的矩阵算法
用 Dijkstra 算法只能计算从图中某一点到其他点的最
短距离，如果要计算各点之间的最短距离就需要对每个点
分别计算，而用矩阵算法则可以同时求出所有各点间的最
短距离。
例, 利用矩阵算法求上述网络图中各点间的最短距离。
解, 设 dij 表示图中两相邻点 i 与 j 的距离，若 i 与 j
不相邻，令 dij =∞，显然 dii =0。建立距离矩阵,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
??
??
??
???
???
????
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
063
60124
31067
26072
4702
7205
250
77767574737271
67666564636261
57565554535251
47464544434241
37363534333231
27262524232221
17161514131211
ddddddd
ddddddd
ddddddd
ddddddd
ddddddd
ddddddd
ddddddd
从上述距离矩阵可以看出从 i 点到 j 点的直接距离，
但从 i 到 j 的最段距离不一定就是从 i 点直接到 j 点。
如上述问题中，从 v1→ v2 的最短距离应该是,
min{d11+d12,d12+d22,d13+d32,d14+d42,
d15+d52,d16+d62,d17+d72 }
即 min{d1r+dr2}。
因此可以构造一个新的矩阵 D(1), 令 D(1) 中每一个元
素为,dij(1) =min{dir+drj}, 则矩阵 D(1) 给出了网络中任意
两点之间直接到达及经由一个中间点时的最短距离。
再构造矩阵 D(2), dij(2) =min{dir (1) +drj (1)} 。
依次类推构造矩阵 D(k), dij(k) =min{dir (k -1) +drj (k -1)} 。
计算停止的控制,p是图中顶点数。
kpk ???? 2lg )1lg (1
该例中 k = 3 。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
04381010
4012446
31035712
8230627
10456072
10472705
6127250
)1(
D
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
04368810
4012446
3103557
6230627
8456072
8452705
10677250
)2(
D
)2()3( DD ?
上述 D(2) 中的元素给出了各点间的最短距离，但是并
没有给出具体是经过了哪些中间点才得到的这个最短距离，
如果要知道中间点具体是什么，需要在计算过程中进行记
录。
教材 160页例 5
§ 4．网络的最大流
一, 网络最大流的有关概念
1,有向图与容量网络
对图中每条边规定指向的图称为 有向图,有向图的
边称为 弧,记作 (vi,vj),表示方向从点 vi 指向点 vj,有向
图是点与弧的集合，记作 D(V,A)。
弧 (vi,vj)的最大通过能力，称为该 弧的容量,记为
c(vi,vj),或简记为 cij 。
定义了弧容量的网络称为 容量网络 。
容量网络通常规定一个 发点 (源点，记为 s)一个 收点
(汇点，记为 t),网络中其余的点称为 中间点 。
从发点到收点之间允许通过的最大流量称为 最大流 。
多个收 (发 )点的网络可以转换为只含一个收 (发 )点。
2,流与可行流
流 是指加在网络各条弧上的一组负载量，对加在弧
(vi,vj)上的负载量记作 f (vi,vj), 或简记作 fij, 若网络上
所有的 fij =0，这个流称为 零流 。
称网络上满足下述条件 (1),(2)的流为 可行流,
(1) 容量限制条件, 对所有弧有
0≤f (vi,vj) ≤c (vi,vj)
(2) 中间点平衡条件,
∑f (vi,vj) - ∑ (vj,vi) =0 (i≠s,t)
以 v( f )表示网络中从 s→ t 的 流量,则
?? ??
j
tj
j
js vvfvvffv ),(),()(
零流是可行流，求最大流就是求 v( f )的最大值。
二, 割和流量
割 是指将容量网络中的发点和收点分割开，并使 s→ t
的流中断的一组弧的集合。
上图中 KK 将网络上的点分割成 V 和 两个集合,
并有 s∈ V,t ∈, 称弧的集合 (V,)={(v1,v3),(v2,v4)}
是一个割 。 注意, 这里不包含 (v3,v2) 。
弧旁数字为 cij ( fij )
所有不同的割见教材
162页
V
V V
割的容量 是组成它的集合中各弧容量之和，用
c(V,)表示,V
?
?
?
),(),(
),(),(
VVji
ji vvcVVc
用 f (V,) 表示通过割 (V,) 中所有 V→ 方向弧
的流量的总和,f (,V) 表示通过割 中所有 → V方向
弧的流量的总和，则有,
V V V
V V
??
??
??
),(),(),(),(
),(),(,),(),(
VVij
ij
VVji
ji vvfVVfvvfVVf
从 s→ t 的流量 等于通过割的从 V→ 的流量减去 → V
的流量，有,
VV
),(),()( VVfVVffv ??
用 v*( f ) 表示网络中从 s→ t 的最大流，则有
),(),()( *** VVfVVffv ??
最大流 v*( f ) 应小于最小割的容量 (用 c*(V,)表示 ) V
),(),(),()( **** VVcVVfVVffv ???
因此，上例中对大流不会超过 14 。
三, 最大流最小割定理
如果在网络的发点和收点之间能找到一条链，在这条
链上所有指向为 s→ t 的弧（称 前向弧,记作 μ+）,存在 f
< c (非饱和 )；所有指向为 t → s 的弧（称 后向弧,记为 μ -
），存在 f > 0(非零 )，这样的链称 增广链 。
当有增广链存在时，找出
? ?
0
,
,
m i n ?
??
?
?
? ?
?
?
?
?
?
?
?
对
对
i
ii
f
fc
再令
?
?
?
?
?
?
?
?? ?
?
对非增广链上的弧
对所有
对所有
,
,
,
i
i
i
f
f
f
f ??
??
显然，经过计算后 f ’ 仍然为可行流，但较原来的可
行流 f 流量增大了 θ 。 因此，只有当网络图中找不到增广
链时,s→ t 流才不可能进一步增大。
定理 2,在网络中 s→ t 的最大流量等于它的最小割集
的容量，即
? ? ? ?VVcfv,** ?
证明,略（教材 163页）
三, 求网络最大流的标号算法
Ford-Fulkerson 标号算法,其本质是判断是否存在增
广链，并找出增广链。
第一步：首先给发点 s 标号 (0,ε(s))。
第一个数字是使这个点得到标号的前一个点的代号，
因 s 是发点，因此记为 0。
第二个数字 ε(s) 表示从上一个标号到这个标号点的流
量的最大允许调整值,s 为发点，不允许调整容量，故
ε(s)=∞。
第二步：列出与已标号点相邻的所有未标号点,
1,考虑从标号点 i 出发的弧 (i,j),如果有 fij=cij,不
给点 j 标号；若 fij<cij, 则对 j 标号，记为 (i,ε( j )),其中
ε( j ) = min{ε( i ),(cij,fij)}
2,考虑所有指向标号点 i 的弧 (h,i),如果有 fhi=0，
对 h 不标号,若 fhi>0,则对 h 点标号，记为 (i,ε( h ))，
其中 ε( h ) = min{ε( i ),fhi)},
3,如果某未标号点 k 有两个以上相邻的标号点，可
按 (1),(2) 中所述规则分别计算出 ε( k )的值，并取其中的
最大的一个标记。
第三步：重复第二步可能出现如下两种结果,
1,标号过程中断,t 得不到标号，说明该网络中不存
在增广链，给定流量即为最大流量。记已标号点集为 V，
未标号点集为, (V,) 为网络的最小割。 V V
2,t 得到标号，这时可用反向追踪法在网络中找到一
条从 s→ t 的有标号点以及相应的弧连接而成的增长链。
第四步：修改流量。
设原图中可行流为 f, 令
?
?
?
?
?
?
?
??
所有非增广链上的弧
对增广链上所有后向弧
对增广链上所有前向弧
,
,)(
,)(
f
tf
tf
f ?
?
这样得到网络上的一个新的可行流 f ’ 。
第五步：抹掉图上所有标号，重复第一到第四步。
注意,在求解步骤中，第三步起到控制运算停止的
作用，而不是第五步。
例,用标号法求下述网络图 s → t 的最大流量，并找
出该网络图的最小割。
解,(1) 先给 s 点标号 (0,∞)；
(2) 从 s 点出发的弧 (s,v2),因有 fs2<cs2, 且
ε(v2)=min{ε(s),(cs2- fs2)}=2
故对 v2 点标号 (s,2)。 (s,v1)饱和，不标号。
(3) 弧 (v1,v2),因有 f12>0, 且
ε(v1)=min{ε(v2),f12)}=2
故对 v1 点标号 (v2,2)。 (v2,v4)饱和，不标号。
(4) 弧 (v1,v3),因有 f13<c13, 且
ε(v3)=min{ε(v1),(c13- f13)}=2
故对 v3 点标号 (v1,2)。
(5) 弧 (v4,v3),因有 f43>0, 且
ε(v4)=min{ε(v3),f43)}=1
故对 v4 点标号 (v3,1)。 (v3,t)饱和，不标号,v2 已标号。
(6) 弧 (v4,t),因有 f4t<c4t, 且
ε(t)=min{ε(v4),(c4t - f4t)}=1
故对 t 点标号 (v4,1)。
(7) 由于收点 t 得到标号，用反追踪法找出网络图上
的一条增广链。
(8) 修改增广链上各弧的流量,
918)(
011)(
514)(
314)(
615)(
44
4343
1313
1212
22
??????
??????
??????
??????
??????
tff
tff
tff
tff
tff
tt
ss
?
?
?
?
?
非增广链上的所有弧流量不变，这样得到网络图上的
一个新的可行流。
重复上述标号过程，由于对点 s, v1, v2, v3 标号后，
标号中断，故图中的可行流即为最大流,v*( f )=14
已标号点集为 V={s,v1,v2,v3 },未标号点集为,
(V,) ={(3,t),(2,4)}为网络的最小割。
V
V
三, 应用举例
见教材
§ 5．最小费用流
在产销平衡问题中，研究的是使费用最小的物资调运
方案；最大流问题中考虑了联结两个点之间的弧的容量限
制，但是没考虑流量通过各条弧时发生的费用。
实际物资调运中，既要考虑弧的容量又要考虑调运费
用的节省，这就是最小费用流要研究的问题。
在最小费用流问题中，将单位流量通过弧的费用当成
距离，则从发点至收点的最小费用也就等价于求最短距离
问题。这样最短路问题变成了最小费用流问题的特例。
求最小费用流时，一方面通过增广链来调整流量，另
一方面要找出每一步费用最小的增广链。是最大流和最短
路问题的综合求解。
例,如图，图中弧旁数字 (cij,bij)中,cij 表示弧容量,
bij 表示单位费用，求从 s → t 的最小费用的最大流。
解,1,先不考虑弧容量，构造最短路,
该图中路径旁数字
为单位费用。
2,根据各弧容量，将路径上的流量调整到最大可能,
3,构建新的网络图,
(1) 对于非饱和且非零的弧 (i,j), 在两点间分别给出
弧 (i,j) 和 ( j,i),其权值分别为 bij 和 - bij；
(2) 对于饱和弧 (i,j), 只画出弧 ( j,i), 其权值为 - bij；
(3) 对于零弧 (i,j), 只给出弧 (i,j),其权值为 bij 。
4,重复第 1 步，构造最短路 (即费用最小增广链 ),
5,重复第 2 步，在原流量不减少的前提下调整流量；
6,重复第 3 步，重新构造网络图，原则与第 3 步相
同,
7,重复第 4 步，构造最短路,
8,重复第 5 步，在原流量不减少的前提下调整流量；
9,重复第 6 步，重新构造网络图，原则与第 3 步相
同,
10,重复第 7 步，构造最短路,
11,重复第 8 步；
12,重复第 9 步，重新构造网络图,
13,由于无法再找到最短
路，因此计算停止，第 11
步所得流量即为最小费用
的最大流。
§ 2．树图和图的最小部分树
§ 3．最短路问题
§ 4．网络的最大流
§ 5．最小费用流
第六章 图与网络分析
§ 1．图的基本概念与模型
一个 图 （ graph） 是由一些 结点或顶点 （ nodes or
vertices ） 以及连接点的 边 （ edges） 构成。记做 G = {V,E}，
其中 V 是顶点的集合,E 是边的集合。
给图中的点和边赋以具体的含义和权值，我们称这样
的图为 网络图 （赋权图）
图中的点用 v 表示，边用 e 表示，对每条边可用它所
联结的点表示，如图，则有,
e1 = [v1,v1],
e2 = [v1,v2]或 e2= [v2,v1]
端点，关联边，相邻
若边 e 可表示为 e = [vi,vj],称 vi 和 vj 是边 e 的 端点,
同时称边 e 为点 vi 和 vj 的 关联边,若点 vi,vj 与同一条
边关联，称点 vi 和 vj 相邻 ；若边 ei 与 ej 有公共端点，称
边 ei 和 ej 相邻 ；
环，多重边，简单图
如果边 e 的两个端点相重，称该
边为 环,如果两个点之间的边多于
一条，称为具有 多重边,对无环、
无多重边的图称为 简单图 。
次，奇点，偶点，孤立点
与某个点相关联的边的数目，称为该点的 次 （或 度、
线度 ），记作 d(v)。 次为奇数的点称为 奇点,次为偶数
的点称为 偶点,次为零的点称为 孤立点 。
如图,
奇点为 v5, v3
偶点为 v1,v2,v4,v6
孤立点为 v6
链，圈，路，回路，连通图
图中有些点和边的交替序列 μ={v0,e1,v1,e2,…,ek,
vk},若其各边 e1,e2,…,ek 各不相同，且任意 vi,t-1,vit (2
≤ t ≤ k)都相邻，称 μ 为 链,如果链中所有的顶点 v0,v1,
…,vk也不相同，这样的链成为 路,起点和终点重合的
链称为 圈,起点和终点重合的路称为 回路,若在一个图
中，每一对顶点之间至少存在一条链，称这样的图为 连
通图,否则称该图为不连通的。
完全图，偶图
一个简单图中若任意两点之间均有边相连，称这样的
图为完全图，含有 n 个顶点的 完全图,其边数有
1/2[n(n-1)] 条。
如果图的顶点能分成两个互不相交的非空集合 V1 和
V2,使在同一集合中任意两个顶点均不相邻，称这样的图
为 偶图 （也称 二分图 ），如果偶图的顶点集合 V1 和 V2 之
间的每一对顶点都有一条边相连，称这样的图为完全偶图，
完全偶图中 V1 含 m 个顶点,V2 含有 n 个顶点，则其边数
共 m · n 条。
子图，部分图
图 G1={V1,E1} 和 G2={V2,E2},如果有 和
,称 G1 是 G2 的一个 子图,若有
则称 G1 是 G2 的一个 部分图 。注意部分图也是子图，但
子图不一定是部分图。
21 VV ?
21 EE ? 2121,EEVV ??
子图,部分图
§ 2．树图和最小部分树
树图 （简称 树,记作 T(V,E)） 是简单连通图。（无
圈，无重边）
一, 树的性质
性质 1,任何树中必存在次为 1 的点。
次为 1的点称为 悬挂点,与之关联的边称为 悬挂边 。
性质 2,具有 n 个顶点的树恰有（ n-1） 条边。
性质 3,任何具有 n 个点,(n - 1)条边连通图是树。
说明,
1,树中只要任意再加一条边，必出现圈。
2,树中任意两点之间有且只有一条通路，从树中任
意删掉一条边，就不再连通。
二, 图的最小部分树
如果 G1 是 G2 的部分图，又是树图，则称 G1 是 G2 的
部分树 （或 支撑树 ）。树图的各条边称为树枝 (假定各边
均有权重 )，一般图 G2 含有多个部分树，其中树枝总长
最小的部分树，称为该图的 最小部分树 (也称 最小支撑
树 )。
定理 1,图中任一个点 i, 若 j 是与 i 相邻点中距离最
近的，则边 [ i,j ] 一定包含在该图的最小部分树中。
推论, 把图的所有点分成 V 和 两个集合，则两集
合之间连线的最短边一定包含在最小部分树内。
V
三, 避圈法和破圈法
寻找最小部分树的方法主要有避圈法和破圈法两种。
避圈法步骤,
1,从图中任选一点 vi, 让 vi ∈ V, 图中其余点均包
含在 中； V
2,从 V 与 的连线中找出最小边，这条边一定包含
在最小部分树中，不妨设这条边为 [vi,vj]将其加粗，标记
为最小部分树中的边。
V
3,令 V∪ vj→ V,- vj→ ； V V
4,重复 2,3两步，一直到图中所有点均包含在 V 中。
避圈法另一种做法,
1,在所有各边中找到边权最小的一条，将其作为最
小部分树中的第一边；在剩余的边中，仍然找到边权最小
的作为最小部分树的第二条边；
2,在剩余的边中，找到边权最小的边，查看其是否
与前面的边形成圈，如果没有，则在最小部分树中添加该
边，如果形成了圈，则不再考虑该边；
3,重复进行第二步，直到找到第 n-1 条边为止。
（因为有 n 个顶点的树中一定有 n-1 条边）
例：分别用两种避圈法构造下图的最小部分树。
第一种解法,
1,在点集中任选一点，不妨取 S,令 V={S}
2,找到和 S 相邻的边中，权值最小的 [S,A] 。
3,V={S,A}
4,重复第 2,3步，找到下一个点。
第二种做法求解过程,
破圈法求解步骤,
1,从图 N 中任取一回路，去掉这个回路中边权最大
的边，得到原图的一个子图 N1。
2,从剩余的子图中任找一回路，同样去掉回路中边
权最大的一条边，得一新的子图；
3,重复第 2 步，直到图中不再含有回路为止。
用破圈法求解上例,
1,任意找到一回路，不妨取 DETD,去掉边权最大
的边 [T,E];
2,从剩余的子图中任找一回路，同样去掉回路中边
权最大的一条边，得一新的子图；依次类推。
破圈法的另一种解法,
1,从剩余图中找到边权最大的一条边，如果将其删
除后图仍然是连通的，则删除此边，否则不再考虑此边；
2,重复上述步骤，直到剩余边数为 n-1 为止。
用此法求解上述问题,
注意,
1,一个图的最小部分树不唯一，该题中用几种解法
得到的结果都是相同的，是特殊情况；
2,不同解法得到的最小部分树所包含的边虽然可能
不相同，但是，每个最小部分树中所有边权的总和一定都
是相同的，即都达到了最小。
§ 3．最短路问题
最短路问题 是指从给定的网络图中找出任意两点
之间距离最短（权值和最小）的一条路。
某些整数规划和动态规划问题可以归结为求最短路的
问题。
如选址问题、管道铺设选线问题、设备更新、投资等
问题。
最短路的求法,
1,从某一点至其它各点之间最短距离的狄克斯屈拉
( Dijksrta )算法 ;
2,求网络图中任意两点之间的最短距离的矩阵算法。
一, Dijkstra 算法
1,设 dij 表示图中两相邻点 i 与 j 的距离，若 i 与 j 不
相邻，令 dij =∞，显然 dii =0。
Dijkstra 算法假设,
基本思路,如果 v1→ v2→ v3→ v4 是 v1→ v4 的最短路
径，则 v1→ v2→ v3 一定是 v1→ v3 的最短路径。 v2→ v3→
v4 一定是 v2→ v4 的最短路径。
2,设 Lsi 表示从 s 点到 i 点的最短距离。
Dijkstra 算法步骤,
1,对起始点 s,因 Lss =0,将 0 标注在 s 旁的小方框
内，表示 s 点已标号；
2,从点 s 出发，找出与 s 相邻的点中距离最小的一个，
设为 r, 将 Lsr = Lss+ dsr 的值标注在 r 旁的小方框内，表
明点 r 也已标号；
3,从已标号的点出发，找出与这些点相邻的所有未
标号点 p, 若有 Lsp =min { Lss+ dsp,Lsr+ drp }，则对 p 点
标号，并将 Lsp 的值标注在 p 点旁的小方框内；
4,重复第 3 步，直到 t 点得到标号为止。
求从起始点 s 到终止点 t 的最短路径。
例, 求下图中从 v1 到 v7 的最短路。
解,(1) 从 v1 点出发，对 v1 点标号，将 L11=0 标注在
旁的小方框内，令 v1∈ V,其余点属于 ； V
L1r = min { 0+d12,0+ d13 }
=min{5,2}=2= L13
(2) 同 v1 相邻的未标号点有 v2, v3,
对 v3 标号，将 L13 的值标
注在 v3 旁的小方框内； 将 ( v1,v3) 加粗，并令 V∪ v3 → V,
VvV ?? 3 。
L1p = min { L11+d12,L13+d34,
L13+d36 }
=min{0+5,2+7,2+4}=5= L12
对 v2 标号，将 L12 的值标
注在 v2 旁的小方框内； 将 ( v1,v2) 加粗，并令 V∪ v2 → V,
VvV ?? 2 。
(3) 同 v1,v3 相邻的未标号点有 v2, v4, v6,
L1p = min { L12+d25,L12+d24,
L13+d34,L13+d36 }
=min{5+7,5+2,2+7,2+4}
=6= L16
对 v6 标号，将 L16 的值标注在 v6 旁的小方框内；将
( v3,v6) 加粗，并令 V∪ v6 → V,VvV ??
6
。
(4) 同 v1,v2,v3 相邻的未标号点有 v4, v5,v6,
L1p = min { L12+d25,L12+d24,
L13+d34,L16+d64,
L16+d65,L16+d67 }
=min{5+7,5+2,2+7,6+2,6+1,6+6}
=7= L14 = L15
对 v4,v5 同时标号，将 L14 = L15 的值标注在 v4,v5 旁
的小方框内；将 ( v2,v4),( v6,v5) 加粗，并令 V∪ v4∪ v5→ V,
? ? VvvV ?? 54,。
(5) 同 v1,v2,v3,v6 相邻的未标号点有 v4, v5,v7,
L1p = min { L15+d57,L16+d67 }
=min{7+3,6+6}=10= L17
对 v7 标号，将 L17 的值标注在 v7 旁的小方框内；将
( v5,v7) 加粗。图中粗线表明从点 v1 到网络中其它各点的
最短路，各点旁的数字就是点 v1 到各点的最短距离。
(6) 同 v1,v2,v3,v4,v5,v6 相邻的未标号点只有 v7,
二, 求任意两点间最短距离的矩阵算法
用 Dijkstra 算法只能计算从图中某一点到其他点的最
短距离，如果要计算各点之间的最短距离就需要对每个点
分别计算，而用矩阵算法则可以同时求出所有各点间的最
短距离。
例, 利用矩阵算法求上述网络图中各点间的最短距离。
解, 设 dij 表示图中两相邻点 i 与 j 的距离，若 i 与 j
不相邻，令 dij =∞，显然 dii =0。建立距离矩阵,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
??
??
??
???
???
????
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
063
60124
31067
26072
4702
7205
250
77767574737271
67666564636261
57565554535251
47464544434241
37363534333231
27262524232221
17161514131211
ddddddd
ddddddd
ddddddd
ddddddd
ddddddd
ddddddd
ddddddd
从上述距离矩阵可以看出从 i 点到 j 点的直接距离，
但从 i 到 j 的最段距离不一定就是从 i 点直接到 j 点。
如上述问题中，从 v1→ v2 的最短距离应该是,
min{d11+d12,d12+d22,d13+d32,d14+d42,
d15+d52,d16+d62,d17+d72 }
即 min{d1r+dr2}。
因此可以构造一个新的矩阵 D(1), 令 D(1) 中每一个元
素为,dij(1) =min{dir+drj}, 则矩阵 D(1) 给出了网络中任意
两点之间直接到达及经由一个中间点时的最短距离。
再构造矩阵 D(2), dij(2) =min{dir (1) +drj (1)} 。
依次类推构造矩阵 D(k), dij(k) =min{dir (k -1) +drj (k -1)} 。
计算停止的控制,p是图中顶点数。
kpk ???? 2lg )1lg (1
该例中 k = 3 。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
04381010
4012446
31035712
8230627
10456072
10472705
6127250
)1(
D
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
04368810
4012446
3103557
6230627
8456072
8452705
10677250
)2(
D
)2()3( DD ?
上述 D(2) 中的元素给出了各点间的最短距离，但是并
没有给出具体是经过了哪些中间点才得到的这个最短距离，
如果要知道中间点具体是什么，需要在计算过程中进行记
录。
教材 160页例 5
§ 4．网络的最大流
一, 网络最大流的有关概念
1,有向图与容量网络
对图中每条边规定指向的图称为 有向图,有向图的
边称为 弧,记作 (vi,vj),表示方向从点 vi 指向点 vj,有向
图是点与弧的集合，记作 D(V,A)。
弧 (vi,vj)的最大通过能力，称为该 弧的容量,记为
c(vi,vj),或简记为 cij 。
定义了弧容量的网络称为 容量网络 。
容量网络通常规定一个 发点 (源点，记为 s)一个 收点
(汇点，记为 t),网络中其余的点称为 中间点 。
从发点到收点之间允许通过的最大流量称为 最大流 。
多个收 (发 )点的网络可以转换为只含一个收 (发 )点。
2,流与可行流
流 是指加在网络各条弧上的一组负载量，对加在弧
(vi,vj)上的负载量记作 f (vi,vj), 或简记作 fij, 若网络上
所有的 fij =0，这个流称为 零流 。
称网络上满足下述条件 (1),(2)的流为 可行流,
(1) 容量限制条件, 对所有弧有
0≤f (vi,vj) ≤c (vi,vj)
(2) 中间点平衡条件,
∑f (vi,vj) - ∑ (vj,vi) =0 (i≠s,t)
以 v( f )表示网络中从 s→ t 的 流量,则
?? ??
j
tj
j
js vvfvvffv ),(),()(
零流是可行流，求最大流就是求 v( f )的最大值。
二, 割和流量
割 是指将容量网络中的发点和收点分割开，并使 s→ t
的流中断的一组弧的集合。
上图中 KK 将网络上的点分割成 V 和 两个集合,
并有 s∈ V,t ∈, 称弧的集合 (V,)={(v1,v3),(v2,v4)}
是一个割 。 注意, 这里不包含 (v3,v2) 。
弧旁数字为 cij ( fij )
所有不同的割见教材
162页
V
V V
割的容量 是组成它的集合中各弧容量之和，用
c(V,)表示,V
?
?
?
),(),(
),(),(
VVji
ji vvcVVc
用 f (V,) 表示通过割 (V,) 中所有 V→ 方向弧
的流量的总和,f (,V) 表示通过割 中所有 → V方向
弧的流量的总和，则有,
V V V
V V
??
??
??
),(),(),(),(
),(),(,),(),(
VVij
ij
VVji
ji vvfVVfvvfVVf
从 s→ t 的流量 等于通过割的从 V→ 的流量减去 → V
的流量，有,
VV
),(),()( VVfVVffv ??
用 v*( f ) 表示网络中从 s→ t 的最大流，则有
),(),()( *** VVfVVffv ??
最大流 v*( f ) 应小于最小割的容量 (用 c*(V,)表示 ) V
),(),(),()( **** VVcVVfVVffv ???
因此，上例中对大流不会超过 14 。
三, 最大流最小割定理
如果在网络的发点和收点之间能找到一条链，在这条
链上所有指向为 s→ t 的弧（称 前向弧,记作 μ+）,存在 f
< c (非饱和 )；所有指向为 t → s 的弧（称 后向弧,记为 μ -
），存在 f > 0(非零 )，这样的链称 增广链 。
当有增广链存在时，找出
? ?
0
,
,
m i n ?
??
?
?
? ?
?
?
?
?
?
?
?
对
对
i
ii
f
fc
再令
?
?
?
?
?
?
?
?? ?
?
对非增广链上的弧
对所有
对所有
,
,
,
i
i
i
f
f
f
f ??
??
显然，经过计算后 f ’ 仍然为可行流，但较原来的可
行流 f 流量增大了 θ 。 因此，只有当网络图中找不到增广
链时,s→ t 流才不可能进一步增大。
定理 2,在网络中 s→ t 的最大流量等于它的最小割集
的容量，即
? ? ? ?VVcfv,** ?
证明,略（教材 163页）
三, 求网络最大流的标号算法
Ford-Fulkerson 标号算法,其本质是判断是否存在增
广链，并找出增广链。
第一步：首先给发点 s 标号 (0,ε(s))。
第一个数字是使这个点得到标号的前一个点的代号，
因 s 是发点，因此记为 0。
第二个数字 ε(s) 表示从上一个标号到这个标号点的流
量的最大允许调整值,s 为发点，不允许调整容量，故
ε(s)=∞。
第二步：列出与已标号点相邻的所有未标号点,
1,考虑从标号点 i 出发的弧 (i,j),如果有 fij=cij,不
给点 j 标号；若 fij<cij, 则对 j 标号，记为 (i,ε( j )),其中
ε( j ) = min{ε( i ),(cij,fij)}
2,考虑所有指向标号点 i 的弧 (h,i),如果有 fhi=0，
对 h 不标号,若 fhi>0,则对 h 点标号，记为 (i,ε( h ))，
其中 ε( h ) = min{ε( i ),fhi)},
3,如果某未标号点 k 有两个以上相邻的标号点，可
按 (1),(2) 中所述规则分别计算出 ε( k )的值，并取其中的
最大的一个标记。
第三步：重复第二步可能出现如下两种结果,
1,标号过程中断,t 得不到标号，说明该网络中不存
在增广链，给定流量即为最大流量。记已标号点集为 V，
未标号点集为, (V,) 为网络的最小割。 V V
2,t 得到标号，这时可用反向追踪法在网络中找到一
条从 s→ t 的有标号点以及相应的弧连接而成的增长链。
第四步：修改流量。
设原图中可行流为 f, 令
?
?
?
?
?
?
?
??
所有非增广链上的弧
对增广链上所有后向弧
对增广链上所有前向弧
,
,)(
,)(
f
tf
tf
f ?
?
这样得到网络上的一个新的可行流 f ’ 。
第五步：抹掉图上所有标号，重复第一到第四步。
注意,在求解步骤中，第三步起到控制运算停止的
作用，而不是第五步。
例,用标号法求下述网络图 s → t 的最大流量，并找
出该网络图的最小割。
解,(1) 先给 s 点标号 (0,∞)；
(2) 从 s 点出发的弧 (s,v2),因有 fs2<cs2, 且
ε(v2)=min{ε(s),(cs2- fs2)}=2
故对 v2 点标号 (s,2)。 (s,v1)饱和，不标号。
(3) 弧 (v1,v2),因有 f12>0, 且
ε(v1)=min{ε(v2),f12)}=2
故对 v1 点标号 (v2,2)。 (v2,v4)饱和，不标号。
(4) 弧 (v1,v3),因有 f13<c13, 且
ε(v3)=min{ε(v1),(c13- f13)}=2
故对 v3 点标号 (v1,2)。
(5) 弧 (v4,v3),因有 f43>0, 且
ε(v4)=min{ε(v3),f43)}=1
故对 v4 点标号 (v3,1)。 (v3,t)饱和，不标号,v2 已标号。
(6) 弧 (v4,t),因有 f4t<c4t, 且
ε(t)=min{ε(v4),(c4t - f4t)}=1
故对 t 点标号 (v4,1)。
(7) 由于收点 t 得到标号，用反追踪法找出网络图上
的一条增广链。
(8) 修改增广链上各弧的流量,
918)(
011)(
514)(
314)(
615)(
44
4343
1313
1212
22
??????
??????
??????
??????
??????
tff
tff
tff
tff
tff
tt
ss
?
?
?
?
?
非增广链上的所有弧流量不变，这样得到网络图上的
一个新的可行流。
重复上述标号过程，由于对点 s, v1, v2, v3 标号后，
标号中断，故图中的可行流即为最大流,v*( f )=14
已标号点集为 V={s,v1,v2,v3 },未标号点集为,
(V,) ={(3,t),(2,4)}为网络的最小割。
V
V
三, 应用举例
见教材
§ 5．最小费用流
在产销平衡问题中，研究的是使费用最小的物资调运
方案；最大流问题中考虑了联结两个点之间的弧的容量限
制，但是没考虑流量通过各条弧时发生的费用。
实际物资调运中，既要考虑弧的容量又要考虑调运费
用的节省，这就是最小费用流要研究的问题。
在最小费用流问题中，将单位流量通过弧的费用当成
距离，则从发点至收点的最小费用也就等价于求最短距离
问题。这样最短路问题变成了最小费用流问题的特例。
求最小费用流时，一方面通过增广链来调整流量，另
一方面要找出每一步费用最小的增广链。是最大流和最短
路问题的综合求解。
例,如图，图中弧旁数字 (cij,bij)中,cij 表示弧容量,
bij 表示单位费用，求从 s → t 的最小费用的最大流。
解,1,先不考虑弧容量，构造最短路,
该图中路径旁数字
为单位费用。
2,根据各弧容量，将路径上的流量调整到最大可能,
3,构建新的网络图,
(1) 对于非饱和且非零的弧 (i,j), 在两点间分别给出
弧 (i,j) 和 ( j,i),其权值分别为 bij 和 - bij；
(2) 对于饱和弧 (i,j), 只画出弧 ( j,i), 其权值为 - bij；
(3) 对于零弧 (i,j), 只给出弧 (i,j),其权值为 bij 。
4,重复第 1 步，构造最短路 (即费用最小增广链 ),
5,重复第 2 步，在原流量不减少的前提下调整流量；
6,重复第 3 步，重新构造网络图，原则与第 3 步相
同,
7,重复第 4 步，构造最短路,
8,重复第 5 步，在原流量不减少的前提下调整流量；
9,重复第 6 步，重新构造网络图，原则与第 3 步相
同,
10,重复第 7 步，构造最短路,
11,重复第 8 步；
12,重复第 9 步，重新构造网络图,
13,由于无法再找到最短
路，因此计算停止，第 11
步所得流量即为最小费用
的最大流。
