1
图论与网络流理论
（ Graph Theory and Network Flow Theory）
讲授：高随祥
中科院研究生院专业基础课
学时/学分：60/3
本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数
理统计各专业的硕士学位研究生作为专业基础课，也可供物理学、化学、天文学、
地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、
信号等学科专业的硕士研究生选修。主要讲授图论与网络流理论的基本概念、方
法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方
法的广泛应用。为学习者将来从事有关方面的理论研究打下基础，也为进行应用
性研究提供一种有力的工具。
2
内容提要
第一章 图的基本概念
图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。
路、圈与连通图；最短路问题。
树及其基本性质；生成树；最小生成树。
第二章 图的连通性
割点、割边和块；边连通与点连通；连通度； Whitney 定理；可靠通信网络的设计。
第三章 匹配问题
匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。
第四章 欧拉图与哈密尔顿图
欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。
第五章 支配集、独立集、覆盖集与团
支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。
第六章 图的着色问题
点着色；边着色；平面图；四色猜想；色多项式；色数的应用。
第七章 网络流理论
有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费
用流问题；最小费用最大流；网络流理论的应用。
主要参考书
[1] J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中译本（吴望名等译） 。
[2] B.Bollobas, Modern graph theory (现代图论 )，科学出版社， 2001。
[3] 蒋长浩，图论与网络流，中国林业出版社， 2001。
[4] 田丰，马仲蕃，图与网络流理论，科学出版社， 1987。
[5] 徐俊明，图论及其应用，中国科技大学出版社， 1998。
[6] 王树禾，图论及其算法，中国科技大学出版社， 1994。
[7] 殷剑宏，吴开亚，图论及其算法，中国科技大学出版社， 2003。
考核方式 ：平时成绩＋期末闭卷笔试
3
第一章 图的基本概念
§ 1.1 图的基本概念
1. 图 (graph)：一集元素及它们之间的某种关系。具体地说，图是一个二元组 ),( EV ，其中
集合 V 称为 顶点集 ，集合 E 是 VV × 的一个子集（无序对，元素可重复） ，称为 边集 。
例 1.1.1 ),( EVG = ，其中
},,,,{
54321
vvvvvV = ， )},(),,(),,(),,(),,(),,(),,{(
55515153433221
vvvvvvvvvvvvvvE = 。
这便定义出一个图。
2. 图的图示
通常， 图的顶点可用平面上的一个点来表示， 边可用平面上的线段来表示 （直的或曲的） 。
这样画出的平面图形称为图的图示。
例如，例 1.1.1 中图的一个图示为
注 ： （ 1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。
比如下图是例 1.1 中图的另一个图示：
（ 2）图的图示直观易懂，因此以后一般说到一个图，我们总是画出它的一个图示来表示。
3. 一些概念和术语
（ 1） 点与边的关联 (incident)
（ 2） 点与点的相邻（ adjacent）
（ 3） 边与边的相邻
（ 4） 边的端点（ end vertices）
（ 5） 环边 (loop)
（ 6） 重边 (multiedge)
（ 7） 简单图 (simple graph)
v
5
e
1
e
2
e
3
e
4
e
5
e
6
e
7
v
1
v
2v3
v
4
v
4
e
1
e
2
e
3
e
4
e
5
e
6
e
7
v
1
v
2
v
3
v
5
4
（ 8） 完全图 (complete graph)
（ 9） 图的顶点数（图的阶） ν 、边数 ε
（ 10） 顶点 v 的度 (degree)： d(v) = 顶点 v 所关联的边的数目（环边计两次） 。
（ 11） 图 G 的最大度： )}(|)(max{)( GVvvdG
G
∈=?
图 G 的最小度： )}(|)(min{)( GVvvdG
G
∈=δ
（ 12）正则图 (regular graph)：每个顶点的度都相等的图。
（ 13） 图的补图 (complement)： 设 G 是一个图， 以 )(GV 为顶点集， 以 )}(),(|),{( GEyxyx ?
为边集的图称为 G 的补图，记为 G 。
定理 1.1.1 ε2)(
)(
=
∑
∈ GVv
vd
证明：按每个顶点的度来计数边，每条边恰数了两次。
推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0） 。
4. 子图
子图 (subgraph)：如果 )()( GVHV ? 且 )()( GEHE ? ，则称图 H 是 G 的子图，记为
GH ? 。
生成子图 (spanning subgraph): 若 H 是 G 的子图且 () ()VH VG= ，则称 H 是 G 的生成子图。
点导出子图 (induced subgraph)：设 )(GVV ?′ ，以 V′为顶点集，以两端点均在 V′中的边
的全体为边集所组成的子图，称为 G 的由顶点集 V′导出的子图，简称为 G 的点导出子图，
记为 ][VG ′ .
边导出子图 (edge-induced subgraph)：设 )(GEE ?′ ，以 E′为顶点集，以两端点均在 E′中
的边的全体为边集所组成的子图， 称为 G 的由边集 E′导出的子图， 简称为 G 的边导出子图，
记为 ][EG ′ .
5. 路和圈
途径 (walk)：图 G 中一个点边交替出现的序列
kk
iiiiii
veevevw L
2110
= 。
迹 (trail)：边不重的途径。
路 (path): 顶点不重复的迹。
（注：简单图中的路可以完全用顶点来表示，
k
iii
vvvP L
10
= ）
闭途径 （ closed walk） ：起点和终点相同的途径。
闭迹 (closed trail)：起点和终点相同的迹，也称为回路（ circuit） .
圈 (cycle): 起点和终点相同的路。
5
注：
（ 1）途径（闭途径） 、迹（闭迹） 、路（圈）上所含的边的个数称为它的 长度 。
（ 2）简单图 G 中长度为奇数和偶数的圈分别称为 奇圈 (odd cycle)和 偶圈 (even cycle)。
（ 3） 对任意 )(, GVyx ∈ ， 从 x 到 y 的具有最小长度的路称为 x 到 y 的 最短路 （ shortest path） ，
其长度称为 x 到 y 的 距离 (distance)，记为 ),( yxd
G
。
（ 4）图 G 的直径 (diameter): )}(,|),(max{ GVyxyxdD
G
∈?= .
（ 5）简单图 G 中最短圈的长度称为图 G 的 围长 (girth)，最长圈的长度称为图 G 的 周长
(circumference)。
例 1.1.2 设 G 是一个简单图，若 2)( ≥Gδ ，则 G 中必含有圈。
证明：设 G 中的最长路为
k
vvvP L
10
= 。因 2)(
0
≥vd ，故存在与
1
v 相异的顶点 v 与
0
v 相
邻。若 Pv? ，则得到比 P 更长的路，这与 P 的取法矛盾。因此必定 Pv∈ ，从而 G 中有
圈。证毕。
例 1.1.3 设 G 是简单图，若 3)( ≥Gδ ,则 G 必有偶圈。
证明：设
k
vvvP L
10
= 是 G 的最长路。
因为 3)(
0
≥vd ， 所以存在两个与
1
v 相异的顶点 vv ′′′, 与
0
v 相邻。 vv ′′′, 必都在路 P 上，
否则会得到比 P 更长的路。无妨设 )(,, jivvvv
ji
<=′′=′ 。
若 ji, 中有奇数，比如 i 是奇数，则路 P 上
0
v 到
i
v 的一段与边
i
vv
0
构成一个偶圈；
若 ji, 都是偶数，则路 P 上
i
v 到
j
v 的一段与边
i
vv
0
及
j
vv
0
构成一个偶圈。证毕。
例 1.1.4 设 G 是简单图，若 3)( ≥Gδ ,则 G 中各个圈长的最大公因数是 1 或 2。
证明：由上例知， G 中有长分别为 1,1 ++ ji 和 2+?ij 的圈。若 1,1 ++ ji ， 2+?ij 三
数有公因数 2>m ，则 )(| jim ? ，于是 2|m ，这是不可能的。因此 1,1 ++ ji ， 2+?ij
三数的公因数必不超过 2。从而各个圈长的最大公因数是 1 或 2。证毕。
6. 二部图
二部图 (bipartite graph)：若图 G 的顶点集可划分为两个非空子集 X 和 Y，使得任一条边都
有一个端点在 X 中， 另一个端点在 Y 中， 则称 G 为二部图 （或偶图） ， 记为 G＝ ),( EYX U ，
),( YX 称为 G 的一个划分。
完全二部图 (complete bipartite graph)：在二部图 ),( EYXG U= 中，若 X 的每个顶点与 Y
的每个顶点有边连接，则称 G 为完全二部图；若 mX =|| ， nY =|| ，则记此完全二部图为
nm
K
,
。
6
定理 1.1.2 一个图是二部图当且仅当它不含奇圈。
证明： 必要性 ：设
010
vvvvC
k
L= 是二部图 ),( EYXG U= 的一个圈。无妨设 Xv ∈
0
，
由二部图的定义知， Yv ∈
1
， Xv ∈
2
， L ，一般地， Xv
i
∈
2
， Yv
i
∈
+12
， （ L,1,0=i ） 。
又因 Xv ∈
0
，故 Yv
k
∈ ，因而 k 是奇数。注意到圈 C 上共有 1+k 条边，因此是偶圈。
充分性 ：设 G 不含奇圈。取 )(GVu∈ ，令
}),(|)({ oddvudGVvX ＝∈= ， }),(|)({ evenvudGVvY ＝∈= 。
任取一条边
21
vve = ，欲证
21
, vv 分属于 X 和 Y。设 P， Q 分别是 u 到
21
, vv 的最短路。
（ 1）如果
12
vvQP += 或
21
vvPQ += ，则
21
, vv 到 u 的距离奇偶性相反，
21
, vv 分属于 X
和 Y。
（ 2）否则，设 u′是 P 与 Q 的最后一个公共顶点，因 P 的 ),( uu ′ 段和 Q 的 ),( uu ′ 段都是 u
到 u′的最短路，故这两段长度相等。
假如 P， Q 的奇偶性相同，则 P 的 ),(
1
vu′ 段和 Q 的 ),(
2
vu′ 段奇偶性相同，这两段与边
e 构成一个奇圈，与定理条件矛盾。可见 P， Q 的奇偶性不同，从而
21
, vv 分属于 X 和 Y。
这便证明了 G 是一个二部图。 证毕。
7. 连通性
图中两点的连通 ：如果在图 G 中 u， v 两点有路相通，则称顶点 u， v 在图 G 中连通。
连通图 （ connected graph） ：图 G 中任二顶点都连通。
图的连通分支 （ connected branch, component） ：若图 G 的顶点集 V(G)可划分为若干非空子集
ω
VVV ,,,
21
L ，使得两顶点属于同一子集当且仅当它们在 G 中连通，则称每个子图 ][
i
VG 为
图 G 的一个连通分支（ ω,,2,1 L=i ） 。
注 ： （ 1）图 G 的连通分支是 G 的一个极大连通子图。
（ 2）图 G 连通当且仅当 1＝ω 。
例 1.1.5 设有 2n 个电话交换台，每个台与至少 n 个台有直通线路，则该交换系统中任二台均
可实现通话。
证明： 构造图 G 如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线
路。问题化为：已知图 G 有 2n 个顶点，且 nG ≥)(δ ，求证 G 连通。
事实上，假如 G 不连通，则至少有一个连通分支的顶点数不超过 n。在此连通分支中，
顶点的度至多是 1?n 。这与 nG ≥)(δ 矛盾。证毕。
例 1.1.6 若图中只有两个奇度顶点，则它们必连通。
证明： 用反证法。假如 u 与 v 不连通，则它们必分属于不同的连通分支。将每个分支看成一
个图时，其中只有一个奇度顶点。这与推论 1.1.1 矛盾。证毕。
7
8. 图的同构
由前已知，同一个图有不同形状的图示。反过来，两个不同的图也可以有形状相同的图
示。比如：
可见
1
G 和
2
G 的顶点及边之间都一一对应，且连接关系完全相同，只是顶点和边的名称
不同而已。这样的两个图称为是 同构的 (isomorphic)。
从数学上看，同构的两个图，其顶点间可建立一一对应，边之间也能建立一一对应，且
若一图的两点间有边，则在另一图中对应的两点间有对应的边。严格的数学定义如下。
定义 1.1.1 两个图 ))(),(( GEGVG = 与 ))(),(( HEHVH = ，如果存在两个一一映射：
)()(: HVGV →α ， )()(: HEGE →β ，
使得对任意 )(),( GEvue ∈= ，都有 )())(),(( HEvu ∈αα 且 =)(eβ ))(),(( vu αα ，则称图
G 与 H 同构。记为 HG ? .
9. 图的矩阵表示
（ 1）关联矩阵
=)(GM
?
?
?
?
?
?
?
?
?
?
?
?
?
?
νενν
ε
ε
ε
ν
mmm
mmm
mmm
eee
v
v
v
L
LLLL
L
L
L
M
21
22221
11211
21
2
1
，
其中
ij
m 表示顶点
i
v 与边
j
e 关联的次数。
（ 2）邻接矩阵
=)(GA
?
?
?
?
?
?
?
?
?
?
?
?
?
?
v
v
v
aaa
aaa
aaa
vvv
v
v
v
ννν
ν
ν
L
LLLL
L
L
L
M
21
22221
11211
21
2
1
，
其中
ij
a 表示顶点
i
v 与
j
v 相邻的次数。
v
1
v
2
v
3
v
4
e
1
e
3
e
2
e
4
e
5
e
6
a
4
u
1
a
1
a
2
a
3
u
2
u
3
u
4
a
6
a
5
u
1
u
2
u
3
u
4
a
1
a
3
a
2
a
4
a
5
a
6
G
1
G
2
8
例 1.1.7
?
?
?
?
?
?
?
?
?
?
?
?
?
?
=
0211000
1001100
0000111
1010011
)(GM ，
?
?
?
?
?
?
?
?
?
?
?
?
?
?
=
1101
1011
0102
1120
)(GA 。
可见： （ 1） M(G)和 A(G)的元素是 0， 1 或 2。若 G 是简单图，则只有 0 和 1；
（ 2） A(G)是对称矩阵；
（ 3） M(G)中每列之和＝ 2； M(G)中第 i 行之和＝ v
i
的度；
若 G 中无环边，则 A(G)中第 i 行（列）之和＝ M(G)中第 i 行之和＝ v
i
的度。
图在计算机上处理时，可以以关联矩阵或邻接矩阵的形式存于计算机中。因邻接矩阵比
关联矩阵小又是对称矩阵，故通常使用邻接矩阵的上三角部分。
§ 1.2 最短路问题
一、赋权图
对图 G 的每条边 e，赋以一个实数 w(e)，称为边 e 的权。每个边都赋有权的图称为赋权
图。
权在不同的问题中会有不同的含义。例如交通网络中，权可能表示运费、里程或道路的
造价等。
设 H 是赋权图 G 的一个子图， H 的权定义为 )(HW ＝
∑
∈ )(
)(
HEe
ew ，特别地，对 G 中一
条路 P， P 的权为 )(PW ＝
∑
∈ )(
)(
PEe
ew
。
二、 最短路问题
给定赋权图 G 及 G 中两点 u,v，求 u 到 v 的具有最小权的路（称为 u 到 v 的最短路） 。
注 ：赋权图中路的权也称为路的长，最短 (u,v)路的长也称为 u,v 间的距离，记为 d(u,v)。
最短路问题是一个优化问题，属于网络优化和组合优化的范畴。对这种优化问题的解答
一般是一个算法。最短路问题有很多算法，其中最基本的一个是 Dijkstra 算法。
e
1
e
2
e
3
e
4
e
5
e
6
e
7
v
1
v
2
v
4
v
3
9
三、 Dijkstra 算法
1. 算法思想
若路
kk
uuuuP
110 ?
= L 是从
0
u 到
k
u 的最短路，则
110 ?
=′
k
uuuP L 必是
0
u 到
1?k
u 的最
短路。基于这一原理，算法由近及远地逐次求出
0
u 到 其它各点 的最短路。
下面通过例子说明具体做法。
（ 1）令
00
uS = ，
00
\ SVS = ，求
0
u 到
0
S 中最近点的最短路，结果找到
1
u 。
（ 2）令 }{:
100
uSS U= ，
00
\ SVS = ，求
0
u 到
0
S 中最近点的最短路。此时除了考虑
0
u 到
0
S 的直接连边外，还要考虑
0
u 通过
1
u 向
0
S 的连边，即选取
0
S 中一点 u′使得
)},(),({min),(
0
,
0
00
vuwuuduud
SvSu
+=′
∈∈
。 (*)
结果找到
2
u 。
一般地，若 },,,{
10 kk
uuuS L= 以及相应的最短路已找到。则可应用 (*)式来选取新的
u′，获得
0
u 到 u′的最短路。
2．算法实现－标号法
标号方法：
初始时， 0:)(
0
=ul ， ∞=:)(vl ， （
0
uv ≠ ） 。然后算法逐步修改 S 中顶点的标号。
第 i 步时， )()},()(),(min{:)(
iii
Svvuwulvlvl ∈?+= 。
Dijkstra 算法：
Step1. Let 0:)(
0
=ul ， ∞=:)(vl ， （
0
uv ≠ ） ， }{:
00
uS = and 0:=i 。
Step2. for every
i
Sv∈ ， )}()(),(min{:)( vuwulvlvl
ii
+= 。 Take
i
Sv ∈
0
such that
)}({min)(
0
vlvl
i
Sv∈
= 。 Denote the vertex
0
v by
1+i
u , let }{
11 ++
=
iii
uSS U 。
Step3. if 1?=νi , then stop, else, 1: += ii , go to step 2.
3. 算法有效性
一个图论算法称为是有效算法（或好算法） ，如果在任何图上施行这个算法所需要的计
算量（时间复杂性）都可由 ν 和 ε 的一个多项式为其上界。 Dijkstra 算法是好算法。它的计
算量为 )(
2
νO 。全部迭代过程需要做
2
)1( ?νν
次加法和 )1( ?νν 次比较。
u
0
u
1 u
2
u
3
u
4
u
5
u
6
u
7
1
2
2
2
3
3
1
3
4
4
4
5
6
6
7
7
8
10
（ step2 中第 1 式需要 1??iν 次加法， 1??iν 次比较。第 2 式需要 1??iν 次比较。
而 =++?+?=??
∑
?
=
1)2()1()1(
1
0
Lννν
ν
i
i
2
)1( ?νν
） 。
§ 1.3 树及其性质
不含圈的图称为森林 ， 不含圈的连通图称为 树 （ tree） 。
定理 1.3.1 下列命题等价：
（ 1） G 是树；
（ 2） G 中无环边且任二顶点之间有且仅有一条路；
（ 3） G 中无圈且 1?=νε ；
（ 4） G 连通且 1?=νε
;
（ 5） G 连通且对任何 )(GEe∈ ， eG ? 不连通；
（ 6） G 无圈且对任何 )(GEe∈ ， eG + 恰有一个圈。
证明： （ 1） ?（ 2）
G 是树 ?G 连通 ? )(, GVvu ∈? ，存在路 ),( vuP 。
若还存在一条路 ≠′ ),( vuP ),( vuP ，则必存在 w， w 是路 P 与 P′除了 v 之外最后一个
公共顶点。 P 的 ),( vw 段与 P′的 ),( vw 段构成圈，这与 G 是树矛盾。故只存在唯一的 ),( vu
路。
（ 2） ?（ 3）
若 G 有圈，则此圈上任二顶点间有两条不同的路，与前提条件矛盾。
下面用归纳法证明 1?=νε 。
1=ν 时， 0=ε ，结论真。
假设 k≤ν 时结论真，我们来证明当 1+= kν 时，也有 1?=νε 成立。
当 1+= kν 时，任取 )(, GVvu ∈ 。考虑图 uvGG ?=′ ，因 G 中 u、 v 间只有一条路，
即边 uv，故 G′不连通且只有两个连通分支，设为
21
,GG 。注意到
21
,GG 分别都连通且任二
顶点间只有一条路，由归纳法假设， 1)()(
11
?= GG νε ， 1)()(
22
?= GG νε 。因此
1)(1)1)(()1)((1)()()(
2121
?=+?+?=++= GGGGGG νννεεε 。
归纳法完成。
（ 3） ?（ 4）
用反证法。若 G 不连通，设
w
GGG ,,,
21
L 是其连通分支（ 2≥w ） ，则 1?=
ii
νε （因
i
G 是连通无圈图，由已证明的 (1) 和 (2) 知，对每个
i
G ， （ 3 ）成立） 。这样，
ww
w
i
i
w
i
i
?=?==
∑∑
==
ννεε
11
，这与 1?=νε 矛盾。
11
（ 4） ?（ 5）
21)()( ?=?=? νεε GeG ，但每个连通图必满足 1?≥νε （见下列命题） ，故图
eG ? 不连通。
命题 若图 H 连通，则 1)()( ?≥ HH νε 。
证明：对 ν 做数学归纳法。
2,1=ν 时， 1?≥νε 显然成立。
假设 k≤ν 的连通图都 1?≥νε 。
对于 1+= kν 的连通图 H，任取 )(HVv∈ ，考虑 vH ? 。
若 vH ? 连通，则由归纳假设， 11)()( ?=??≥? kvHvH νε ，而
1)(1)1(1)1(1)()( ?=?+=+?≥+?≥ HkkvHH νεε 。
若 vH ? 不连通，设
w
HHH ,,,
21
L 是其连通分支（ 2≥w ） 。由归纳假设，
1)()( ?≥
ii
HH νε ， （ wi ,,2,1 L= ） 。故
wkwvHwHHvH
w
i
i
w
i
i
?=??=?≥=?
∑∑
==
)()()()(
11
ννεε ，
而 1)(1)1()()()( ?=?+=+?≥+?≥ HkwwkwvHH νεε 。
归纳法完成。
（ 5） ?（ 6）
先证 G 中无圈：若 G 中有圈，删去圈上任一边仍连通，矛盾。
再证 eG + 恰含一个圈：因 G 连通且已证 G 无圈，故 G 是树。由（ 2） ，任二顶点间仅
有一条路相连，故 eG + 中必有一个含有 e 的圈；另一方面，若 eG + 中有两个圈含有 e，
则 eG + Ge =? 中仍含有一个圈，矛盾。
（ 6） ?（ 1）
只需证 G 连通。任取 )(, GVvu ∈ ，若 u、 v 相邻，则 u 与 v 连通。否则， uvG + 恰含
一个圈，故 u 与 v 在 G 中连通。由 u、 v 的任意性，图 G 连通。
定理证毕。
推论 1.3.1 非平凡树至少含两个 1 度顶点（叶子） 。
证明：设 T 是一个非平凡树。因 T 连通，故对每个顶点
i
v ，都有 1)( ≥
i
vd 。若对所有
i
v 都有 2)( ≥
i
vd ，则 ν
ν
2)(
1
≥
∑
=i
i
vd 。另一方面， 22)1(22)(
1
?=?==
∑
=
ννε
ν
i
i
vd 。这
两方面矛盾。故 T 至少有一个 1 度顶点，设为 u。除此之外，其余 1?ν 个顶点的度数之和
为 32 ?ν 。若这些点的度都大于或等于 2，则其度数之和 22)1(2 ?=?≥ νν 。这与 32 ?ν
矛盾。故除 u 之外 T 还至少有一个度为 1 的顶点。证毕。
12
§ 1.4 生成树与最小生成树
一、生成树（ spanning tree）
定义 1.4.1 设 T 是图 G 的一个子图，如果 T 是一棵树，且 )()( GT νν = ，则称 T 是 G 的一
个生成树。
定理 1.4.1 每个连通图都有生成树。
证明：设 G 是一个连通图。令 GGA ′′= |{ 是 G 的连通子图且 )}()( GG νν =′ 。易见 A 非
空。从 A 中取边数最少的一个，记为 T。下证 T 是 G 的生成树。显然只需证明 T 是树即可。
事实上，已知 T 连通，下证 T 无圈。
若 T 有圈 C，则去掉 C 上任一条边 e， eT ? 仍连通。从而 AeT ?? 。但 eT ? 比 T
少一条边，这与 T 的取法矛盾。证毕。
推论 1.4.1 若 G 连通，则 1?≥νε 。
证明：取 G 的生成树 T，则 1)(1)()()( ?=?≥≥ GTTG ννεε 。证毕。
二、最小生成树问题
问题描述： 在赋权图 G 中，求权最小的生成树。即：求 G 的一棵生成树 T，使得
∑
∈
=
Te
T
ewTw )(min)( 。
算法：
1. Kruskal 算法
step1. take )(
1
GEe ∈ such that 1:)},({min)( ==
∈
iewew
Ge
.
Step2. find },,,{\)(
211 ii
eeeGEe L∈
+
such that
(1) G[{
121
,,,,
+ii
eeee L }] does not contain any cycle, and
(2)
1+i
e is the one with minimum weight that meet (1).
Step3. if i+1 = 1)( ?Gν , stop; else, 1: += ii , go to step2.
定理 1.4.2 设
1)(21
,,,
?G
eee
ν
L 是 Kruskal算法获得的边， 则边导出子图 G[{
1)(21
,,,
?G
eee
ν
L }]
是 G 的最小生成树。
证明：记 =
*
T G[{
1)(21
,,,
?G
eee
ν
L }]。显然
*
T 无圈，因此
*
T 是森林。设它有 w 个连通分
支， 则
** *
() () ()1(()1)1 ()TTwT G Gν =ε + ≥ε +=ν ? +=ν 。 但
*
T 是 G 的子图， 故 )()(
*
GT νν = ，
于是
13
1)(1)()(
**
?=?= TGT ννε 。
由定理 1.3.1 的（ 3） ，
*
T 是一棵树，从而是 G 的一棵生成树。
下证其最优性，用反证法。
假设
*
T 不是最小权生成树（下称最优树） 。
对 G 的任一棵生成树 T，记 },,,{|min{)(
121 ?
∈=
ν
eeeeiTf
i
L 且 }Te
i
? 。选取一棵
使 )(Tf 最大的最优树，记为 T
~
。 （ T
~
不会是
*
T ） 。设 kTf =)
~
( 。由 )
~
(Tf 的定义，
121
,,,
?k
eee L 既在
*
T 上也在 T
~
上，但
k
e 不在 T
~
上。因此
k
eT +
~
含有一个圈 C。 C 上必有一
条边
*
Te
k
?′ 。 显然
kk
eeTT ′?+=′ )
~
( 也是一棵生成树， 且 )()()
~
()(
kk
ewewTwTw ′?+=′ 。
按照算法，
k
e 是使 G[{
k
eee ,,,
21
L }] 中无圈的边中权最小的。注意
G[{
kk
eeee ′
?
,,,,
121
L }] 是 T
~
的子图，也无圈。故由算法规则知：
)()(
kk
ewew ≥′
。由前式，
)
~
()( TwTw ≤′
这说明
T′
也是最优树，但
)
~
()( TfkTf =>′
，这与
T
~
的取法矛盾。证毕。
例 1.4.1 欲建设一个连接 5 个城市的光纤通信网络。各城市间线路的造价如图所示，求一个
使总造价最少的线路建设方案。
2. Prim 算法
step1. 任取 )(
0
GVv ∈ ，令 }{
00
vS = ，
00
\)( SGVS = ， 0:=i 。
step2. 求
i
S 到
i
S 间权最小的边
i
e ，设
i
e 的属于
i
S 的端点为
i
v ，令 }{:
1 iii
vSS U=
+
，
11
\)(
++
=
ii
SGVS 。
Step3. 若 1?=νi ，停止；否则，令 1: += ii ，继续 step2。
14
12
11
10
8
6
5
3 8.5
6.4
v
1
v
2
v
3
v
4
v
5
14
习题一
1． 证明： ?≤≤
ν
ε
δ
2
。
2． 如果 νεν <≥ ,2 ，则连通图 G 至少有两个 1 度顶点。
3． 如果 1+=νε ，则存在 )(GVv∈ 使得 3)( ≥vd 。
4． 在 k 度正则图 G 中， )2(mod0≡νk 。
5． 晚会上大家握手言欢。证明：握过奇数次手的人必有偶数个。
6． n 个运动队进行一项竞赛。已赛完 1+n 局。试证一定存在一个队至少参加过 3 局比赛。
习题二
1． 证明：若 G 是完全二部图，则
4
2
ν
ε ≤ 。
2． 证明：若 ),( EYXG U= 是一个 k 度正则二部图，则 |||| YX = 。
3． 若 G 是简单图且 kG ≥)(δ ，则 G 有长为 k 的路。
4． 证明连通图中两条最长路必有公共顶点。
5． 设 G 是直径为 2 的简单图，且 2)( ?=? νG ，则 42 ?≥ νε 。
6． 2≥δ 的简单图必含有长至少为 1+δ 的圈。
7． 若 νε ≥ ，则 G 中必有圈。
习题三
1． 不含圈的图称为森林（ forest） ，证明：
（ 1） G 是森林当且仅当 w?=νε ； （ 2）无孤立点的森林至少有 2w 个 1 度顶点。
这里 w 表示 G 的连通分支数，孤立点指零度顶点。
2． 证明非平凡树中最长路的起点和终点都是叶子（ 1 度点） 。
3． 恰有两个叶子的树必是路。
4． 若 G 是树且 k≥? ，则 G 至少有 k 个 1 度顶点。
5． 证明每个树都是二部图。
6． 修改 Kruskal 算法用以：
（ 1）求赋权连通图中的最大权生成树； （ 2）求不连通赋权图中的最小权生成林。
15
课外阅读：
[1] 阅读参考书上有关内容。
[2] D. Jungnickel, Graphs, Networks and Algorithms, (Algorithms and Computation in
Mathematics, Vol.5), Springer, 1998, 第 3 章、第 4 章。
[3] N.Deo and N.Kumar, Computation of Constrained Spanning Trees: A Unified Approach, in
Network Optimization (P.M. Pardalos, D.W. Hearn and W.W. Hager editors.), Lecture Notes in
Economics and Mathematical Systems 450, Springer-Verlag, 1997.
[4] M.R. Henzinger and V. King, Maintaining minimum spanning forests in dynamic graphs,
SIAM J. Computing, 31:2(2001), pp364-374.
[5] Guoliang Xue and Shangzhi Sun, Optimal multicast tree in communication systems with
channel capacities and channel reliabilities, IEEE Transactions on Communications, 47:5(1999),
pp662-663.
