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 是 V 中元素组成的某些无序对的集合，称为 边集 。
例 1.1.1 ),( EVG =,其中
},,,,{
54321
vvvvvV =,)},(),,(),,(),,(),,(),,(),,{(
55515153433221
vvvvvvvvvvvvvvE = 。
这便定义出一个图。
图的顶点集中的元素称为顶点，边集中的元素称为边。在本书中边 e = (u,v) 也常写为
e = uv，顶点 u 和 v 称为边 e 的端点，反过来也称边 e 连接顶点 u 和 v。图 G 的顶点数目 ||V
称为图 G 的阶，边的数目 ||E 称为图 G 的边数。本书中一般将图的边数记为 ε,将图的阶记为 υ。
2,图的图示
通常,图的顶点可用平面上的一个点来表示,边可用平面上的线段来表示 （直的或曲的） 。
这样画出的平面图形称为图的图示。
例如，例 1.1.1 中图的一个图示为
注,（ 1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。
比如下图是例 1.1.1 中图的另一个图示,
（ 2）图的图示直观易懂，因此以后一般说到一个图，我们总是画出它的一个图示来表示。
3,一些术语和概念
设 G = (V,E)是一个图，下述概念中顶点均取自 V，边均取自 E。
（ 1） 点与边的关联 (incident)：如果在图 G 中点 v 是边 e 的一个端点，则称点 v 与边 e 在图 G 中相关联。
（ 2） 点与点的相邻 (adjacent)：如果图上两点 u,v 被同一条边相连，则称 u,v 在图 G 中相
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
邻。
（ 3） 边与边的相邻,如果图 G 中两条边有至少一个公共端点，则称这两条边在图 G 中相邻。
（ 4） 环边 (loop)：图中两端点重合的边称为环边。
（ 5） 重边 (multiedge)：设 u 和 v 是图 G 的顶点，图 G 中连接 u 和 v 的两条或两条以上的边称为图 G 中 u,v 间的重边。
（ 6） 简单图 (simple graph)：既无环边也无重边的图称为简单图。
（ 7） 完全图 (complete graph)：任意两点间都有一条边的简单图称为完全图,n 阶完全图记为 K
n
,
（ 8） 平凡图(trivial graph),只有一个顶点，没有边的图。
（ 9） 空图 (empty graph),边集为空的图。
（ 10） 零图 (null graph),顶点集为空的图。
（ 11） 顶点 v 的度 (degree)：图 G 中顶点 v 所关联的边的数目（环边计两次）称为顶点 v 的度，记为 d
G
(v)或 d(v)。
（ 12） 图 G 的最大度,)}(|)(max{)( GVvvdG
G
∈=Δ ；
图 G 的最小度,)}(|)(min{)( GVvvdG
G
∈=δ 。
（ 13） 正则图 (regular graph)：每个顶点的度都相等的图。
（ 14） 图的补图 (complement),设 G 是一个图,以 )(GV 为顶点集,以 )}(),(|),{( GEyxyx?
为边集的图称为 G 的补图，记为 G 。
定理 1.1.1 对任何图 G，都有
()
() 2
vVG
dv ε
∈
=
∑
。
证明,按每个顶点的度来计数边，每条边恰数了两次。
推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0） 。
证明留作练习。
4,子图
子图 (subgraph)：对图 G 和 H，如果 )()( GVHV? 且 )()( GEHE?,则称图 H 是图 G 的子图，记为 GH? 。
生成子图 (spanning subgraph),若 H 是 G 的子图且 () ()VH VG=,则称 H 是 G 的生成子图。
点导出子图 (induced subgraph)：设 G 是一个图,)(GVV?′ 。以 V′为顶点集，以 G 中两端点均属于 V′的所有边作为边集所组成的子图，称为 G 的由顶点集 V′导出的子图，简称为 G
的点导出子图，记为 ][VG ′,
边导出子图 (edge-induced subgraph)：设 G 是一个图,)(GEE?′ 。以 E′为边集，以 E′中边的所有端点作为顶点集所组成的子图，称为 G 的由边集 E′导出的子图，简称为 G 的边导出子图，记为 ][EG ′ 。
5
设 )(GVV?′,)(GEE?′,今后经常用 G V′? 表示从图 G 中删除顶点子集 V′（连同它们关联的边一起删去）所获得的子图，用 G E′? 表示从图 G 中删除边子集 E′（但不删除它们的端点） 所获得的子图。 特别地,对顶点 v 和边 e,常用 G v? 表示 G{}v?,G e?
表示 {}Ge? 图 G 的一个顶点子集 E′。
5,路和圈
途径 (walk)：图 G 中一个点边交替出现的序列
kk
iiiiii
veevevw null
2110
= 称为图 G 的一条途径，
其中
0
i
v,
k
i
v 分别称为途径 w 的起点和终点,w 上其余顶点称为中途点。
迹 (trail)：图 G 中边不重复的途径称为迹。
路 (path)：图 G 中顶点不重复的迹称为路。
（注：简单图中的路可以完全用顶点来表示，
k
iii
vvvP null
10
= ）
闭途径( closed walk)：图 G 中起点和终点相同的途径称为闭途径。
闭迹 (closed trail)：图 G 中边不重复的闭途径称为闭迹，也称为回路（ circuit） 。
圈 (cycle)：中途点不重复的闭迹称为圈。
注,
（ 1）途径（闭途径）,迹（闭迹）,路（圈）上所含的边的数目称为它的 长度 。
（ 2）简单图 G 中长度为奇数和偶数的圈分别称为 奇圈 (odd cycle)和 偶圈 (even cycle)。
（ 3） 对任意 )(,GVyx ∈,从 x 到 y 的具有最小长度的路称为 x 到 y 的 最短路 （ shortest path）,
其长度称为 x 到 y 的 距离 (distance)，记为 ),( yxd
G
。
（ 4）简单图 G 中最短圈的长度称为图 G 的 围长 (girth)，最长圈的长度称为图 G 的 周长
(circumference)。
例 1.1.2 设 G 是一个简单图，若 2)( ≥Gδ,则 G 中必含有圈。
证明：设 G 中的最长路为
k
vvvP null
10
= 。因 2)(
0
≥vd,故存在与
1
v 相异的顶点 v 与
0
v 相邻。若 Pv?,则得到比 P 更长的路，这与 P 的取法矛盾。因此必定 Pv∈,从而 G 中有圈。证毕。
例 1.1.3 设 G 是简单图，若 3)( ≥Gδ,则 G 必有偶圈。
证明：设
k
vvvP null
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。
6
证明：由上例知,G 中有长分别为 1,1 ++ ji 和 2+?ij 的圈。若 1,1 ++ ji,2+?ij 三数有公因数 2>m,则 |( )mji?,于是 2|m,这是不可能的。因此 1,1 ++ ji,2+?ij
三数的公因数必不超过 2。从而各个圈长的最大公因数是 1 或 2。证毕。
6,二部图
二部图 (bipartite graph)：若图 G 的顶点集可划分为两个非空子集 X 和 Y，使得 G 的任一条边都有一个端点在 X 中，另一个端点在 Y 中，则称 G 为二部图（或偶图）,记为 G＝
),( EYX ∪,),( YX 称为 G 的一个顶点二划分。
完全二部图 (complete bipartite graph)：在二部图 ),( EYXG ∪= 中，若 X 的每个顶点与 Y
的每个顶点有边连接，则称 G 为完全二部图；若 mX =||,nY =||,则记此完全二部图为
nm
K
,
。
定理 1.1.2 一个图是二部图当且仅当它不含奇圈。
证明,必要性,设
010
vvvvC
k
null= 是二部图 ),( EYXG ∪= 的一个圈。无妨设 Xv ∈
0
，
由二部图的定义知,Yv ∈
1
,Xv ∈
2
,null,一般地,Xv
i
∈
2
,Yv
i
∈
+12
,（ null,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 是一个二部图。 证毕。
例 1.1.5 判断下列图是不是二部图。
Herschel 图 Peterson图
解,Herschel 图的一个顶点二划分如下,
7
可见 Herschel 图是一个二部图。
Peterson 图中含有奇圈，因此不是二部图。
7,连通性
图中两点的连通,如果在图 G 中 u,v 两点间有路相通，则称顶点 u,v 在图 G 中连通。
连通图 （ connected graph）,若图 G 中任二顶点都连通，则称图 G 是连通图。
图的连通分支 （ connected branch,component）,若图 G 的顶点集 V(G)可划分为若干非空子集
ω
VVV,,,
21
null,使得两顶点属于同一子集当且仅当它们在 G 中连通，则称每个子图 ][
i
VG 为图 G 的一个连通分支（ ω,,2,1 null=i ） 。
注,（ 1）图 G 的连通分支是 G 的一个极大连通子图。
（ 2）图 G 连通当且仅当 1＝ω 。
例 1.1.6 设有 2n 个电话交换台，每个台与至少 n 个台有直通线路，则该交换系统中任二台均可实现通话。
证明,构造图 G 如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线路。问题化为：已知图 G 有 2n 个顶点，且 nG ≥)(δ,求证 G 连通。
事实上，假如 G 不连通，则至少有一个连通分支的顶点数不超过 n。在此连通分支中，
顶点的度至多是 1?n 。这与 nG ≥)(δ 矛盾。证毕。
例 1.1.7 若图中只有两个奇度顶点，则它们必连通。
证明,用反证法。假如 u 与 v 不连通，则它们必分属于不同的连通分支。将每个分支看成一个图时，其中只有一个奇度顶点。这与推论 1.1.1 矛盾。证毕。
8,图的同构
我们已经知道，同一个图可以有不同形状的图示。反过来，两个不同的图也可以有形状相同的图示。比如,
易见
1
G 和
2
G 的顶点及边之间都一一对应，且连接关系完全相同，只是顶点和边的名称不同而已。这样的两个图称为是 同构的 (isomorphic)。
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
x
y y
y y
x
x
x
x
yy
8
从数学上看，同构的两个图，其顶点间可建立一一对应，边之间也能建立一一对应，且若一图的两点间有边，则在另一图中对应的两点间有对应的边。严格的数学定义如下。
定义 1.1.1 对两个图 ))(),(( GEGVG = 与 ))(),(( HEHVH =,如果存在两个一一映射,
)()(,HVGV →α,)()(,HEGE →β,
使得对任意 )(),( GEvue ∈=,都有 )())(),(( HEvu ∈αα 且 =)(eβ ))(),(( vu αα,则称图
G 与 H 同构，记为 HG? 。
图的同构关系是一种等价关系（即满足反身性、对称性、传递性）,这种等价关系将 υ阶图分成若干等价类，彼此同构的图属于同一类。同一个等价类中的图有相同的结构，差别仅在于顶点和边的名称不同。由于人们关心的是图的结构，因此，通常将同构图类中的所有图看成同一个图，而不在乎它们顶点和边的名称以及它们的图示画法。在图的图示中，不给顶点和边标定名称的图称为非标定图，否则称为标定图。非标定图实际上就是一个同构图类的代表。在不致误解的情况下，我们也往往不严格区分标定图与非标定图。
目前尚无简便的方法判别两个图是否同构，特别是当图的顶点数较大时，判断两个图是否同构是一件很困难的事情。
两图同构，首先它们的阶必须相等，边数必须相等；其次要有相同的环边、重边及圈的状态；还应保持顶点的度，即在同构映射下相对应的顶点必须有相同的度。这些都是两图同构的必要条件，可用来判断两图不同构。
为判定两图同构，一般要按定义构造出两图顶点间的一一映射，然后检验它是否保持邻接关系。有时也可根据图的特点使用特殊方法。
例 1.1.8 判断下列图是否同构
解,图 G
1
和 G
2
是同构的。事实上，定义它们顶点间的映射 f，分别将顶点 v
1
,v
2
,v
3
,v
4
,v
5
,v
6
映射到 u
1
,u
3
,u
5
,u
2
,u
4
,u
6
，显然这是 G
1
到 G
2
的一个一一映射，且容易验证它保持顶点间的相邻关系。
图 G
2
和 G
3
也是同构的。 事实上,定义它们顶点间的映射 g,分别将顶点 u
1
,u
2
,u
3
,u
4
,u
5
,
u
6
映射到 w
1
,w
2
,w
3
,w
4
,w
5
,w
6
，显然这是 G
2
到 G
3
的一个一一映射，且容易验证它保持顶点间的相邻关系。
图 G
3
和 G
4
不同构，因为 G
4
含有三角形（即子图 K
3
）,但 G
3
不含。
注,（ 1） G
1
,G
2
,G
3
的同构性还可以通过它们的二部图特性来证明。可以检验，它们都是完全二部图 K
3,3
。
（ 2）容易证明，两个图 G 和 H 同构当且仅当它们的补图 GH、同构。利用这一结论，
也可以较简便地判定 G
1
,G
2
,G
3
的同构性，事实上,G
1
,G
2
,G
3
的补图都是两个不相交的
C
3
（长为 3的圈）,因此同构。而 G
4
的补图是 C
6
，故 G
4
与前三个图不同构。
G
1
G
2
u
1
u
2
u
3
u
4
u
5
u
6
w
6
w
5
w
1
w
3
w
2
w
4
v
1
v
2
v
3
v
4
v
6
v
5
x
1
x
2
x
3
x
4
x
5
x
6
G
3
G
4
9
关于图的同构有两个猜想至今尚未解决。
猜想 1（ Ulam 重构猜想,1929）设 G 与 H 是两个图,
|V(G)| = |V(H)|,V(G) = {u
1
,u
2
,,u
n
},V(H)={v
1
,v
2
,,v
n
}。
若对 {1,2,,}in?∈ null,都有
ii
Gu Hv，则 GH? 。其中
i
Gv? 表示将 v
i
以及与 v
i
关联的边都从 G 中删除后所得之图，
i
Hv? 类似。
猜想 2 设 G 与 H 都是至少有四条边的图，若存在一一映射,() ()EG EH? →,使得对
()eEG?∈,都有 ()GeH e,则 GH? 。
有关图的重构问题的更多内容可参看,
[1] C.St.J.A,Nash-Williams,The reconstruction problem,in Selected Topics in Graph Theory (L,
W,Beineke and R.J,Wilson eds.),Academic Press,London,(1978) 205-236,
[2]W.T,Tutte,Graph Theory,Cambridge University Press,(2001) 115-124.(影印版：图论，机械工业出版社,2004),
§ 1.2 最短路问题
一、赋权图
给图 G 的每条边 e 赋以一个实数 w(e)，称为边 e 的 权 。每条边都赋有权的图称为 赋权图 。
权在不同的问题中会有不同的含义。例如交通网络中，权可能表示运费、里程或道路的造价等。
设 H 是赋权图 G 的一个子图,H 的权定义为 )(HW ＝
∑
∈ )(
)(
HEe
ew,特别地，对 G 中一条路 P，其权为 )(PW ＝
∑
∈ )(
)(
PEe
ew
。
二,最短路问题
最短路问题：给定赋权图 G 及 G 中两点 u,v，求 u 到 v 的具有最小权的路（称为 u 到 v
的最短路） 。
注,赋权图中路的权也称为路的长，最短 (u,v)路的长也称为 u,v 间的距离，记为 d(u,v)。
最短路问题是一个优化问题，属于网络优化和组合优化的范畴。对这种优化问题的解答一般是一个算法。最短路问题有很多算法，其中最基本的一个是 Dijkstra 算法。
三,Dijkstra 算法
1,算法思想
设赋权图 G 中所有边都具有非负权,Dijkstra 算法的目标是求出 G 中某个指定顶点
0
v 到其它所有点的最短路。它依据的基本原理是：若路
01 1kk
Pvv vv
= null 是从
0
v 到
k
v 的最短路，
则
01 1k
Pvv v
′= null 必是从
0
v 到
1k
v
的最短路。基于这一原理，算法由近及远地逐次求出
0
v
到其它各点的最短路。
10
下面通过例子说明具体做法。
图 1.1
（ 1）令
0
{}Sv=,\SVS=,求
0
v 到 S 中最近点的最短路。在当前的例子中，从 v
0
v
1
、
v
0
v
2
,v
0
v
3
中选一条最短的，结果获得 v
0
到 v
1
的最短路 v
0
v
1
。
（ 2）令
1
:{}SS v= ∪,,\SVS=,求
0
v 到 S 中最近点的最短路。这里“最近”是指
0
v 到 S
的直接连边、以及从
0
v 出发的已有最短路上的点（即 S 中除
0
v 外的点，当前只有
1
v ）通过最短路再添加上向 S 的连边所形成的路中最短的。即选取 S 中一点 v使得距离
00
,
(,) min{(,) ( )}
i
ii
vSvS
dv v dv v wvv
∈∈
=+。 (*)
在当前的例子中，从 v
0
v
2
,v
0
v
3
,v
0
v
1
v
2
,v
0
v
1
v
3
中选一条最短的，结果获得 v
0
到 v
3
的最短路
v
0
v
1
v
3
。
（ 3）令
3
:{}SS v= ∪,,\SVS=,求
0
v 到 S 中最近点的最短路。即选取 S 中一点 v使得
00
,
(,) min{(,) ( )}
i
ii
vSvS
dv v dv v wvv
∈∈
= + 。
当前应从 v
0
v
2
,v
0
v
1
v
2
,v
0
v
1
v
3
v
2
,v
0
v
1
v
3
v
4
中选一条最短的,结果获得 v
0
到 v
4
的最短路 v
0
v
1
v
3
v
4
。
（ 4）令
4
:{}SS v= ∪,,\SVS=,求
0
v 到 S 中最近点的最短路。即选取 S 中一点 v使得
00
,
(,) min{(,) ( )}
i
ii
vSvS
dv v dv v wvv
∈∈
= + 。
当前应从 v
0
v
2
,v
0
v
1
v
2
,v
0
v
1
v
3
v
2
,v
0
v
1
v
3
v
4
v
2
中选一条最短的，结果获得 v
0
到 v
2
的最短路 v
0
v
1
v
2
（或 v
0
v
1
v
3
v
4
v
2
） 。
一般地，若
01
{,,,}
k
Svv v= null 以及相应的最短路已找到，则可用 (*)式来选取 v，获得
0
v
到 v的最短路。
2．算法实现－标号法
在上述算法的过程中，每轮循环求
0
(,)dv v 时，都要对所有的点
i
vS∈ 计算
0
(,) ( )
ii
dv v wvv+ 且比较出一个最小的值，因而在算法循环过程中需要大量重复的路长计算和比较。为了避免这种重复计算,Dijkstra 算法采用标号方法来实现：算法执行中，给每个点 v 都附一个标号 l(v)，表示当前已经算出的从 v
0
到该点的最短路的长
0
(,)dv v。算法每轮循环都考虑修改点 v 的标号,如果通过此前刚刚进入 S 集合的点 v
i
到该点的连边不能获得更短的路，则该点保持原有标号 l(v)不变；否则，修改该点标号为 l(v),= l(v
i
) + w(v
i
v)，当前
v
0
到 v 的最短路应由 v
0
到 v
i
的最短路及边 v
i
v 构成。
1
v
0
v
1
v
2
v
3
v
4
5
8
1
2
2
6
4
11
标号法的基本原理是累进比较。初始时，
0
():0lv =,∞=:)(vl,（
0
vv≠ ）,
0
{}Sv=,
\SVS= 。然后算法逐步修改 S 中顶点的标号。第 i 步时，对 S 中每个 v，只对刚进入 S
的点 v
i
计算
0
(,) ( )
ii
dv v wvv+ （即 () ( )
ii
lv wvv+ ）,并与 ()lv进行比较，取其较小的一个作为的新标号，即 (),min{(),( ) ( )}
ii
lv lv lv wvv=+。因为对在
i
v 之前进入 S 的点
01 1
,,,
i
vv v
null,
0
(,) ( )
kk
dv v wvv+ （ k = 1,2,…,i?1）的值及其大小信息已含于 ()lv之中，
因此只需计算一个值
0
(,) ( )
ii
dv v wvv+,并将其与此前纪录的最短路的长 ()lv进行比较即可，而不必对所有的点
i
vS∈ 都重新计算
0
(,) ( )
ii
dv v wvv+ 且比较出一个最小的，从而避免了重复计算和比较。
按照算法过程，标号法实现算法主要包括两个过程,（ 1）修改各点的标号,（ 2）从 S 的所有点中取标号最小的一个点，放入 S 中。某个点被放入 S 集合后，它的标号成为永久标号，不再被修改。算法反复执行上述过程，直至所有顶点获得永久标号（被放入 S 中） 。
算法具体步骤如下,
Dijkstra 算法：求非负权图中 v
0
点到其余各点的最短路。
第 1 步,令
0
():0lv =,∞=:)(vl,（
0
vv≠ ）,
0
:{}Sv=,:\SVS=,0:=i 。
第 2 步,对每个 vS∈,令 (),min{(),( ) ( )}
ii
lv lv lv wvv=+。
取 *vS∈ 使得 (*) min{()}
vS
lv lv
∈
= 。 记 *
1i
vv
+
=,令
1
:{}
i
SS v
+
= ∪,:\SVS= 。
第 3 步,令 1,+= ii 。如果 1i υ=?,则停止；否则，转第 2 步。
3,算法正确性
定理 1.2.1 Dijkstra 算法结束时，对任一个顶点 v，其标号 l(v)恰是 v
0
到 v 的最短路的长。
证明：按照算法，顶点 v 的最终标号 l(v)是 v 进入集合 S 时的标号。假设 v 在算法第 i 次循环时进入集合 S，则
1i
vv
+
=,且 v 进入集合 S 后 {,,,,}
01 1ii
Svv vv
+
= null 。由于 l(v)是算法在前 i 次循环中逐次比较出的当前从 v
0
到 v 最短路的长,因此从 v
0
到 v 仅含 {,,,,}
01 1ii
vv vv
+
null
中点的任何路的长都不会小于 l(v)。任取图 G 中一条从 v
0
到 v 的路 P，如果 P 仅含
{,,,,}
01 1ii
vv vv
+
null 中的点，则如上所述,P 的长不会小于 l(v)；如果 P 含 {,,,,}
01 1ii
vv vv
+
null
之外的点，无妨设沿着 P 从 v
0
出发第一个不在 {,,,,}
01 1ii
vv vv
+
null 中的顶点是 v′。因在算法第 i 次循环时,v
i+1
进入 S 而 v′ 仍未进入 S，说明当前 l(v
i+1
)≤ l(v′ )。注意 v′ 只是 P 的中途点且图 G 中所有边的权都非负,而当前的 l(v′ )大于或等于 v
0
到 v′ 仅含 {,,,,}
01 1ii
vv vv
+
null 中点的最短路的长，故路 P 的长大于或等于 P 上 v
0
到 v′ 段的长（ ≥ l(v′ )）,从而 P 的长不会小于 l(v
i+1
)（即 l(v)） 。 证毕。
按照上述定理,Dijkstra 算法结束时，每个顶点的标号 l(v)表示 v
0
到该点的最短路的长。
此外，通过检查标号的来源点，可反向追踪得到 v
0
到各点的最短路。
4,算法有效性
对于一个图论算法，如果在任何图上施行这个算法所需要的基本计算量（比如加、减、
12
乘、除运算或比较、赋值等）都以图的顶点数 υ的一个函数为其上界，则称这个函数为该算法的计算复杂度或时间复杂度，一般简称为 复杂度 （ complexity） 。图的顶点数 υ称为图论问题的规模。人们总是希望利用计算机执行算法以解决人工难以计算的大规模问题，因此，对一个算法人们主要关心它在解决大规模问题时的计算量。对于图论算法，主要关心当图的顶点数 υ增大时，算法所需计算量的增加情况。如果一个算法的计算复杂度是规模 υ的指数函数，比如 2
υ
,!υ 等，则当问题的规模较大时，算法所需的计算量快速增大以至于无法接受，
这样的算法在解决大规模问题时实际上是无用的。当一个算法的计算复杂度是多项式函数时，算法的计算量随规模的增加其增幅较缓，人们认为一般是可以接受的。因此，一个具有多项式时间复杂度的算法称为是 有效算法 （ efficient algorithm）或 好算法 (good algorithm）,
有时直接称为多项式时间算法或 多项式算法 。对于多项式算法，影响其时间复杂度的主项是多项式的最高次项，因此人们在作算法分析时，主要关注其最高次项。一般地，如果一个算法的复杂度是
1
110
kk
aa aaυυ υ
+ ++ +null,则我们说它的计算复杂度是 ()
k
O υ,或是
()
k
O υ 阶的。利用这个记号，如果一个算法的复杂度是 2
υ
或 !υ,我们也可写为 O(2 )
υ
或
O( !)υ 。
按照复杂度的上述定义，如果一个算法是 ()
k
O υ 阶的，则它也是
1
()
k
O υ
+
阶的，甚至也是 O(2 )
υ
阶的。但实际上，人们在提到算法的复杂性时，总是指它的最低的阶。
下一定理表明 Dijkstra 算法是多项式算法。
定理 1.2.2 Dijkstra 算法的计算复杂度为 ()
2
O υ 。
证明,Dijkstra 算法的主要计算量在第 2 步。在第 i 次循环中，第 2 步第 1 式需要 1iυ次加法,1iυ次比较；第 2 式需要不超过 1iυ 次比较。 ( 0,1,,2i υ=?null )。从而 1υ?
次循环总的计算量不超过
2
0
3( 1)
i
i
ν
υ
=
=
∑
3( 1)
2
υ υ?
= ()
2
O υ 。
对一个需要用算法解决的问题，如果存在求解它的多项式算法，则这个问题称为 P 问题 (polynomial problem)。如果一个问题，当猜出其答案时可在多项式计算量内验证答案的正确性，则这个问题称为 NP 问题 (non-deterministic polynomial problem)。将所有 P 问题的集合记为 P，所有 NP 问题的集合记为 NP，是否 P=NP？这是计算机科学和组合最优化领域的一个重要未解难题。明显地 PNP?,但人们目前还不知道是否 PNP? 。 Cook(1970)发现
NP 问题中有一类问题，只要其中有一个问题是 P 问题，则所有 NP 问题全是 P 问题，即
P=NP。 这类问题称为 NP完全问题,简称为 NPC问题 (non-deterministic polynomial problem)。
遗憾的是，对目前已找到的成千上万个 NPC 问题，人们还未能证明其中任何一个是 P 问题。
图论中有许多问题属于 NPC 问题。有兴趣的读者可参阅下列文献。
[2] http://www.nada.kth.se/~viggo/problemlist/
[3] M,R,Garey & D,S,Johnson,Computers and Intractability? a guid to the theory of
NP-completeness,W,H,Freedman,San Francisco,1979,（中译本：张立昂等译，计算机和难解性— NP 完全性理论导引，科学出版社,1987） 。
[4] D.S,Hochbaum,Approximation algorithms for NP-hard problems,International Thomson
13
Publishing Company,1995,
[5] Ding-zhu Du and Ker-I Ko,Theory of Computational Complexity,John Wiley & Sons,INC.,
New York,2000,
[6] Feng Gao,Ding-zhu Du,Biao Gao,Peng-jun Wan,and P,M,Pardalos,Minimax problems in
combinatorial optimization,Minmax and Applications (eds,by Ding-zhu Du & P,M,Pardalos),
Kluwer Academic Publishers,1995,
[7] D.B.Shmoys,Computing near-optimal solutions to combinatorial optimization problems,
Combinatorial Optimization (W.Cook,L.Lovasz and P.Seymour eds.),DIMACS Series in Discrete
Mathematics and Theoretical Computer Science,Vol.20,(1995) 355-397,
[8] C.H,Papadimitriou & K,Steiglitz,Combinatorial Optimization,Algorithms and Complexity,
Prentice-Hall,Inc.,Englewood Cliffs,New Jersey,1982,
[9] A,Gibbons,Algorithmic graph theory,Cambridge,Cambridge University Press,1985,
[10] M,R,Garey & D,S,Johnson and L,Stockmeyer,Some simplified NP-complete graph
problems,Theoret,Comput,Sci.,I 237-267,1976,
[11] Cook S,The complexity of theorem-proving procedure,Conference Record of Third ACM
Symposium on Theory of Computing,1970,pp151-158,
[12] 王树禾，图论及其算法，中国科技大学出版社,1990。
[13] 谢政，网络算法与复杂性理论（第二版）,国防科技大学出版社,2003。
上述 Dijkstra 算法可以用列表的方式进行计算，下面举例说明。
考虑图 1.1 中的赋权图。首先将顶点 v
1
,v
2
,v
3
,v
4
作为一行。然后将起始点 v
0
放在表内第一行左首，将 v
0
到其余各点连边上的权（即标号 l(v
k
)）放在各顶点下方相应位置上。
从第一行数字中选取最小的一个，用方括号标记，并在斜杠下方标上 v
0
，当前找到 v
1
下方的数字最小。接着，将 v
1
放在表内第二行左首（表示 v
1
进入集合 S）,对每个尚未进入 S 的顶点 v
k
，将第一行方括号中的数字与边 v
1
v
k
上的权相加，并与第一行 v
k
下方的数字比较，
取较小的一个（即新标号 ():min{(),() ( )}
11kk k
lv lv lv wvv=+）放在第二行相应位置上。
从第二行数字中选取最小的一个，用方括号标记，当前找到 v
3
下方的数字最小。由于该数字 3 是通过 v
1
得来的（即 min{ ( ),( ) ( )}
31 13
lv lv wvv+
113
() ( ) 3lv wvv= +=）,故在该数字斜杠下方标上 v
1
。
同样，将 v
3
放在表内第三行左首（表示 v
3
进入集合 S）,对每个尚未进入 S 的顶点 v
k
，
S V v
1
v
2
v
3
v
4
v
0
[1]/v
0
8 4 ∞
v
1
6 [3]/v
1
∞
v
3
6 [5]/v
3
v
4
[6]/v
1
14
将第一行方括号中的数字与边 v
3
v
k
上的权相加，并与第二行 v
k
下方的数字比较，取较小的一个（即新标号 ():min{(),() ( )}
33kk k
lv lv lv wvv=+）放在第三行相应位置上。并从第三行数字中选取最小的一个，用方括号标记，当前找到 v
4
下方的数字最小。由于该数字 5 是通过 v
3
得来的（即 min{ ( ),( ) ( )}
43 34
lv lv wvv+
334
() ( ) 5lv wvv= +=）,故在该数字斜杠下方标上 v
3
。最后，将 v
4
放在表内第四行左首（表示 v
4
进入集合 S）,对尚未进入 S 的唯一顶点 v
2
，将第一行方括号中的数字与边 v
3
v
2
上的权相加，并与第三行 v
2
下方的数字比较，
取较小的一个（即新标号 ():min{(),() ( )}
22442
lv lv lv wvv=+）放在第四行相应位置上。
并从第四行数字中选取最小的一个，现在第四行只有 v
2
下方的数字 6，用方括号标记之,v
2
进入集合 S 。由于该数字 6 可看成是通过 v
2
的旧标号 l(v
2
) 得来的（即
min{ ( ),( ) ( )}
24 42
lv lv wvv+
2
() 6lv==）,旧标号 l(v
2
)又是在第二行通过 v
1
得来的，故在该数字斜杠下方标上 v
1
。至此，算法结束。从每个顶点 v
k
所在列的最后一个数字（方括号内的数字）可以得知 v
0
到 v
k
的最短路的长。比如,v
0
到 v
4
的最短路的长为 5。
由斜杠后的标识可反向追踪出最短路。比如找 v
0
到 v
4
的最短路：先从 v
4
列下方的标识找到 v
3
，再从 v
3
列下方的标识找到 v
1
，最后从 v
1
列下方的标识找到 v
0
，从而可知 v
0
到 v
4
的最短路为 v
0
v
1
v
3
v
4
。
Dijkstra 算法也可以通过矩阵形式来进行，其步骤为,
第 0 步,将赋权图 G 的权矩阵 (w
ij
)的第一列中所有元素全改为×，在第一行剩下的其他元素下面划一条横线。
第 1 步,在画横线的元素中找一个最小的 w
ki
，若 w
ki
=∞，则停止，从 v
0
到某些顶点没有路；
否则，把 w
ki
用方括号标记，并把第 i 列其他元素都改成×，然后给第 i 行中不是×的元素都加上 w
ki
，并在这些元素下面划一条横线，转第 2 步。
第 2 步,如果存在不含×的列，则转第 1 步；否则结束，方括号标记的元素 w
ij
表示从 v
0
到
v
j
的最短路的长，而从 v
0
到 v
j
的最短路由最短 (v
0
,v
i
)路与边 v
i
v
j
构成。
仍以图 1.1 为例，其权矩阵为
(w
ij
) =
01234
0
1
2
3
4
184
152
85 61
426 2
12
vvvvv
v
v
v
v
v
∞ ∞
∞ ∞
∞
∞
∞ ∞∞
184
152
85 61
426 2
12
∞∞
∞
∞
∞∞ ∞
184
52
561
26 2
12
×∞
×∞ ∞
×∞
×∞ ∞
[1] 8 4
63
61
62
12
× ∞
× ×∞
×× ∞
×× ∞
× ×∞
15
[1] 8
6[3]
1
95
1
××∞
×× ∞
×× ∞×
×× ×
×× × ∞
[1] 8
6[3]
9[5]
6
×××
×× ×
×× ∞× ×
×× ×
×× × ×
[1]
[6] [3]
[5]
× ×××
× ××
× ××××
×× × ×
× ××××
由最后一个矩阵的元素回溯便可获得 v
0
到各点的最短路。比如,v
4
的最短路的长为 5；
为找从 v
0
到 v
4
的最短路，从 v
4
所在列（最后一列）开始回溯，因该列非×元素在 v
3
行（第
4行）,v
3
列非×元素在 v
1
行（第 2 行）,而 v
1
列非×元素在 v
0
行（第 1 行）,故 v
0
到 v
4
的最短路为 v
0
v
1
v
3
v
4
。
上述最短路算法仅适用于求所有边的权均非负的途中的最短路。 在边允许有负权的图中求最短路，有 Ford 算法和 Floyd 算法。 Ford 算法用于求无负权圈的图中一点到其它各点的最短路； Floyd 算法用于求无负权圈的图中所有顶点对之间的最短路。这两个算法当然也可以用于所有边的权均为非负的图中。有兴趣的读者可参看文献 [14],[15],[16]。求图的前 k
条最短路的算法可参考 [16]。
[14] 谢政,网络算法与复杂性理论（第二版）,国防科技大学出版社,2003。
[15] 王朝瑞,图论（第三版）,北京理工大学出版社,2001。
[16] N,Christofides,Graph Theory–a algorithmic approach,Academic Press,INC.,1990,
此外,对分层图,也可用动态规划方法来求最短路。 动态规划源于多阶段最优决策过程，
它的基本思想是 Bellman 最优化原理。该原理可概括地描述为：如果图 G 中从 A 点到 C 点的最短路 P 经过点 B，则 P 上 B 到 C 的一段必定是该图中 B 点到 C 点的最短路。依据这个原理，可用一个基本的递推关系式使最优决策过程连续地转移。使用动态规划方法时，要从最终状态开始逐步递推到起始状态。例如，对下图求 A 到 H 的最短路。
该图的顶点从 A 到 F 分为 5 层，同层顶点间互不连边，隔层顶点间也没有连边，这便是分层图。我们从 H 点开始考虑。其前一层顶点 F 和 G 到 H 的最短路的长分别是 4 和 3，
记为 W(F)=4,W(G)=3。再考虑 F 和 G 的前一层顶点 D 和 E。从 D 出发有两种选择,DFH，
路长为 1+ W(F)=5； DGH，路长为 1+ W(G)=4；故从 D 到 H 的最短路为 DGH,W(D)=4。
同样可知，从 E 到 H 的最短路为 EGH,W(E)=5。再考虑 B,C。 B 到 H 可经过 D 也可经过
E，经 D 到 H 的最短路长为 6+W(D)=10，经 E 到 H 的最短路长为 6+W(E)=11，故从 B 到 H
的最短路应经过 D，且最短路长为 W(B)=10。同样可得，从 C 到 H 的最短路应经过 D，且最短路长为 W(C)=8。最后考虑顶点 A，它到 H 可经过 B 也可经过 C，经 B 到 H 的最短路长为 4+W(B)=14，经 C 到 H 的最短路长为 5+W(C)=13，故从 A 到 H 的最短路应经过 C，
且最短路长为 W(A)=13。因此获得 A 到 H 的最短路为 ACDGH。
A
B
C
D
E
F
G
H
4
5
6
6
7
4
4
2
1
1
2
3
16
在上述过程中，决定每层顶点的结果只需要做 4 次加法。如果将图扩展为 n 层，则计算量为 4(n?3)+2，这比 Dijkstra 算法的计算量低的多。由此可见，针对具体问题的特点可以设计出非常有效的算法。
关于最短路问题读者可进一步参阅文献,
[17] E,Dijkstra,A note on two problem in connection with graphs,Numer,Math.,1(1959)
269-271,
[18] L.R,Ford,Network flow theory,Rand Corporation Report,(1956) 923,
[19] R.W,Floyed,Algorithm 97- Shortest Path,Comm.,ACM,5(1962) 345,
[20] D,Bertsekas,A simple and fast label correcting algorithm for shortest paths,Networks,
23(1993) 703-709,
[21] M,Desrochers,and F,Soumis,a reoptimization algorithm for the shortest path problem with
time windows,Europaean Journal of Operational Research,35(1988) 242-254,
[22] M.Dror,Note on the complexity of the shortest path models for column generation,
Operations Research,42(1994) 977-978,
[23] G,Gallo,and S,Pallottino,Shortest path algorithms,Annals of Operations Research,7(1988)
73-79,
[24] F,Glover,R,Glover,and D,Klingman,The threshold shortest path algorithm,Networks,
14(1984) 25-36,
[25] W.B,Powell,Zhi-Long Chen,A generalized threshold algorithm for the shortest path problem
with time windows,in Network Design,Connectivity and Facilities Location (P.M,Pardalos and
Ding-zhu Du eds.),DIMACS Series in Discrete Mathematics and Theoretical Computer Science,
Vol.40,(1998) 303-318,
§ 1.3 树及其性质
不含圈的图称为 森林 (forest)，不含圈的连通图称为 树 （ 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）
17
若 G 有圈，则此圈上任二顶点间有两条不同的路，与前提条件矛盾。
下面用归纳法证明 1ε υ=?。
1υ = 时,0=ε,结论真。
假设 kυ ≤ 时结论真，我们来证明当 1kυ = + 时，也有 1ε υ=? 成立。
当 1kυ =+时，任取边 E( )uv G∈ 。考虑图 uvGG?=′,因 G 中 u,v 间只有一条路，
即边 uv，故 G′不连通且只有两个连通分支，设为
21
,GG 。注意到
21
,GG 分别都连通且任二顶点间只有一条路，由归纳法假设，
11
() ()1GGε υ=?,
22
() ()1GGε υ=? 。因此
12 1 2
() () ()1(()1)(()1)1 ()1GG G G G Gε εε υ υ υ= + +=?+?+=?。
归纳法完成。
（ 3）?（ 4）
用反证法。若 G 不连通，设
w
GGG,,,
21
null 是其连通分支（ 2≥w ）,则 1
ii
ε υ=?（因
i
G 是连通无圈图，由已证明的 (1) 和 (2) 知，对每个
i
G,（ 3 ）成立） 。这样，
11
ww
ii
ii
wwεευ υ
==
==?=?
∑∑
，这与 1ε υ=? 矛盾。
（ 4）?（ 5）
()()1 2Ge Gε ευ?=?=?，但每个连通图必满足 1ε υ≥?（见下列引理）,故图
eG? 不连通。
引理 若图 H 连通，则 () ()1HHε υ≥?。
证明：对 υ做数学归纳法。
1,2υ = 时,1ε υ≥?显然成立。
假设 kυ ≤ 的连通图都 1ε υ≥?。
对于 1kυ =+的连通图 H，任取 )(HVv∈,考虑 vH? 。
若 vH? 连通，则由归纳假设,()()11Hv Hv kε υ? ≥=?，而
() ( )1( 1)1( 1)1 ()1HHv k k Hε ευ≥? +≥? += +?=?。
若 vH? 不连通，设
w
HHH,,,
21
null 是其连通分支 ( 2≥w ) 。由归纳假设，
() ()1
ii
HHε υ≥?,( wi,,2,1 null= )。故
11
( ) () () ( )
ww
ii
ii
Hv H H w Hv wkwεευυ
==
= ≥?==?
∑∑
,
而 () ( ) ( ) ( 1)1 ()1HHvwkwwk Hε ευ≥?+≥?+=+?=?。
归纳法完成。
（ 5）?（ 6）
先证 G 中无圈：若 G 中有圈，删去圈上任一边仍连通，矛盾。
18
再证对任何 )(GEe∈,eG + 恰含一个圈：因 G 连通且已证 G 无圈，故 G 是树。由
（ 2）,任二不相邻顶点间都有一条路相连，故 eG + 中必有一个含有 e 的圈；另一方面，若
eG + 中有两个圈含有 e，则 ( eG + ) Ge =? 中仍含有一个圈，矛盾。
（ 6）?（ 1）
只需证 G 连通。任取 )(,GVvu ∈,若 u,v 相邻，则 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,则
1
() 2
i
i
dv
υ
υ
=
≥
∑
。但另一方面，
1
() 2 2( 1) 2 2
i
i
dv
υ
ευ υ
=
= =?=?
∑
。
这两方面矛盾。故 T 至少有一个 1 度顶点，设为 u。除此之外，其余 1υ? 个顶点的度数之和为 23υ? 。若这些点的度都大于或等于 2，则其度数之和 2( 1) 2 2υ υ≥?=?。这与
23υ? 矛盾。故除 u 之外 T 还至少有一个度为 1 的顶点。证毕。
§ 1.4 生成树与最小生成树
一、生成树（ spanning tree）
定义 1.4.1 设 T 是图 G 的一个子图，如果 T 是一棵树，且 () ()TGυ υ=,则称 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 ()1GT T Gε ευ υ≥≥?=?。证毕。
二、最小生成树问题
最小生成树问题,在赋权图 G 中，求权最小的生成树（简称为最小生成树） 。即：求 G 的一棵生成树 T，使得
∑
∈
=
Te
T
ewTw )(min)( 。
19
最小生成树问题是一个优化问题，需要设计优化算法寻找其最优解。求解最小生成树问题的算法较多，本节主要介绍 Kruskal 算法和 Prim 算法。
（一） Kruskal 算法 (Joseph Bernard Kruskal,1956)
1,算法思想,先从图 G 中找出权最小的一条边作为最小生成树的边，然后逐次从剩余边中选边添入最小生成树中，每次选边找出不与已选边构成圈的权最小的一条边。直至选出
(G) 1υ? 条边为止。
2,算法步骤,输入：赋权连通 υ阶图 G。输出,G 的最小生成树 T。
第一步 取 )(
1
GEe ∈ 使得 () min{ ()},
eG
we we
∈
= 令,1i = 。
第二步 取 },,,{\)(
211 ii
eeeGEe null∈
+
使得
(1) G[{
121
,,,,
+ii
eeee null }] 不含圈； (2)
1+i
e 是满足 (1)的权最小的边。
第三步 当 i+1 = ()1Gυ? 时,输出最小生成树 G[{
12 1
,,,ee e
υ?
null }]，算法停止 ; 否则,令
1,+= ii,转第二步。
3,算法正确性,
定理 1.4.2 设
12 ()1
,,,
G
ee e
υ?
null 是 Kruskal 算法获得的边,则边导出子图 G[{
12 ()1
,,,
G
ee e
υ?
null }]
是 G 的最小生成树。
证明：记
*
T = G[{
12 ()1
,,,
G
ee e
υ?
null }]。显然
*
T 无圈，因此
*
T 是森林。设它有 w 个连通分支，则 (T ) (T ) (T ) 1 ( (G) 1) 1 (G)wυε ε υ υ
=+≥+=?+=。
但
*
T 是 G 的子图，故
*
() ()TGυυ= 。于是
**
() ()1 ()1TG Tευ υ=?=?。
由定理 1.3.1 的 (3)，
*
T 是一棵树。又
*
() ()TGυυ=,从而是 G 的一棵生成树。
下证其最优性，用反证法。
假设
*
T 不是权最小的生成树 (下称最优树 )。对 G 的任一棵不同于
*
T 的生成树 T，记
12 1
() min{| {,,,}
i
f Tieee
υ?
=∈null 且 }Te
i
。
在Ｇ的所有最优树中选取一棵使 )(Tf 最大的，记为 T
~
。 (T
~
不会是
*
T,因假设
*
T 不是最优树 )。设 kTf =)
~
( 。由 )
~
(Tf 的定义，
121
,,,
k
eee null 既在
*
T 上也在 T
~
上，但
k
e 不在
T
~
上。因此
k
eT +
~
含有一个圈 C。 C 上必有一条边
*
Te
k
′ 。显然
kk
eeTT ′?+=′ )
~
( 也是一棵生成树，且 )()()
~
()(
kk
ewewTwTw ′?+=′ 。
按照算法，
k
e 是使 G[{
k
eee,,,
21
null }] 中无圈的边中权最小的。注意
G[{
kk
eeee ′
,,,,
121
null }] 是 T
~
的子图，也无圈。故由算法规则知：
)()(
kk
ewew ≥′
。由前式，
)
~
()( TwTw ≤′
,这说明
T′
也是最优树。 但
)
~
()( TfkTf =>′
（注意由于
121
,,,
k
eee null 在
*
T
上且
*
Te
k
′,故
12 1
{,,,}
kk
eee e
′? null
） 。这与
T
~
的取法矛盾。证毕。
4,Kruskal 算法的实现及其计算复杂度分析
20
Kruskal 算法的计算量主要在第二步。算法共需执行 1υ? 次第二步，在第 i 次执行第二步时，须比较集合
12
()\{,,,}
i
EG e e enull 中所有边的权以求得一条权最小的边，并检验该边是否与已有边构成圈，如果构成圈，还需再找新的最小权边，这是比较浪费的。
在实际应用 Kruskal 算法时，一般先将所有的边按权由小到大排序，这需要大约
2
logε ε
次比较（见 [26]） 。每次执行算法第二步时，不必再比较边的权，而是直接选取此前尚未考虑过的权最小的边，检验它是否与已有边构成圈即可。这样可省去许多次循环比较。
[26] D.E,Knuth,The art of computer programming,Vol.3,Sorting and Searching,
Addison-Wesley,Reading,Mass.,(1973)184,
接下来的问题是如何检验所选边是否与已有边构成圈。这可通过给顶点标号来实现。设算法在 i 次循环后选出的边集合为 E
i
。算法开始时，给所有顶点标不同的标号：顶点
k
v 标号为 k,（ 1,2,,k υ= null ） 。当算法执行第 i+1 次循环选出一边
1i
e
+
添加进 G[E
i
]形成 G[E
i+1
]
时,用该边两端点标号的较小者给这条边所连的 G[E
i+1
]的两个连通分支的顶点重新标号 （连通分支有可能仅由
1i
e
+
的一个端点组成） 。按这个标号方案，在任意一步中，两个顶点属于已选边形成的同一连通分支当且仅当它们有相同的标号。这意味着当我们考虑向 G[E
i
]添加某条边 e是否会形成圈时，只要检查 e的两个端点是否有相同的标号即可。如果有相同的标号，则抛弃该边（以后的循环中不再使用）,再检验权稍大些的下一个候选边；如果标号相异，则取 e 作为
1i
e
+
添加进 G[E
i
]。在这个过程中，对每条候选边只需做一次比较就能决定是否抛弃它。算法全过程至多需要 ε
(1)
2
υ υ?
≤ 次这样的比较。
当添加
1i
e
+
进入 G[E
i
]时，顶点重新标号最多需要 υ次比较，因此对 1υ? 条边最多需要
(1)υ υ? 次比较。
可见算法执行过程约需要 ε + (1)υ υ? 次计算。
由以上分析可得如下结论。
定理 1.4.3 若事先将顶点按权排序，则 Kruskal 算法的计算复杂度为
2
O( )υ ；若加上事先排序的计算量，则 Kruskal 算法的计算复杂度为
2
2
O( log )υ υ 。
证明,算法执行过程中需要的主要计算量为 ε + (1)υ υ?
(1)
2
υ υ?
≤ + (1)υ υ? =
3
(1)
2
υυ?,
事先排序需要的计算量为
2
logε ε
2
22
(1) (1)
log log
22
υ υυυ
υ υ
≤≤。故知定理结论成立。证毕。
例 1.4.1 欲建设一个连接 5 个城市的光纤通信网络。各城市间线路的造价如图所示，求一个使总造价最少的线路建设方案。
v
3
v
4
12
87
9
10
6
6
5
8.5
6.4
v
1
v
2
v
5
21
解,算法执行过程如下所示。
（二） Prim 算法 (Robert Clay Prim,1957)
1,算法思想,先从图 G 中找出权最小的一条边作为最小生成树的边,在算法任一轮循环中，
设已经选出的边导出的子图为 G′，从 G′的顶点向 G′以外顶点的连边为 E′，则选择 E′中权最小的边向 G′中添加，如此反复循环直至选出 (G) 1υ? 条边为止。
Prim 算法与 Kruskal 算法的根本区别在于,Kruskal 算法在保持无圈的基础上选边，而在保持连通的基础上选边。 Prim 算法的添边过程实际上是树的生长过程。 Kruskal 算法的添边过程一般情况下是森林合并为树的过程。
在一些文献中,Kruskal 算法也称为避圈法,Prim 算法也称为边割法。
2,算法步骤,输入：赋权连通 υ阶图 G。输出,G 的最小生成树 T。
step1,任取 )(
0
GVv ∈,令
00
{}Sv=,
00
()\SVGS=,,0i =,
0
E φ= 。
step2,求
i
S 到
i
S 间权最小的边
1i
e
+
，设
1i
e
+
的属于
i
S 的端点为
1i
v
+
，令
11
:{}
iii
SSv
++
= ∪,
11
\)(
++
=
ii
SGVS,
11
:{}
iii
EEe
++
= ∪
Step3,当 i+1= ()1Gυ? 时,输出最小生成树 G[E
i+1
]=G[{
12 1
,,,ee e
υ?
null }]，算法停止 ;
否则，令 1,+= ii,转 step2。
3,算法正确性,
定理 1.4.4 设
12 1
,,,ee e
υ?
null 是 Prim 算法获得的边，则边导出子图 G[{
12 1
,,,ee e
υ?
null }]是 G
的最小生成树。
证明：用
k
T 表示 Prim 算法第 k 次循环得到的边集所构成的子图，即
k
T = G[E
k
]=G[{
12
,,,
k
ee enull }],1,2,1k υ=?null 。
我们用归纳法来证明，对每个 k ( 1,2,1k υ=?null ),
k
T 必含于 G 的某个最小生成树中。
当 k=1 时，
1
T 仅由边
1
e 生成。注意到
1
e 是 G 中权最小的边，因此，对 G 的任一棵最小生成树 T
，若 T
不含有
1
e,则
1
Te
+ 有一个圈 C,C 上每条边的权都不小于
1
e 的权
1
()we 。设
e是 C上一条异于
1
e 的边,则
1
TTee
′=+?也是 G的一棵生成树,且其权
*
() ( )wT wT′ ≤ 。
可见 T′也是 G 的一棵最小生成树，并且含有边
1
e 。即
1
T 含于最小生成树 T′中。
假设 k = m 时（ 11m υ≤<?）,结论成立，即
m
T 含于 G 的某个最小生成树 T
*
中。考虑最后一条进入
112 1
[{,,,}]
mmm
TGeeee
++
= null 的边
1m
e
+
。 若
1m
e
+
在 T
*
中,则
11mmm
TTe
++
=+
含于最小生成树 T
*
中。若
1m
e
+
不在 T
*
中，则
1m
Te
+
+ 有一个圈 C。由于
11mmm
TTe
++
=+
v
3
v
4
12
87
9
10
6
6
5
8.5
6.4
v
1
v
2
v
5
v
3
v
4
12
8 7
9
10
6
6
5
8.5
6.4
v
1
v
2
v
5
v
3
v
4
12
8 7
9
10
6
6
5
8.5
6.4
v
1
v
2
v
5
v
3
v
4
12
87
9
10
6
6
5
8.5
6.4
v
1
v
2
v
5
22
无圈，故 C 上必有边属于 T
*
而不属于
m
T,但
m
T 是 T
*
的子图，故 C 上必可找到一条异于
1m
e
+
的边 euv=,使得
m
uT∈ 而
m
vT? 。由算法步骤知，权
1
() ( )
m
we we
+
≥ 。于是
1m
TTe e
+
′=+?也是 G 的一棵最小生成树，并且含有边
1m
e
+
。再注意到
m
T 的边全在 T
*
中，因此上述结论表明
11mmm
TTe
++
=+ 含于最小生成树 T′中。归纳法完成。证毕。
4,计算复杂度分析,
Prim 算法的主要计算量在第二步。在算法第 i 轮循环执行第二步时，
i
S 中有 i 个顶点，
i
S 中有 iυ? 个顶点，故
i
S 到
i
S 间最多有 ()iiυ? 条边。从这些边中选出一条权最小的边
1i
e
+
，需要 ()1iiυ次比较。算法需循环执行第二步 1υ? 次，因此总的计算量为
-1 -1
11
1
[ ( ) 1] ( ) ( 1)( +1)
6
ii
ii ii
υυ
υυ
==
≤?=?
∑∑
。
由此可见,Prim 算法的计算复杂度为
3
()O υ 。与 Kruskal 算法类似，使用顶点标号法可进一步降低 Prim 算法的计算复杂度。
（三） Prim 算法的标号形式―标号 Prim 算法
1,算法思想,给图的顶点赋以标号，该标号与边的权有关，在执行 Prim 算法的过程中，通过修改顶点标号和比较顶点的权，来选择满足 Prim 算法要求的最小权边。
顶点 v 的标号记为 ()lv 。用 ()wuv 表示边 euv= 的权，若,uv两点间没有边，则
()wuv =∞。
2,算法步骤,输入：赋权连通 ν 阶图 G。输出,G 的最小生成树 T。
step1,任取 )(
0
GVv ∈,令
000
() 0,(),( ),{}lv lv v v S v= =∞ ≠ =,
00
()\SVGS=,
00
Tv=,,0i = 。
step2,对 ()
Gi i
vNv S?∈ ∩,若 () ()
i
wvv lv<,则令 (),( )
i
lv wvv= 。
Step3,选取
1ii
vS
+
∈ 使得
1
()min()
i
i
vS
lv lv
+
∈
= 。设
11
,( )
ii i
euvuS
++
= ∈ 使得
11
()()
ii
we lv
++
=,
令
11
:{}
iii
SSv
++
= ∪,
11
\)(
++
=
ii
SGVS,
11
:{}
iii
TTe
++
= ∪ 。
Step4,当 i+1= 1)(?Gν 时,输出最小生成树
1
T
ν?
，算法停止 ; 否则，令 1,+= ii,转 step2。
3,算法正确性,
标号 Prim 算法是 Prim 算法的标号实现,因此由 Prim 算法的正确性即知标号 Prim 算法结束时必能得到图 G 的最小生成树。
4,计算复杂度分析,
算法的主要计算量在第 2 步和第 3 步。算法第一次执行 Step3 需做 n?2 次比较，第二次执行 Step3 需做 n?3 次比较,，因此执行 Step3 共需做
1
(2)(1)
2
υυ 次比较；同样，
执行 Step2 共需不超过
1
(2)(1)
2
υυ次比较。 于是标号 Prim 算法的时间复杂性为 O(υ
2
)。
标号 Prim 算法将 Prim 算法每次循环中比较
1i
S
+
到
1i
S
+
间所有边的权，改为修改
()
Gi i
Nv S∩ 中点的标号并比较
i
S 中点的标号，因此节省了计算量。
23
一些文献中将标号 Prim 算法称为 Dijkstra 最小生成树算法。
5,Prim 算法的矩阵实现―求最小树的权矩阵法
Prim 算法可以通过权矩阵来实现。给定一个赋权的连通 n 阶简单图 G，其各边上的权组成的 n 阶 ()
ij n n
Ww
×
= 称为 G 的权矩阵，其中元素
ij
w 定义如下,
(1),1,2,,
ii
wi n=∞ = null ； (2) 若边 ()
ij
vv E G∈,则 ()
ij i j
wwvv= ； (3)若边 ()
ij
vv E G?,
则
ij
w =∞。
算法步骤为,
Step0,划掉矩阵 W 的第一列（将 W 第一列元素全改为 ×）,并在第一行剩下的每个元素下面画一条横线。
Step1,在画横线的元素中找一个最小的元素
ki
w,并将其圈起来。然后把第 i 列其它元素全部划去（改为 ×）,并在第 i 行没有被划掉的元素下面画上横线。
Step2,若矩阵 W 的所有元素要么已被划去要么已被圈起来，则算法结束，圈起来的元素即对应于所求最小生成树的边。否则，转 Step1。
例 1.4.2 用权矩阵法求如下赋权图 G 的一棵最小生成树。
解：求解过程如下。
W=
20 30 25 50
20 40 30
30 40 10 20
25 30 10 15
50 20 15
∞
∞∞
∞
∞
∞∞
→
20 30 25 50
40 30
40 10 20
30 10 15
20 15
×
×∞ ∞
×∞
×∞ ∞
→
(20) 30 25 50
40 30
10 20
10 15
20 15
×
× ×∞
××∞
×× ∞
× ×∞
→
(20) 30 (25) 50
40
20
10 15
20
×
×× ×∞
××∞×
×× ×
×× ×∞
→
(20) (25) 50
20
(10) 15
××
×× × ×∞
×× × ×
×× ×
×× × ×∞
→
(20) (25)
(10) (15)
× ××
× ××××
× ××××
×× ×
× ××××
。
最后得到的最小生成树由边 v
1
v
2
,v
1
v
4
,v
4
v
3
,v
4
v
5
构成，其权为 20+25+10+15=70。
在实际应用中，往往需要求图的满足某种约束条件的最小生成树。这一类问题统称为约束最小生成树问题（ Constrained minimum spanning tree problems） 。常见的有顶点度约束最小生成树、直径约束最小生成树、边容量约束最小生成树、最多叶子最小生成树等，详细可参阅下列文献 [27]或 [28]~[42]。约束最小生成树问题大多数是 NPC 问题，因此对这些问题主要是设计好的近似算法。
20
30
25
10
30
40
20
50
15
v
1
v
2
v
3
v
4
v
5
24
约束最小生成树问题参考文献
[27] N,Deo and N,Kumar,Computation of constrained spanning trees,a unified approach,
Network Optimization (P.M.Pardalos,D.W.Hearn,and W.W.Hager eds.),Lecture Notes in
Economics and Mathematical Systems,450,Springer-Verlag,Berlin Heidelberg,1997,
[28] D,Kleitman and D.West,Spanning trees with many leaves,SIAM Journal on Discrete
Mathematics,4(1) (1991) 99-106,
[29] N,Deo and N,Kumar,Constrained spanning tree problems,approximate methods and
parallel computation,in Network Design,connectivity and facilities location (P.M,Pardalos and
Ding-zhu Du eds.),DIMACS Series in Discrete Mathematics and Theoretical Computer Science,
Vol.40,(1998) 191-216,
[30]A,Abdallah,N,Deo,N,Kumar,and T,Terry,Parallel computation of a diameter-constrained
MST and related problems,Technical Report CS-TR-97-04,Department of Computer Science,
University of Central Florida,Orlando,(1997),
[31] B,Boldon,N.Deo,and N,Kumar,Minimum-weight degree-constrained spanning tree
problem,heuristics and implementation on an SIMD parallel machine,Parallel Comput,
22(1996)369-382,
[32] G,Craig,M.Krishnamoorthy,and M.Palaniswami,Comparison of heuristic algorithms for the
degree constrained minimum spanning tree,In Meta-heuristics,Theory and Applications
(I.H.Osman and J.P.Kelly eds.),(1996)83-96,
[33] N,Kumar,Parallel computation of constrained spanning trees,heuristics and SIMD
implementations,Ph.D,Dissertation,Department of Computer Science,University of Central
Florida,Orlando,(1997),
[34] B.M.E.Moret,and H.D.Shapiro,An empirical analysis of algorithms for constructing
minimum spanning tree,Lect,Notes on Comp,Science,519(1991)400-411,
[35] G,Galbiati,F,Maffioli,A,Morzenti,A short note on the approximability of the maximum
leaves spanning tree problem,Info,Proc,Lett,52(1994)45-49,
[36] L,Gouveia,A 2n constraint formulation for the capacitated minimal spanning tree problem,
Operation Research,43(1995) 130-141,
[37] H,I,Lu,R,Ravi,The power of local optimization,Approximation algorithms for
maximum-leaf spanning tree,in Proc,30
th
Allerton Conference,(1992)533-542,
[38] K,Malik,G,Yu,A branch and bound algorithm for the capacitated minimum spanning tree
problem,Networks,23(1993) 525-532,
[39] W,Xu,Quadratic minimum spanning tree problems and related topics,Ph.D,Dissertation,
Dept,of Math.,Univ,of Maryland,College Park,MD,(1984),
[40] M.R,Henzinger and V,King,Maintaining minimum spanning forests in dynamic graphs,
SIAM J,on Computing,31:2(2001) 364-374,
[41] G,Robins and J.S,Salowe,Low-degree minimum spanning trees,Discrete and
Computational Geometry,14:2(1995)151-166,
[42] 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,
有关随机生成树问题可参阅,
[43] D.J,Bertsimas,The probabilistic minimum spanning tree problem,Networks,20 (1990),
245-275,
25
[44] S.Geetha,K.P.K.Nair,On stochastic spanning tree problem,Networks,23(1993)675-679,
[45] H,Ishii,S,Shiode,T,Nishida,Y,Namasuya,Stochastic spanning tree problem,Discrete
Applied Mathematics,3(1981) 263-273,
[46] I.B,Moret,Interval elimination method for stochastic spanning tree problem,Appl,Math,
And Computation,66(1994) 325-331,
有时需要考虑欧氏距离下图的最小生成树问题，这方面可参考文献,
[47] C,Monna,and S.Suri,Transitions in geometric minimum spanning trees,Discrete and
Computational Geometry,8:2(1992)265-293,
[48] J.M,Ho,D.T.Lee,C.H,Chang,C.K,Wong,Minimum diameter spanning trees and related
problems,SIAM J,Computing,20:5(1991) 987-997,
[49] S,Khuller,B.Raghavachari,and N.Young,Low degree spanning tree of small weights,SIAM
J,Computing,25:2(1996) 355-368,
[50] G,Robins and J.S,Salowe,On the maximum degree of minimum spanning trees,Discrete
and Computational Geometry,14:2(1995)151-166,
关于最小生成树的更全面的介绍请参看文献,
[51] R.K,Ahuja,T.L,Magnanti,and J.B,Orlin,Network Flows,Prentice Hall,1993,
[52] D.R,Karger,P.N,Klein,and R.E,Tarjan,A randomized linear-time algorithm to find
minimum spanning trees,J,Assoc.Comp,Mach.,42(1995) 321-328,
[53] R.E.Tarjan,A simple version of Karzanov’s blocking flow algorithm,Operation Research
Letters,2(1984) 265-268,
[54] H.N.Gabow,Z.Galil,T.Spencer,and R.E.Tarjan,Efficient algorithms for finding minimum
spanning trees in undirected and directed graphs,Combinatorica,6(1986) 109-122,
[55] J.B.Jr.Kruskal,On the shortest spanning subtree of a graph and the Traveling Salesman
Problem,Proceedings of the American Mathematical Society,7(1956) 48-50,
[56] R.C.Prim,Shortest connection networks and some generalizations,Bell Systems Technical
Journal,36(1957) 1389-1401,
[57] S,Khuller,B,Raghavachari,N,Young,Balancing minimum spanning and shortest path trees,
Algorithmica,14:4(1995)305-321,
[58] D,Jungnickel,Graphs,Networks and Algorithms,(Algorithms and Computation in
Mathematics,Vol.5),Springer,1998。
§ 1.5 图的中心与重心
一、基本概念
设 G 是一个赋权图，每条边 v
i
v
j
上的权为 0
ij
w ≥,每个顶点
i
v 也有一个权 () 0
i
qv ≥ 。
(,)duv表示在考虑边赋权下图 G 中顶点 u 到 v 的距离。
图 G 的 半径 (radius)：
() ()
rad min max (,)
uVG vVG
Gdu
∈ ∈
= 。
图 G 的 直径 (diameter)：
() ()
max max (,) max{ (,) |,( )}
uVG vVG
diam G d u v d u v u v V G
∈∈
==?∈。
图中顶点 v 的 离心率 (eccentricity)：
()
() max () (,)
uVG
ev quduv
∈
= 。
图 G 的 中心 （ center）,图 G 中具有最小离心率的顶点。
图 G 的 重心 （ barycenter,）,,设
()
() () (,)
uVG
gv quduv
∈
=
∑
，使 g(v)达到最小的顶点称为图 G
26
的重心。重心也称为中位点（ median） 。
注,（ 1）一个图的中心一般不唯一，重心一般也不唯一；中心和重心未必相同。
（ 2）对于顶点无赋权的图，可将每个顶点的权看作 1,即得到离心率、中心、重心的相应定义。此时，图的半径
()
rad min ( )
vVG
Gev
∈
=,图的直径
()
diam max ( )
vVG
Gev
∈
= 。进一步地，如果图的边也无赋权，则将每条边上的权视为 1,便得到半径、直径、离心率、中心、重心的相应定义。此时，距离 (,)duv实际上是在边非赋权情况下顶点 u 到 v 的距离。
例 1.5.1 求如下非赋权图 G 的半径、直径、所有的中心、重心以及点 v
10
的离心率。
解,按定义求得，中心集合为 v
3
和 v
4
，半径 rad (G) = 4，直径 diam (G) =7，离心率 e(v
10
)=5.。
重心 v
3
，因为 g(v
3
)=30 是所有 g(v)中最小的。
二、求图的中心和重心的算法
根据中心和重心的定义不难得出如下算法。
1．求中心的算法
算法1,求图 G 的中心
第 1 步 利用最短路算法求出 G 中所有顶点间的距离。
第 2 步 对 G 的每个顶点 v，计算离心率
()
() max () (,)
uVG
ev quduv
∈
= 。
第 3 步 比较各顶点的离心率，求出离心率最小的顶点。
第 4 步 结束。
该算法可以通过距离矩阵实现。
算法 2,求图 G 的中心(距离矩阵形式)
第 1 步 利用最短路算法求出 G 中所有顶点间的距离，并组成距离矩阵 ()
ij
Dd=,其元素
d
ij
是图 G 中顶点 v
i
与顶点 v
j
间的距离,,1,2,,ij υ= null 。
第 2 步 对 j=1,2,···,υ,给矩阵 D 的第 j 列乘以 ()
j
qv ； 并求出所得矩阵每一行的最大元素：
()
i
ev,1,2,,i υ= null 。
第 3 步 比较所有 ()
i
ev,（ 1,2,,i υ= null ）,其中最小者所在的行对应的顶点即为 G 的中心。
第 4 步 结束。
上述算法的正确性是显然的。如果第 1 步中求距离使用 Floyd 最短路算法，则上述算法的时间复杂度为 O(n
3
),
2．求重心的算法
v
5
v
11
v
8
v
9
v
10
v
12
v
6
v
7
v
1
v
2
v
3
v
4
v
13
v
14
27
算法1,求图 G 的重心
第 1 步 利用最短路算法求出 G 中所有顶点间的距离。
第2步 对 G 的每个顶点 v，计算
()
() () (,)
uVG
gv quduv
∈
=
∑
。
第 3 步 比较各顶点的 ()gv值，求出使 ()gv达到最小的顶点。
第 4 步 结束。
算法2,求图 G 的重心(距离矩阵形式)
第 1 步 利用最短路算法求出 G 中所有顶点间的距离，并组成距离矩阵 ()
ij
Dd=,其元素
d
ij
是图 G 中顶点 v
i
与顶点 v
j
间的距离,,1,2,,ij υ= null 。
第 2 步 对 j=1,2,···,υ,给矩阵 D 的第 j 列乘以 ()
j
qv ；并求出所得矩阵各行和行和：
1
() ( )
ijij
j
gv qv d
υ
=
=
∑
,1,2,,i υ= null 。
第 3 步 比较所有行和 ()
i
gv,（ 1,2,,i υ= null ）,其中最小者所在的行对应的顶点即为 G 的中心。
第 4 步 结束。
该算法的正确性也是显然的。如果第 1 步中求距离使用 Floyd 最短路算法，则上述算法的时间复杂度为 O(n
3
),
例 1.5.2 设某市有 7 个化工厂，已知这些工厂间的公路及距离（公里）如图所示。现拟建一个消防队负责这些工厂的消防工作。问消防队应设在哪个工厂，以便任一个工厂失火时都能及时赶去灭火？
解,为了使消防队能在最短时间赶到任一个工厂灭火,需要消防队离最远点的距离尽可能短。
因此这是一个确定图的中心的问题。此例中图的顶点无赋权，故可将所有顶点的权视为 1。
利用最短路算法求得图 G 的距离矩阵为
0 3 5 9.3 6.3 4.5 6
3 0 2 6.3 3.3 1.5 3
520522.54
9.3 6.3 5 0 3 4.8 6.3
6.3 3.3 2 3 0 1.8 3.3
4.5 1.5 2.5 4.8 1.8 0 1.5
6 3 4 6.3 3.3 1.5 0
D
=
求得 D 的各行最大元分别为 9.3,6.3,5,9.3,6.3,4.8,6.3，其最小者为 4.8，对应于第 6 行，故中心为 v
6
，因此应将消防队设在 v
6
处。
v
5
2
v
6
v
7
v
1
v
2
v
3
v
4
3
2
6
3
2.5
1.8
1.5
1.5
28
例 1.5.3 设某能源集团有若干煤矿，集团打算在这些矿点之一建一个火力发电厂。已知这些煤矿间的道路连接及距离（公里）如图所示，各煤矿每年可供应给该电厂的原煤预计产量
（万吨）为（ 0.5,1.08,0.7,1,1.3,0.3,0.6） 。问发电厂应建在哪个矿点，才能使发电厂每年的原煤运费最省？
解,这是一个确定图的重心的问题。利用最短路算法求得图 G 的距离矩阵为
0 305093634560
30 0 20 63 33 15 30
50 20 0 50 20 25 40
93 63 50 0 30 48 63
63 33 20 30 0 18 33
45 15 25 48 18 0 15
60 30 40 63 33 15 0
D
=
各列分别乘以相应顶点的产量，得
1
0 32.4 35 93 81.9 13.5 36
15 0 14 63 42.9 4.5 18
25 21.6 0 50 26 7.5 24
46.5 68.04 35 0 39 14.4 37.8
31.5 35.64 14 30 0 5.4 19.8
22.5 16.2 17.5 48 23.4 0 9
30 32.4 28 63 42.9 4.5 0
D
=
D
1
的行和依次为,291.8,157.4,154.1,240.74,136.34,136.6,200.8，其最小者为 136.34，
对应于第 5 行，故中心为 v
5
，因此发电厂应设在 v
5
处，每年原煤总运费为 136.34 万吨公里乘以单位运价。
三、树的中心和重心
本部分我们对顶点和边均无赋权的树讨论其中心和重心。 在这种情况下树 T 中顶点的离心率为
()
() max (,)
uVT
ev duv
∈
=,树的中心是具有最小离心率的顶点，而树的重心是使
()
() (,)
uVT
gv duv
∈
=
∑
达到最小的顶点。
定理 1.5.1(Jordan,1869) 一棵树要么只有一个中心，要么有两个相邻的中心。
证明,当 2υ ≤ 时，结论显然成立。
设结论对所有 kυ ≤ 的树都成立。我们来证明结论对 1kυ = + 的树也成立。
v
5
20
v
6
v
7
v
1
v
2
v
3
v
4
30
20
60
30
25
18
15
15
29
设树 T 是一棵顶点数 12kυ =+>的树。由于 () 2Tυ >,故 T 的中心不会是叶子（ 1
度顶点） 。设
T
V′是 T 的所有叶子的集合，则删去 T 的所有叶子所得之图
T
TTV′′=? 仍是树。
我们来证明 T′与 T 具有相同的中心。
首先因 () 2Tυ >,故 T 的顶点不全是 1 度的，因而 ()VT′ 非空。对 ()uVT′? ∈,必有
()uVT∈ 。 设 v
是 T 中到 u 距离最远的顶点,即
()
(,) max (,) ()
TT
vVT
duv duv eu
∈
==，（ ()
T
eu
表示 u 在 T 中的离心率）,则 v
必是 T 的叶子（否则 u 到 v
的最短路通过 v
仍可延伸,v
不会是到 u 的最远点） 。由于 T′是由 T 删去所有叶子顶点后形成的，上述结论表明 T′中每个顶点的离心率比 T 中减少 1，即
() () 1,( )
TT
eu eu uVT
′
′=∈ 。
可见 ()uVT
′∈ 使
()
() min ()
TT
uVT
eu eu
′′
′∈
= 当且仅当
()
() min ()
TT
uVT
eu eu
∈
=,因此 T′与 T 具有相同的中心。
由于 ()Tkυ ′ ≤,按照归纳假设,T′要么只有一个中心，要么有两个相邻的中心。因此
T 也只有一个中心或有两个相邻的中心。归纳法完成，证毕。
对树的重心有类似的结论。
定理 1.5.2(Jordan,1869) 一棵树要么只有一个重心，要么有两个相邻的重心。
证明留作习题。
设 T 是一棵树。对 T 中任一个顶点 u，若 ()du k=,则 T 可分解成由 u 出发的 k 个分支（每个分支都含有 u 作为其一个叶子）,其中具有最多边数的那个分支中所含的边数，称为顶点 u 的 分支权,记为 ()qu
定理 1.5.3 设 T 是一棵树,uT∈ 。 u 是 T 的重心当且仅当 u 是 T 中具有最小分支权的顶点，
即
()
() min ()
vVT
qu qv
∈
= 。
证明：按定义，树的重心是使
()
() (,)
uVT
gv duv
∈
=
∑
达到最小的顶点。我们只需证明，对
()vVT?∈,() ()gu gv≤ 当且仅当 () ()qu qv≤ 。
事实上，由于 T 是树，故 u,v 两点间仅有唯一一条路相连，记此路为 P。假定从 u 出发不含 v 的分支有 k 个，分别为 J
1
+u,J
2
+u,···,J
k
+u；从 v 出发不含 u 的分支有 r 个，分别为 H
1
+v,H
2
+v,···,H
r
+v,并设
12 k
JJ J J= ∪∪null∪ 共含有 n
1
个顶点，
12 r
HH H H= ∪∪null∪
共含有 n
2
个顶点；
P
u
v
J
1
J
k
J
2
H
1
H
r
H
2
30
则显然
()
() (,)
xVT
gu dxu
∈
=
∑
＝
()
(,)
xV J
dxu
∈
∑
+
2
()
(,) (,)
yVH
dyv nduv
∈
+
∑
,
()
() (,)
xVT
gv dxv
∈
=
∑
＝
()
(,)
xV J
dxu
∈
∑
+
1
()
(,) (,)
yVH
dyv nduv
∈
+
∑
。
由此可见,
若 () ()gu gv≤,则
21
nn≤,此时 v 出发的最大分支必定是含 x 的那个分支，因而
() ()qu qv≤ 。
反之，若 () ()qu qv≤,我们分两种情况来证明 () ()gu gv≤ 。
（ 1）如果 u 的最大分支是不含 v 的某个分支，无妨设为 J
1
＋ u。则显然
11
()nJυ≥≥u 的含有 v 的那个分支的顶点数 ─1
2
n>,从而 () ()gu gv≤ 。
（ 2）如果 u 的最大分支是含 v 的那个分支，则 v 的最大分支必是含 u 的分支（若不然，假定 v 的最大分支是 H
i
，则 ()qu =u 的含 v 的分支所含点数－ 1
1
() ()Hqvυ>=，与前提条件
矛盾） 。但此时,
()qu =
12
() ( ) ( ) ()
r
PH H Pnε υυε+ ++ = +null
()qv =
11
() ( ) ( ) ()
k
PJ J Pnε + ++ = +null
因 () ()qu qv≤,故
21
nn≤,从而 () ()gu gv≤ 。证毕。
这个定理的结论使我们能够较容易地确定树的重心。实际上，该充分必要条件往往作为树的重心的另一种定义。一些著作中将这样定义的重心称为树的形心（ centroid） 。
值得一提的是，树的中心和重心未必重合，例如下图中所示的树的中心为 v，而重心为
w。这也说明一般情况下，图的中心和重心未必重合。
还需指出，树 T 中所有顶点对的距离之和
,()
() (,)
uv V T
WT duv
∈
=
∑
称为该树的 Wiener 指数，它是树的一个重要参数，在化学和通信理论中有重要的应用，读者可参看文献,
[59] A.A,Dobrynin,R,Entringer,and I,Gutman,Wiener Index of trees,theory and applications,
Acta Applicandae Mathematicae,66(2001) 211-249,
[60] M,Diudea,I.Gutman,and L.Jantschi,Molecular Topology,Nova Publishers,Huntington,
New York,2001,
[61] I,Gutman,E,Estrada,and O,Ivanciuc,Some properties of the Weiner polynomial of trees,
Graph Theory Notes of New York,36(1999) 7-13,
[62] J,Rada,Variation of the Wiener index under tree transformations,Discrete Applied
Mathematics,148(2005),135-146,
[63] J,Rada,and C,Uzcátehui,Randi? ordering of chemical tree,Discrete Applied Mathematics,
150(2005),232-250,
[64] M,Fischermann,A,Hoffmann,D,Rautenbach,L,Székely and L,Volkmann,Wiener index
versus maximum degree in trees,Discrete Applied Mathematics,122(2002),127-137,
v w
31
[65] W.C,Shiu,P.C,Bor Lam,and K.K,Poon,On Wiener numbers of polygonal nets,122(2002),
251-261,
图的中心和重心属于图论和网络最优化的一个研究专题－选址问题（ location problem）
的研究范畴，实际应用中常见的 k 中心问题,k 重心问题，以及各种限制条件下求中心和重心的问题，都属于这一研究方向。在这一研究专题上已有丰富的研究成果，有兴趣的读者可查阅参考文献 [66~73]。
[66] Nicos Christofides,Graph theory –an algorithmic approach,Academic Press,INC.,1990,
[67] Z.Drezner,Facility location-a survey of applications and methods,Springer Ser,Oper,Res.,
Springer,New York,1995,
[68] G.Y.Handler,P.B,Mirchandani,Location in networks,theory and algorithms,MIT Press,
Massachusetts,1979,
[69] R.F.Love,Facility location –models and methods,North-Holland,1988,
[70] P.B,Mirchandani,R.L.Francis,Discrete location theory,John Wiley & Sons,Inc.,New York,
1990,
[71] J,Bar-Ilan et al,How to allocate network center,J,Algorithms,15(1993)385-415,
[72] J,Plesnik,A heuristic for the p-center problem in graphs,Discrete Applied Math.,
17(1987)262-268,
[73] S,Guha,S,Khuller,Connected facility location problems,in Network Design,connectivity
and facilities location (P.M,Pardalos and Ding-zhu Du eds.),DIMACS Series in Discrete
Mathematics and Theoretical Computer Science,Vol.40,(1998) 179-190
§ 1.6 图的矩阵表示
设图 G=(V,E)，其中
12
{,,,}Vvv v
υ
= null,
12
{,,,}Eee e
ε
= null 。定义 G 的关联矩阵和邻接矩阵如下,
（ 1）关联矩阵
=)(GM
12
111 12 1
221 2 2
12
ee e
vm m m
vm m m
vm m m
ε
ε
ε
υ υυ υε
null
null
null
nullnull nullnullnull
null
,
其中
ij
m 表示顶点
i
v 与边
j
e 关联的次数。
（ 2）邻接矩阵
=)(GA
12
111 12 1
221 2 2
12
vv v
va a a
va a a
va a a
υ
υ
υ
υ υυ υ
null
null
null
nullnullnullnullnull
null
,
32
其中
ij
a 表示顶点
i
v 与
j
v 相邻的次数。
例 1.6.1 求下图的关联矩阵和邻接矩阵。
解,
=
0211000
1001100
0000111
1010011
)(GM,
=
1101
1011
0102
1120
)(GA 。
通过观察容易看出，图 G 的关联矩阵 M(G)和邻接矩阵 A(G)有如下特点,
（ 1） M(G)的元素是 0,1 或 2，其中元素 2 是由环边导致的； A(G)的元素也是 0,1 或 2，
其中 2 是由重边导致的（若两点间有多于两条重边，则会出现大于 2 的元素） 。如果图 G 是简单图，则关联矩阵 M(G)和邻接矩阵 A(G)中只有元素 0 和 1。
（ 2）邻接矩阵 A(G)是对称矩阵。
（ 3） M(G)中每列之和＝ 2； M(G)中第 i 行之和＝ v
i
的度；
若 G 中无环边，则 A(G)的主对角线元素全为 0，且 A(G)中第 i 行（列）之和＝ v
i
的度。
定理 1.6.1 设 A 是 υ阶图 G 的邻接矩阵，则 A
n
的第 i 行第 j 列元素
()n
ij
a 等于 G 中从 v
i
到 v
j
的长度为 n 的路的数目,(1 n υ≤<)。
证明：对 n 作数学归纳法。
n=1 时,A 的第 i 行第 j 列元素
(1)
ij ij
aa= 表示顶点 v
i
到 v
j
的边数，即 v
i
到 v
j
的长度为 1
的路的数目，结论成立。
假设 n = k 时结论成立，即 A
k
的第 i 行第 j 列元素
()k
ij
a 等于 G 中从 v
i
到 v
j
的长度为 k 的路的数目。
当 n = k +1 时,A
n
= A
k+1
=AA
k
，故
() ( 1) ()
1
nk k
ij ij ir rj
r
aa aa
υ
+
=
==
∑
。
由于
ir
a 是 G 中顶点 v
i
到 v
r
的长度为 1 的路的数目，
()k
rj
a 是 G 中顶点 v
r
到 v
j
的长度为 k 的路的数目，故
()k
ir rj
aa 是 G 中从顶点 v
i
经过 v
r
到 v
j
的长度为 k+1 的路的数目，因而
()
1
k
ir rj
r
aa
υ
=
∑
是 G 中从顶点 v
i
到 v
j
的长度为 k+1 的路的总数，可见定理结论对 n = k +1 成立。
归纳法完成。
推论 1.6.1 设 A 是图 G 的邻接矩阵，则
（ 1） A
2
的对角线元素
(2)
ii
a 是 G 中顶点 v
i
的度数；
e
1
e
2
e
3
e
4
e
5
e
6
e
7
v
1 v2
v
4
v
3
33
（ 2） A
3
的对角线元素
(3)
ii
a 是 G 中含顶点 v
i
的三角形的数目的两倍；
（ 3）若 G 是连通图，则 G 中任二相异点 v
i
与 v
j
间的距离等于使 A
n
的元素
()
0
n
ij
a ≠ 的最小的整数 n。
推论 1.6.2 图 G 中三角形的数目等于 A
3
的迹除以 6。
推论 1.6.3 设 A 是 υ阶图 G 的邻接矩阵，
2
()
k
ij
AA A r+++=null,则 r
ij
就是 G 中从顶点
v
i
到 v
j
的长度不超过 k 的路的数目。
以上推论由读者自行给出证明。
推论 1.6.4 设 A 是 υ阶图 G 的邻接矩阵 (3)υ ≥,
21
R AA A
υ?
= +++null,则图 G 连通的充分必要条件是矩阵 R 中每个元素均不为零。
证明：设
() ()
(),( ),()
kk
ij ij ij
A aA a Rr===。
必要性：设 G 是连通图，则 G 中任二顶点 v
i
与 v
j
之间都有路相连，取一条 (v
i
,v
j
)路，设其长度为 k（显然 11k υ≤≤?）,则
()
1
k
ij
a ≥,故由 R 的定义，
()
1
k
ij ij
ra≥≥；而对
{1,2,,}i υ?∈ null,因 G 连通且 3υ ≥,故
(2)
() 1
ii ii i
ra dv≥= ≥。可见 R 中没有零元素。
充分性：设 v
i
与 v
j
是 G 中任二相异顶点。因
(2) ( 1)
0
ij ij ij ij
raa a
υ?
= +++ ≠null,故必有某
()
0
k
ij
a ≠ 。因此在 G 中有至少一条长为 k 的 (v
i
,v
j
)路，由此可见 G 是连通图。
推论 1.6.5 设 A 是图 G 的邻接矩阵，
2 k
k
R AA A= +++null,则 G 的顶点 v
i
的离心率 e(v
i
)
等于使得矩阵 R
k
的第 i 行没有零元素的最小 k 值。
推论 1.6.6 设 A 是连通图 G 的邻接矩阵，
2 k
k
R AA A= +++null,则 G 的半径 rad(G)等于使得矩阵 R
k
中至少有一行没有零元素的最小 k 值。
推论 1.6.7 设 A 是连通图 G 的邻接矩阵，
2 k
k
R AA A= +++null,则 G 的直径 D(G)等于使得矩阵 R
k
中没有零元素的最小 k 值。
这三个推论的证明留给读者。
推论 1.6.6 不仅给出了求图的半径的方法，同时也给出了求无赋权图的中心的方法：在依次计算
12 1
,,R RR
υ?
null 的过程中，当遇到某个 k 对应的 R
k
中至少有一行没有零元素时，非零行对应的顶点即为图的中心。
图在计算机上处理时，可以以关联矩阵或邻接矩阵的形式存于计算机中。因邻接矩阵比关联矩阵小且又是对称矩阵，故在计算机存储时通常使用邻接矩阵的上三角部分。
图论与网络流理论
（ 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 是 V 中元素组成的某些无序对的集合，称为 边集 。
例 1.1.1 ),( EVG =,其中
},,,,{
54321
vvvvvV =,)},(),,(),,(),,(),,(),,(),,{(
55515153433221
vvvvvvvvvvvvvvE = 。
这便定义出一个图。
图的顶点集中的元素称为顶点，边集中的元素称为边。在本书中边 e = (u,v) 也常写为
e = uv，顶点 u 和 v 称为边 e 的端点，反过来也称边 e 连接顶点 u 和 v。图 G 的顶点数目 ||V
称为图 G 的阶，边的数目 ||E 称为图 G 的边数。本书中一般将图的边数记为 ε,将图的阶记为 υ。
2,图的图示
通常,图的顶点可用平面上的一个点来表示,边可用平面上的线段来表示 （直的或曲的） 。
这样画出的平面图形称为图的图示。
例如，例 1.1.1 中图的一个图示为
注,（ 1）由于表示顶点的平面点的位置的任意性，同一个图可以画出形状迥异的很多图示。
比如下图是例 1.1.1 中图的另一个图示,
（ 2）图的图示直观易懂，因此以后一般说到一个图，我们总是画出它的一个图示来表示。
3,一些术语和概念
设 G = (V,E)是一个图，下述概念中顶点均取自 V，边均取自 E。
（ 1） 点与边的关联 (incident)：如果在图 G 中点 v 是边 e 的一个端点，则称点 v 与边 e 在图 G 中相关联。
（ 2） 点与点的相邻 (adjacent)：如果图上两点 u,v 被同一条边相连，则称 u,v 在图 G 中相
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
邻。
（ 3） 边与边的相邻,如果图 G 中两条边有至少一个公共端点，则称这两条边在图 G 中相邻。
（ 4） 环边 (loop)：图中两端点重合的边称为环边。
（ 5） 重边 (multiedge)：设 u 和 v 是图 G 的顶点，图 G 中连接 u 和 v 的两条或两条以上的边称为图 G 中 u,v 间的重边。
（ 6） 简单图 (simple graph)：既无环边也无重边的图称为简单图。
（ 7） 完全图 (complete graph)：任意两点间都有一条边的简单图称为完全图,n 阶完全图记为 K
n
,
（ 8） 平凡图(trivial graph),只有一个顶点，没有边的图。
（ 9） 空图 (empty graph),边集为空的图。
（ 10） 零图 (null graph),顶点集为空的图。
（ 11） 顶点 v 的度 (degree)：图 G 中顶点 v 所关联的边的数目（环边计两次）称为顶点 v 的度，记为 d
G
(v)或 d(v)。
（ 12） 图 G 的最大度,)}(|)(max{)( GVvvdG
G
∈=Δ ；
图 G 的最小度,)}(|)(min{)( GVvvdG
G
∈=δ 。
（ 13） 正则图 (regular graph)：每个顶点的度都相等的图。
（ 14） 图的补图 (complement),设 G 是一个图,以 )(GV 为顶点集,以 )}(),(|),{( GEyxyx?
为边集的图称为 G 的补图，记为 G 。
定理 1.1.1 对任何图 G，都有
()
() 2
vVG
dv ε
∈
=
∑
。
证明,按每个顶点的度来计数边，每条边恰数了两次。
推论 1.1.1 任何图中，奇度顶点的个数总是偶数（包括 0） 。
证明留作练习。
4,子图
子图 (subgraph)：对图 G 和 H，如果 )()( GVHV? 且 )()( GEHE?,则称图 H 是图 G 的子图，记为 GH? 。
生成子图 (spanning subgraph),若 H 是 G 的子图且 () ()VH VG=,则称 H 是 G 的生成子图。
点导出子图 (induced subgraph)：设 G 是一个图,)(GVV?′ 。以 V′为顶点集，以 G 中两端点均属于 V′的所有边作为边集所组成的子图，称为 G 的由顶点集 V′导出的子图，简称为 G
的点导出子图，记为 ][VG ′,
边导出子图 (edge-induced subgraph)：设 G 是一个图,)(GEE?′ 。以 E′为边集，以 E′中边的所有端点作为顶点集所组成的子图，称为 G 的由边集 E′导出的子图，简称为 G 的边导出子图，记为 ][EG ′ 。
5
设 )(GVV?′,)(GEE?′,今后经常用 G V′? 表示从图 G 中删除顶点子集 V′（连同它们关联的边一起删去）所获得的子图，用 G E′? 表示从图 G 中删除边子集 E′（但不删除它们的端点） 所获得的子图。 特别地,对顶点 v 和边 e,常用 G v? 表示 G{}v?,G e?
表示 {}Ge? 图 G 的一个顶点子集 E′。
5,路和圈
途径 (walk)：图 G 中一个点边交替出现的序列
kk
iiiiii
veevevw null
2110
= 称为图 G 的一条途径，
其中
0
i
v,
k
i
v 分别称为途径 w 的起点和终点,w 上其余顶点称为中途点。
迹 (trail)：图 G 中边不重复的途径称为迹。
路 (path)：图 G 中顶点不重复的迹称为路。
（注：简单图中的路可以完全用顶点来表示，
k
iii
vvvP null
10
= ）
闭途径( closed walk)：图 G 中起点和终点相同的途径称为闭途径。
闭迹 (closed trail)：图 G 中边不重复的闭途径称为闭迹，也称为回路（ circuit） 。
圈 (cycle)：中途点不重复的闭迹称为圈。
注,
（ 1）途径（闭途径）,迹（闭迹）,路（圈）上所含的边的数目称为它的 长度 。
（ 2）简单图 G 中长度为奇数和偶数的圈分别称为 奇圈 (odd cycle)和 偶圈 (even cycle)。
（ 3） 对任意 )(,GVyx ∈,从 x 到 y 的具有最小长度的路称为 x 到 y 的 最短路 （ shortest path）,
其长度称为 x 到 y 的 距离 (distance)，记为 ),( yxd
G
。
（ 4）简单图 G 中最短圈的长度称为图 G 的 围长 (girth)，最长圈的长度称为图 G 的 周长
(circumference)。
例 1.1.2 设 G 是一个简单图，若 2)( ≥Gδ,则 G 中必含有圈。
证明：设 G 中的最长路为
k
vvvP null
10
= 。因 2)(
0
≥vd,故存在与
1
v 相异的顶点 v 与
0
v 相邻。若 Pv?,则得到比 P 更长的路，这与 P 的取法矛盾。因此必定 Pv∈,从而 G 中有圈。证毕。
例 1.1.3 设 G 是简单图，若 3)( ≥Gδ,则 G 必有偶圈。
证明：设
k
vvvP null
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。
6
证明：由上例知,G 中有长分别为 1,1 ++ ji 和 2+?ij 的圈。若 1,1 ++ ji,2+?ij 三数有公因数 2>m,则 |( )mji?,于是 2|m,这是不可能的。因此 1,1 ++ ji,2+?ij
三数的公因数必不超过 2。从而各个圈长的最大公因数是 1 或 2。证毕。
6,二部图
二部图 (bipartite graph)：若图 G 的顶点集可划分为两个非空子集 X 和 Y，使得 G 的任一条边都有一个端点在 X 中，另一个端点在 Y 中，则称 G 为二部图（或偶图）,记为 G＝
),( EYX ∪,),( YX 称为 G 的一个顶点二划分。
完全二部图 (complete bipartite graph)：在二部图 ),( EYXG ∪= 中，若 X 的每个顶点与 Y
的每个顶点有边连接，则称 G 为完全二部图；若 mX =||,nY =||,则记此完全二部图为
nm
K
,
。
定理 1.1.2 一个图是二部图当且仅当它不含奇圈。
证明,必要性,设
010
vvvvC
k
null= 是二部图 ),( EYXG ∪= 的一个圈。无妨设 Xv ∈
0
，
由二部图的定义知,Yv ∈
1
,Xv ∈
2
,null,一般地,Xv
i
∈
2
,Yv
i
∈
+12
,（ null,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 是一个二部图。 证毕。
例 1.1.5 判断下列图是不是二部图。
Herschel 图 Peterson图
解,Herschel 图的一个顶点二划分如下,
7
可见 Herschel 图是一个二部图。
Peterson 图中含有奇圈，因此不是二部图。
7,连通性
图中两点的连通,如果在图 G 中 u,v 两点间有路相通，则称顶点 u,v 在图 G 中连通。
连通图 （ connected graph）,若图 G 中任二顶点都连通，则称图 G 是连通图。
图的连通分支 （ connected branch,component）,若图 G 的顶点集 V(G)可划分为若干非空子集
ω
VVV,,,
21
null,使得两顶点属于同一子集当且仅当它们在 G 中连通，则称每个子图 ][
i
VG 为图 G 的一个连通分支（ ω,,2,1 null=i ） 。
注,（ 1）图 G 的连通分支是 G 的一个极大连通子图。
（ 2）图 G 连通当且仅当 1＝ω 。
例 1.1.6 设有 2n 个电话交换台，每个台与至少 n 个台有直通线路，则该交换系统中任二台均可实现通话。
证明,构造图 G 如下：以交换台作为顶点，两顶点间连边当且仅当对应的两台间有直通线路。问题化为：已知图 G 有 2n 个顶点，且 nG ≥)(δ,求证 G 连通。
事实上，假如 G 不连通，则至少有一个连通分支的顶点数不超过 n。在此连通分支中，
顶点的度至多是 1?n 。这与 nG ≥)(δ 矛盾。证毕。
例 1.1.7 若图中只有两个奇度顶点，则它们必连通。
证明,用反证法。假如 u 与 v 不连通，则它们必分属于不同的连通分支。将每个分支看成一个图时，其中只有一个奇度顶点。这与推论 1.1.1 矛盾。证毕。
8,图的同构
我们已经知道，同一个图可以有不同形状的图示。反过来，两个不同的图也可以有形状相同的图示。比如,
易见
1
G 和
2
G 的顶点及边之间都一一对应，且连接关系完全相同，只是顶点和边的名称不同而已。这样的两个图称为是 同构的 (isomorphic)。
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
x
y y
y y
x
x
x
x
yy
8
从数学上看，同构的两个图，其顶点间可建立一一对应，边之间也能建立一一对应，且若一图的两点间有边，则在另一图中对应的两点间有对应的边。严格的数学定义如下。
定义 1.1.1 对两个图 ))(),(( GEGVG = 与 ))(),(( HEHVH =,如果存在两个一一映射,
)()(,HVGV →α,)()(,HEGE →β,
使得对任意 )(),( GEvue ∈=,都有 )())(),(( HEvu ∈αα 且 =)(eβ ))(),(( vu αα,则称图
G 与 H 同构，记为 HG? 。
图的同构关系是一种等价关系（即满足反身性、对称性、传递性）,这种等价关系将 υ阶图分成若干等价类，彼此同构的图属于同一类。同一个等价类中的图有相同的结构，差别仅在于顶点和边的名称不同。由于人们关心的是图的结构，因此，通常将同构图类中的所有图看成同一个图，而不在乎它们顶点和边的名称以及它们的图示画法。在图的图示中，不给顶点和边标定名称的图称为非标定图，否则称为标定图。非标定图实际上就是一个同构图类的代表。在不致误解的情况下，我们也往往不严格区分标定图与非标定图。
目前尚无简便的方法判别两个图是否同构，特别是当图的顶点数较大时，判断两个图是否同构是一件很困难的事情。
两图同构，首先它们的阶必须相等，边数必须相等；其次要有相同的环边、重边及圈的状态；还应保持顶点的度，即在同构映射下相对应的顶点必须有相同的度。这些都是两图同构的必要条件，可用来判断两图不同构。
为判定两图同构，一般要按定义构造出两图顶点间的一一映射，然后检验它是否保持邻接关系。有时也可根据图的特点使用特殊方法。
例 1.1.8 判断下列图是否同构
解,图 G
1
和 G
2
是同构的。事实上，定义它们顶点间的映射 f，分别将顶点 v
1
,v
2
,v
3
,v
4
,v
5
,v
6
映射到 u
1
,u
3
,u
5
,u
2
,u
4
,u
6
，显然这是 G
1
到 G
2
的一个一一映射，且容易验证它保持顶点间的相邻关系。
图 G
2
和 G
3
也是同构的。 事实上,定义它们顶点间的映射 g,分别将顶点 u
1
,u
2
,u
3
,u
4
,u
5
,
u
6
映射到 w
1
,w
2
,w
3
,w
4
,w
5
,w
6
，显然这是 G
2
到 G
3
的一个一一映射，且容易验证它保持顶点间的相邻关系。
图 G
3
和 G
4
不同构，因为 G
4
含有三角形（即子图 K
3
）,但 G
3
不含。
注,（ 1） G
1
,G
2
,G
3
的同构性还可以通过它们的二部图特性来证明。可以检验，它们都是完全二部图 K
3,3
。
（ 2）容易证明，两个图 G 和 H 同构当且仅当它们的补图 GH、同构。利用这一结论，
也可以较简便地判定 G
1
,G
2
,G
3
的同构性，事实上,G
1
,G
2
,G
3
的补图都是两个不相交的
C
3
（长为 3的圈）,因此同构。而 G
4
的补图是 C
6
，故 G
4
与前三个图不同构。
G
1
G
2
u
1
u
2
u
3
u
4
u
5
u
6
w
6
w
5
w
1
w
3
w
2
w
4
v
1
v
2
v
3
v
4
v
6
v
5
x
1
x
2
x
3
x
4
x
5
x
6
G
3
G
4
9
关于图的同构有两个猜想至今尚未解决。
猜想 1（ Ulam 重构猜想,1929）设 G 与 H 是两个图,
|V(G)| = |V(H)|,V(G) = {u
1
,u
2
,,u
n
},V(H)={v
1
,v
2
,,v
n
}。
若对 {1,2,,}in?∈ null,都有
ii
Gu Hv，则 GH? 。其中
i
Gv? 表示将 v
i
以及与 v
i
关联的边都从 G 中删除后所得之图，
i
Hv? 类似。
猜想 2 设 G 与 H 都是至少有四条边的图，若存在一一映射,() ()EG EH? →,使得对
()eEG?∈,都有 ()GeH e,则 GH? 。
有关图的重构问题的更多内容可参看,
[1] C.St.J.A,Nash-Williams,The reconstruction problem,in Selected Topics in Graph Theory (L,
W,Beineke and R.J,Wilson eds.),Academic Press,London,(1978) 205-236,
[2]W.T,Tutte,Graph Theory,Cambridge University Press,(2001) 115-124.(影印版：图论，机械工业出版社,2004),
§ 1.2 最短路问题
一、赋权图
给图 G 的每条边 e 赋以一个实数 w(e)，称为边 e 的 权 。每条边都赋有权的图称为 赋权图 。
权在不同的问题中会有不同的含义。例如交通网络中，权可能表示运费、里程或道路的造价等。
设 H 是赋权图 G 的一个子图,H 的权定义为 )(HW ＝
∑
∈ )(
)(
HEe
ew,特别地，对 G 中一条路 P，其权为 )(PW ＝
∑
∈ )(
)(
PEe
ew
。
二,最短路问题
最短路问题：给定赋权图 G 及 G 中两点 u,v，求 u 到 v 的具有最小权的路（称为 u 到 v
的最短路） 。
注,赋权图中路的权也称为路的长，最短 (u,v)路的长也称为 u,v 间的距离，记为 d(u,v)。
最短路问题是一个优化问题，属于网络优化和组合优化的范畴。对这种优化问题的解答一般是一个算法。最短路问题有很多算法，其中最基本的一个是 Dijkstra 算法。
三,Dijkstra 算法
1,算法思想
设赋权图 G 中所有边都具有非负权,Dijkstra 算法的目标是求出 G 中某个指定顶点
0
v 到其它所有点的最短路。它依据的基本原理是：若路
01 1kk
Pvv vv
= null 是从
0
v 到
k
v 的最短路，
则
01 1k
Pvv v
′= null 必是从
0
v 到
1k
v
的最短路。基于这一原理，算法由近及远地逐次求出
0
v
到其它各点的最短路。
10
下面通过例子说明具体做法。
图 1.1
（ 1）令
0
{}Sv=,\SVS=,求
0
v 到 S 中最近点的最短路。在当前的例子中，从 v
0
v
1
、
v
0
v
2
,v
0
v
3
中选一条最短的，结果获得 v
0
到 v
1
的最短路 v
0
v
1
。
（ 2）令
1
:{}SS v= ∪,,\SVS=,求
0
v 到 S 中最近点的最短路。这里“最近”是指
0
v 到 S
的直接连边、以及从
0
v 出发的已有最短路上的点（即 S 中除
0
v 外的点，当前只有
1
v ）通过最短路再添加上向 S 的连边所形成的路中最短的。即选取 S 中一点 v使得距离
00
,
(,) min{(,) ( )}
i
ii
vSvS
dv v dv v wvv
∈∈
=+。 (*)
在当前的例子中，从 v
0
v
2
,v
0
v
3
,v
0
v
1
v
2
,v
0
v
1
v
3
中选一条最短的，结果获得 v
0
到 v
3
的最短路
v
0
v
1
v
3
。
（ 3）令
3
:{}SS v= ∪,,\SVS=,求
0
v 到 S 中最近点的最短路。即选取 S 中一点 v使得
00
,
(,) min{(,) ( )}
i
ii
vSvS
dv v dv v wvv
∈∈
= + 。
当前应从 v
0
v
2
,v
0
v
1
v
2
,v
0
v
1
v
3
v
2
,v
0
v
1
v
3
v
4
中选一条最短的,结果获得 v
0
到 v
4
的最短路 v
0
v
1
v
3
v
4
。
（ 4）令
4
:{}SS v= ∪,,\SVS=,求
0
v 到 S 中最近点的最短路。即选取 S 中一点 v使得
00
,
(,) min{(,) ( )}
i
ii
vSvS
dv v dv v wvv
∈∈
= + 。
当前应从 v
0
v
2
,v
0
v
1
v
2
,v
0
v
1
v
3
v
2
,v
0
v
1
v
3
v
4
v
2
中选一条最短的，结果获得 v
0
到 v
2
的最短路 v
0
v
1
v
2
（或 v
0
v
1
v
3
v
4
v
2
） 。
一般地，若
01
{,,,}
k
Svv v= null 以及相应的最短路已找到，则可用 (*)式来选取 v，获得
0
v
到 v的最短路。
2．算法实现－标号法
在上述算法的过程中，每轮循环求
0
(,)dv v 时，都要对所有的点
i
vS∈ 计算
0
(,) ( )
ii
dv v wvv+ 且比较出一个最小的值，因而在算法循环过程中需要大量重复的路长计算和比较。为了避免这种重复计算,Dijkstra 算法采用标号方法来实现：算法执行中，给每个点 v 都附一个标号 l(v)，表示当前已经算出的从 v
0
到该点的最短路的长
0
(,)dv v。算法每轮循环都考虑修改点 v 的标号,如果通过此前刚刚进入 S 集合的点 v
i
到该点的连边不能获得更短的路，则该点保持原有标号 l(v)不变；否则，修改该点标号为 l(v),= l(v
i
) + w(v
i
v)，当前
v
0
到 v 的最短路应由 v
0
到 v
i
的最短路及边 v
i
v 构成。
1
v
0
v
1
v
2
v
3
v
4
5
8
1
2
2
6
4
11
标号法的基本原理是累进比较。初始时，
0
():0lv =,∞=:)(vl,（
0
vv≠ ）,
0
{}Sv=,
\SVS= 。然后算法逐步修改 S 中顶点的标号。第 i 步时，对 S 中每个 v，只对刚进入 S
的点 v
i
计算
0
(,) ( )
ii
dv v wvv+ （即 () ( )
ii
lv wvv+ ）,并与 ()lv进行比较，取其较小的一个作为的新标号，即 (),min{(),( ) ( )}
ii
lv lv lv wvv=+。因为对在
i
v 之前进入 S 的点
01 1
,,,
i
vv v
null,
0
(,) ( )
kk
dv v wvv+ （ k = 1,2,…,i?1）的值及其大小信息已含于 ()lv之中，
因此只需计算一个值
0
(,) ( )
ii
dv v wvv+,并将其与此前纪录的最短路的长 ()lv进行比较即可，而不必对所有的点
i
vS∈ 都重新计算
0
(,) ( )
ii
dv v wvv+ 且比较出一个最小的，从而避免了重复计算和比较。
按照算法过程，标号法实现算法主要包括两个过程,（ 1）修改各点的标号,（ 2）从 S 的所有点中取标号最小的一个点，放入 S 中。某个点被放入 S 集合后，它的标号成为永久标号，不再被修改。算法反复执行上述过程，直至所有顶点获得永久标号（被放入 S 中） 。
算法具体步骤如下,
Dijkstra 算法：求非负权图中 v
0
点到其余各点的最短路。
第 1 步,令
0
():0lv =,∞=:)(vl,（
0
vv≠ ）,
0
:{}Sv=,:\SVS=,0:=i 。
第 2 步,对每个 vS∈,令 (),min{(),( ) ( )}
ii
lv lv lv wvv=+。
取 *vS∈ 使得 (*) min{()}
vS
lv lv
∈
= 。 记 *
1i
vv
+
=,令
1
:{}
i
SS v
+
= ∪,:\SVS= 。
第 3 步,令 1,+= ii 。如果 1i υ=?,则停止；否则，转第 2 步。
3,算法正确性
定理 1.2.1 Dijkstra 算法结束时，对任一个顶点 v，其标号 l(v)恰是 v
0
到 v 的最短路的长。
证明：按照算法，顶点 v 的最终标号 l(v)是 v 进入集合 S 时的标号。假设 v 在算法第 i 次循环时进入集合 S，则
1i
vv
+
=,且 v 进入集合 S 后 {,,,,}
01 1ii
Svv vv
+
= null 。由于 l(v)是算法在前 i 次循环中逐次比较出的当前从 v
0
到 v 最短路的长,因此从 v
0
到 v 仅含 {,,,,}
01 1ii
vv vv
+
null
中点的任何路的长都不会小于 l(v)。任取图 G 中一条从 v
0
到 v 的路 P，如果 P 仅含
{,,,,}
01 1ii
vv vv
+
null 中的点，则如上所述,P 的长不会小于 l(v)；如果 P 含 {,,,,}
01 1ii
vv vv
+
null
之外的点，无妨设沿着 P 从 v
0
出发第一个不在 {,,,,}
01 1ii
vv vv
+
null 中的顶点是 v′。因在算法第 i 次循环时,v
i+1
进入 S 而 v′ 仍未进入 S，说明当前 l(v
i+1
)≤ l(v′ )。注意 v′ 只是 P 的中途点且图 G 中所有边的权都非负,而当前的 l(v′ )大于或等于 v
0
到 v′ 仅含 {,,,,}
01 1ii
vv vv
+
null 中点的最短路的长，故路 P 的长大于或等于 P 上 v
0
到 v′ 段的长（ ≥ l(v′ )）,从而 P 的长不会小于 l(v
i+1
)（即 l(v)） 。 证毕。
按照上述定理,Dijkstra 算法结束时，每个顶点的标号 l(v)表示 v
0
到该点的最短路的长。
此外，通过检查标号的来源点，可反向追踪得到 v
0
到各点的最短路。
4,算法有效性
对于一个图论算法，如果在任何图上施行这个算法所需要的基本计算量（比如加、减、
12
乘、除运算或比较、赋值等）都以图的顶点数 υ的一个函数为其上界，则称这个函数为该算法的计算复杂度或时间复杂度，一般简称为 复杂度 （ complexity） 。图的顶点数 υ称为图论问题的规模。人们总是希望利用计算机执行算法以解决人工难以计算的大规模问题，因此，对一个算法人们主要关心它在解决大规模问题时的计算量。对于图论算法，主要关心当图的顶点数 υ增大时，算法所需计算量的增加情况。如果一个算法的计算复杂度是规模 υ的指数函数，比如 2
υ
,!υ 等，则当问题的规模较大时，算法所需的计算量快速增大以至于无法接受，
这样的算法在解决大规模问题时实际上是无用的。当一个算法的计算复杂度是多项式函数时，算法的计算量随规模的增加其增幅较缓，人们认为一般是可以接受的。因此，一个具有多项式时间复杂度的算法称为是 有效算法 （ efficient algorithm）或 好算法 (good algorithm）,
有时直接称为多项式时间算法或 多项式算法 。对于多项式算法，影响其时间复杂度的主项是多项式的最高次项，因此人们在作算法分析时，主要关注其最高次项。一般地，如果一个算法的复杂度是
1
110
kk
aa aaυυ υ
+ ++ +null,则我们说它的计算复杂度是 ()
k
O υ,或是
()
k
O υ 阶的。利用这个记号，如果一个算法的复杂度是 2
υ
或 !υ,我们也可写为 O(2 )
υ
或
O( !)υ 。
按照复杂度的上述定义，如果一个算法是 ()
k
O υ 阶的，则它也是
1
()
k
O υ
+
阶的，甚至也是 O(2 )
υ
阶的。但实际上，人们在提到算法的复杂性时，总是指它的最低的阶。
下一定理表明 Dijkstra 算法是多项式算法。
定理 1.2.2 Dijkstra 算法的计算复杂度为 ()
2
O υ 。
证明,Dijkstra 算法的主要计算量在第 2 步。在第 i 次循环中，第 2 步第 1 式需要 1iυ次加法,1iυ次比较；第 2 式需要不超过 1iυ 次比较。 ( 0,1,,2i υ=?null )。从而 1υ?
次循环总的计算量不超过
2
0
3( 1)
i
i
ν
υ
=
=
∑
3( 1)
2
υ υ?
= ()
2
O υ 。
对一个需要用算法解决的问题，如果存在求解它的多项式算法，则这个问题称为 P 问题 (polynomial problem)。如果一个问题，当猜出其答案时可在多项式计算量内验证答案的正确性，则这个问题称为 NP 问题 (non-deterministic polynomial problem)。将所有 P 问题的集合记为 P，所有 NP 问题的集合记为 NP，是否 P=NP？这是计算机科学和组合最优化领域的一个重要未解难题。明显地 PNP?,但人们目前还不知道是否 PNP? 。 Cook(1970)发现
NP 问题中有一类问题，只要其中有一个问题是 P 问题，则所有 NP 问题全是 P 问题，即
P=NP。 这类问题称为 NP完全问题,简称为 NPC问题 (non-deterministic polynomial problem)。
遗憾的是，对目前已找到的成千上万个 NPC 问题，人们还未能证明其中任何一个是 P 问题。
图论中有许多问题属于 NPC 问题。有兴趣的读者可参阅下列文献。
[2] http://www.nada.kth.se/~viggo/problemlist/
[3] M,R,Garey & D,S,Johnson,Computers and Intractability? a guid to the theory of
NP-completeness,W,H,Freedman,San Francisco,1979,（中译本：张立昂等译，计算机和难解性— NP 完全性理论导引，科学出版社,1987） 。
[4] D.S,Hochbaum,Approximation algorithms for NP-hard problems,International Thomson
13
Publishing Company,1995,
[5] Ding-zhu Du and Ker-I Ko,Theory of Computational Complexity,John Wiley & Sons,INC.,
New York,2000,
[6] Feng Gao,Ding-zhu Du,Biao Gao,Peng-jun Wan,and P,M,Pardalos,Minimax problems in
combinatorial optimization,Minmax and Applications (eds,by Ding-zhu Du & P,M,Pardalos),
Kluwer Academic Publishers,1995,
[7] D.B.Shmoys,Computing near-optimal solutions to combinatorial optimization problems,
Combinatorial Optimization (W.Cook,L.Lovasz and P.Seymour eds.),DIMACS Series in Discrete
Mathematics and Theoretical Computer Science,Vol.20,(1995) 355-397,
[8] C.H,Papadimitriou & K,Steiglitz,Combinatorial Optimization,Algorithms and Complexity,
Prentice-Hall,Inc.,Englewood Cliffs,New Jersey,1982,
[9] A,Gibbons,Algorithmic graph theory,Cambridge,Cambridge University Press,1985,
[10] M,R,Garey & D,S,Johnson and L,Stockmeyer,Some simplified NP-complete graph
problems,Theoret,Comput,Sci.,I 237-267,1976,
[11] Cook S,The complexity of theorem-proving procedure,Conference Record of Third ACM
Symposium on Theory of Computing,1970,pp151-158,
[12] 王树禾，图论及其算法，中国科技大学出版社,1990。
[13] 谢政，网络算法与复杂性理论（第二版）,国防科技大学出版社,2003。
上述 Dijkstra 算法可以用列表的方式进行计算，下面举例说明。
考虑图 1.1 中的赋权图。首先将顶点 v
1
,v
2
,v
3
,v
4
作为一行。然后将起始点 v
0
放在表内第一行左首，将 v
0
到其余各点连边上的权（即标号 l(v
k
)）放在各顶点下方相应位置上。
从第一行数字中选取最小的一个，用方括号标记，并在斜杠下方标上 v
0
，当前找到 v
1
下方的数字最小。接着，将 v
1
放在表内第二行左首（表示 v
1
进入集合 S）,对每个尚未进入 S 的顶点 v
k
，将第一行方括号中的数字与边 v
1
v
k
上的权相加，并与第一行 v
k
下方的数字比较，
取较小的一个（即新标号 ():min{(),() ( )}
11kk k
lv lv lv wvv=+）放在第二行相应位置上。
从第二行数字中选取最小的一个，用方括号标记，当前找到 v
3
下方的数字最小。由于该数字 3 是通过 v
1
得来的（即 min{ ( ),( ) ( )}
31 13
lv lv wvv+
113
() ( ) 3lv wvv= +=）,故在该数字斜杠下方标上 v
1
。
同样，将 v
3
放在表内第三行左首（表示 v
3
进入集合 S）,对每个尚未进入 S 的顶点 v
k
，
S V v
1
v
2
v
3
v
4
v
0
[1]/v
0
8 4 ∞
v
1
6 [3]/v
1
∞
v
3
6 [5]/v
3
v
4
[6]/v
1
14
将第一行方括号中的数字与边 v
3
v
k
上的权相加，并与第二行 v
k
下方的数字比较，取较小的一个（即新标号 ():min{(),() ( )}
33kk k
lv lv lv wvv=+）放在第三行相应位置上。并从第三行数字中选取最小的一个，用方括号标记，当前找到 v
4
下方的数字最小。由于该数字 5 是通过 v
3
得来的（即 min{ ( ),( ) ( )}
43 34
lv lv wvv+
334
() ( ) 5lv wvv= +=）,故在该数字斜杠下方标上 v
3
。最后，将 v
4
放在表内第四行左首（表示 v
4
进入集合 S）,对尚未进入 S 的唯一顶点 v
2
，将第一行方括号中的数字与边 v
3
v
2
上的权相加，并与第三行 v
2
下方的数字比较，
取较小的一个（即新标号 ():min{(),() ( )}
22442
lv lv lv wvv=+）放在第四行相应位置上。
并从第四行数字中选取最小的一个，现在第四行只有 v
2
下方的数字 6，用方括号标记之,v
2
进入集合 S 。由于该数字 6 可看成是通过 v
2
的旧标号 l(v
2
) 得来的（即
min{ ( ),( ) ( )}
24 42
lv lv wvv+
2
() 6lv==）,旧标号 l(v
2
)又是在第二行通过 v
1
得来的，故在该数字斜杠下方标上 v
1
。至此，算法结束。从每个顶点 v
k
所在列的最后一个数字（方括号内的数字）可以得知 v
0
到 v
k
的最短路的长。比如,v
0
到 v
4
的最短路的长为 5。
由斜杠后的标识可反向追踪出最短路。比如找 v
0
到 v
4
的最短路：先从 v
4
列下方的标识找到 v
3
，再从 v
3
列下方的标识找到 v
1
，最后从 v
1
列下方的标识找到 v
0
，从而可知 v
0
到 v
4
的最短路为 v
0
v
1
v
3
v
4
。
Dijkstra 算法也可以通过矩阵形式来进行，其步骤为,
第 0 步,将赋权图 G 的权矩阵 (w
ij
)的第一列中所有元素全改为×，在第一行剩下的其他元素下面划一条横线。
第 1 步,在画横线的元素中找一个最小的 w
ki
，若 w
ki
=∞，则停止，从 v
0
到某些顶点没有路；
否则，把 w
ki
用方括号标记，并把第 i 列其他元素都改成×，然后给第 i 行中不是×的元素都加上 w
ki
，并在这些元素下面划一条横线，转第 2 步。
第 2 步,如果存在不含×的列，则转第 1 步；否则结束，方括号标记的元素 w
ij
表示从 v
0
到
v
j
的最短路的长，而从 v
0
到 v
j
的最短路由最短 (v
0
,v
i
)路与边 v
i
v
j
构成。
仍以图 1.1 为例，其权矩阵为
(w
ij
) =
01234
0
1
2
3
4
184
152
85 61
426 2
12
vvvvv
v
v
v
v
v
∞ ∞
∞ ∞
∞
∞
∞ ∞∞
184
152
85 61
426 2
12
∞∞
∞
∞
∞∞ ∞
184
52
561
26 2
12
×∞
×∞ ∞
×∞
×∞ ∞
[1] 8 4
63
61
62
12
× ∞
× ×∞
×× ∞
×× ∞
× ×∞
15
[1] 8
6[3]
1
95
1
××∞
×× ∞
×× ∞×
×× ×
×× × ∞
[1] 8
6[3]
9[5]
6
×××
×× ×
×× ∞× ×
×× ×
×× × ×
[1]
[6] [3]
[5]
× ×××
× ××
× ××××
×× × ×
× ××××
由最后一个矩阵的元素回溯便可获得 v
0
到各点的最短路。比如,v
4
的最短路的长为 5；
为找从 v
0
到 v
4
的最短路，从 v
4
所在列（最后一列）开始回溯，因该列非×元素在 v
3
行（第
4行）,v
3
列非×元素在 v
1
行（第 2 行）,而 v
1
列非×元素在 v
0
行（第 1 行）,故 v
0
到 v
4
的最短路为 v
0
v
1
v
3
v
4
。
上述最短路算法仅适用于求所有边的权均非负的途中的最短路。 在边允许有负权的图中求最短路，有 Ford 算法和 Floyd 算法。 Ford 算法用于求无负权圈的图中一点到其它各点的最短路； Floyd 算法用于求无负权圈的图中所有顶点对之间的最短路。这两个算法当然也可以用于所有边的权均为非负的图中。有兴趣的读者可参看文献 [14],[15],[16]。求图的前 k
条最短路的算法可参考 [16]。
[14] 谢政,网络算法与复杂性理论（第二版）,国防科技大学出版社,2003。
[15] 王朝瑞,图论（第三版）,北京理工大学出版社,2001。
[16] N,Christofides,Graph Theory–a algorithmic approach,Academic Press,INC.,1990,
此外,对分层图,也可用动态规划方法来求最短路。 动态规划源于多阶段最优决策过程，
它的基本思想是 Bellman 最优化原理。该原理可概括地描述为：如果图 G 中从 A 点到 C 点的最短路 P 经过点 B，则 P 上 B 到 C 的一段必定是该图中 B 点到 C 点的最短路。依据这个原理，可用一个基本的递推关系式使最优决策过程连续地转移。使用动态规划方法时，要从最终状态开始逐步递推到起始状态。例如，对下图求 A 到 H 的最短路。
该图的顶点从 A 到 F 分为 5 层，同层顶点间互不连边，隔层顶点间也没有连边，这便是分层图。我们从 H 点开始考虑。其前一层顶点 F 和 G 到 H 的最短路的长分别是 4 和 3，
记为 W(F)=4,W(G)=3。再考虑 F 和 G 的前一层顶点 D 和 E。从 D 出发有两种选择,DFH，
路长为 1+ W(F)=5； DGH，路长为 1+ W(G)=4；故从 D 到 H 的最短路为 DGH,W(D)=4。
同样可知，从 E 到 H 的最短路为 EGH,W(E)=5。再考虑 B,C。 B 到 H 可经过 D 也可经过
E，经 D 到 H 的最短路长为 6+W(D)=10，经 E 到 H 的最短路长为 6+W(E)=11，故从 B 到 H
的最短路应经过 D，且最短路长为 W(B)=10。同样可得，从 C 到 H 的最短路应经过 D，且最短路长为 W(C)=8。最后考虑顶点 A，它到 H 可经过 B 也可经过 C，经 B 到 H 的最短路长为 4+W(B)=14，经 C 到 H 的最短路长为 5+W(C)=13，故从 A 到 H 的最短路应经过 C，
且最短路长为 W(A)=13。因此获得 A 到 H 的最短路为 ACDGH。
A
B
C
D
E
F
G
H
4
5
6
6
7
4
4
2
1
1
2
3
16
在上述过程中，决定每层顶点的结果只需要做 4 次加法。如果将图扩展为 n 层，则计算量为 4(n?3)+2，这比 Dijkstra 算法的计算量低的多。由此可见，针对具体问题的特点可以设计出非常有效的算法。
关于最短路问题读者可进一步参阅文献,
[17] E,Dijkstra,A note on two problem in connection with graphs,Numer,Math.,1(1959)
269-271,
[18] L.R,Ford,Network flow theory,Rand Corporation Report,(1956) 923,
[19] R.W,Floyed,Algorithm 97- Shortest Path,Comm.,ACM,5(1962) 345,
[20] D,Bertsekas,A simple and fast label correcting algorithm for shortest paths,Networks,
23(1993) 703-709,
[21] M,Desrochers,and F,Soumis,a reoptimization algorithm for the shortest path problem with
time windows,Europaean Journal of Operational Research,35(1988) 242-254,
[22] M.Dror,Note on the complexity of the shortest path models for column generation,
Operations Research,42(1994) 977-978,
[23] G,Gallo,and S,Pallottino,Shortest path algorithms,Annals of Operations Research,7(1988)
73-79,
[24] F,Glover,R,Glover,and D,Klingman,The threshold shortest path algorithm,Networks,
14(1984) 25-36,
[25] W.B,Powell,Zhi-Long Chen,A generalized threshold algorithm for the shortest path problem
with time windows,in Network Design,Connectivity and Facilities Location (P.M,Pardalos and
Ding-zhu Du eds.),DIMACS Series in Discrete Mathematics and Theoretical Computer Science,
Vol.40,(1998) 303-318,
§ 1.3 树及其性质
不含圈的图称为 森林 (forest)，不含圈的连通图称为 树 （ 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）
17
若 G 有圈，则此圈上任二顶点间有两条不同的路，与前提条件矛盾。
下面用归纳法证明 1ε υ=?。
1υ = 时,0=ε,结论真。
假设 kυ ≤ 时结论真，我们来证明当 1kυ = + 时，也有 1ε υ=? 成立。
当 1kυ =+时，任取边 E( )uv G∈ 。考虑图 uvGG?=′,因 G 中 u,v 间只有一条路，
即边 uv，故 G′不连通且只有两个连通分支，设为
21
,GG 。注意到
21
,GG 分别都连通且任二顶点间只有一条路，由归纳法假设，
11
() ()1GGε υ=?,
22
() ()1GGε υ=? 。因此
12 1 2
() () ()1(()1)(()1)1 ()1GG G G G Gε εε υ υ υ= + +=?+?+=?。
归纳法完成。
（ 3）?（ 4）
用反证法。若 G 不连通，设
w
GGG,,,
21
null 是其连通分支（ 2≥w ）,则 1
ii
ε υ=?（因
i
G 是连通无圈图，由已证明的 (1) 和 (2) 知，对每个
i
G,（ 3 ）成立） 。这样，
11
ww
ii
ii
wwεευ υ
==
==?=?
∑∑
，这与 1ε υ=? 矛盾。
（ 4）?（ 5）
()()1 2Ge Gε ευ?=?=?，但每个连通图必满足 1ε υ≥?（见下列引理）,故图
eG? 不连通。
引理 若图 H 连通，则 () ()1HHε υ≥?。
证明：对 υ做数学归纳法。
1,2υ = 时,1ε υ≥?显然成立。
假设 kυ ≤ 的连通图都 1ε υ≥?。
对于 1kυ =+的连通图 H，任取 )(HVv∈,考虑 vH? 。
若 vH? 连通，则由归纳假设,()()11Hv Hv kε υ? ≥=?，而
() ( )1( 1)1( 1)1 ()1HHv k k Hε ευ≥? +≥? += +?=?。
若 vH? 不连通，设
w
HHH,,,
21
null 是其连通分支 ( 2≥w ) 。由归纳假设，
() ()1
ii
HHε υ≥?,( wi,,2,1 null= )。故
11
( ) () () ( )
ww
ii
ii
Hv H H w Hv wkwεευυ
==
= ≥?==?
∑∑
,
而 () ( ) ( ) ( 1)1 ()1HHvwkwwk Hε ευ≥?+≥?+=+?=?。
归纳法完成。
（ 5）?（ 6）
先证 G 中无圈：若 G 中有圈，删去圈上任一边仍连通，矛盾。
18
再证对任何 )(GEe∈,eG + 恰含一个圈：因 G 连通且已证 G 无圈，故 G 是树。由
（ 2）,任二不相邻顶点间都有一条路相连，故 eG + 中必有一个含有 e 的圈；另一方面，若
eG + 中有两个圈含有 e，则 ( eG + ) Ge =? 中仍含有一个圈，矛盾。
（ 6）?（ 1）
只需证 G 连通。任取 )(,GVvu ∈,若 u,v 相邻，则 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,则
1
() 2
i
i
dv
υ
υ
=
≥
∑
。但另一方面，
1
() 2 2( 1) 2 2
i
i
dv
υ
ευ υ
=
= =?=?
∑
。
这两方面矛盾。故 T 至少有一个 1 度顶点，设为 u。除此之外，其余 1υ? 个顶点的度数之和为 23υ? 。若这些点的度都大于或等于 2，则其度数之和 2( 1) 2 2υ υ≥?=?。这与
23υ? 矛盾。故除 u 之外 T 还至少有一个度为 1 的顶点。证毕。
§ 1.4 生成树与最小生成树
一、生成树（ spanning tree）
定义 1.4.1 设 T 是图 G 的一个子图，如果 T 是一棵树，且 () ()TGυ υ=,则称 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 ()1GT T Gε ευ υ≥≥?=?。证毕。
二、最小生成树问题
最小生成树问题,在赋权图 G 中，求权最小的生成树（简称为最小生成树） 。即：求 G 的一棵生成树 T，使得
∑
∈
=
Te
T
ewTw )(min)( 。
19
最小生成树问题是一个优化问题，需要设计优化算法寻找其最优解。求解最小生成树问题的算法较多，本节主要介绍 Kruskal 算法和 Prim 算法。
（一） Kruskal 算法 (Joseph Bernard Kruskal,1956)
1,算法思想,先从图 G 中找出权最小的一条边作为最小生成树的边，然后逐次从剩余边中选边添入最小生成树中，每次选边找出不与已选边构成圈的权最小的一条边。直至选出
(G) 1υ? 条边为止。
2,算法步骤,输入：赋权连通 υ阶图 G。输出,G 的最小生成树 T。
第一步 取 )(
1
GEe ∈ 使得 () min{ ()},
eG
we we
∈
= 令,1i = 。
第二步 取 },,,{\)(
211 ii
eeeGEe null∈
+
使得
(1) G[{
121
,,,,
+ii
eeee null }] 不含圈； (2)
1+i
e 是满足 (1)的权最小的边。
第三步 当 i+1 = ()1Gυ? 时,输出最小生成树 G[{
12 1
,,,ee e
υ?
null }]，算法停止 ; 否则,令
1,+= ii,转第二步。
3,算法正确性,
定理 1.4.2 设
12 ()1
,,,
G
ee e
υ?
null 是 Kruskal 算法获得的边,则边导出子图 G[{
12 ()1
,,,
G
ee e
υ?
null }]
是 G 的最小生成树。
证明：记
*
T = G[{
12 ()1
,,,
G
ee e
υ?
null }]。显然
*
T 无圈，因此
*
T 是森林。设它有 w 个连通分支，则 (T ) (T ) (T ) 1 ( (G) 1) 1 (G)wυε ε υ υ
=+≥+=?+=。
但
*
T 是 G 的子图，故
*
() ()TGυυ= 。于是
**
() ()1 ()1TG Tευ υ=?=?。
由定理 1.3.1 的 (3)，
*
T 是一棵树。又
*
() ()TGυυ=,从而是 G 的一棵生成树。
下证其最优性，用反证法。
假设
*
T 不是权最小的生成树 (下称最优树 )。对 G 的任一棵不同于
*
T 的生成树 T，记
12 1
() min{| {,,,}
i
f Tieee
υ?
=∈null 且 }Te
i
。
在Ｇ的所有最优树中选取一棵使 )(Tf 最大的，记为 T
~
。 (T
~
不会是
*
T,因假设
*
T 不是最优树 )。设 kTf =)
~
( 。由 )
~
(Tf 的定义，
121
,,,
k
eee null 既在
*
T 上也在 T
~
上，但
k
e 不在
T
~
上。因此
k
eT +
~
含有一个圈 C。 C 上必有一条边
*
Te
k
′ 。显然
kk
eeTT ′?+=′ )
~
( 也是一棵生成树，且 )()()
~
()(
kk
ewewTwTw ′?+=′ 。
按照算法，
k
e 是使 G[{
k
eee,,,
21
null }] 中无圈的边中权最小的。注意
G[{
kk
eeee ′
,,,,
121
null }] 是 T
~
的子图，也无圈。故由算法规则知：
)()(
kk
ewew ≥′
。由前式，
)
~
()( TwTw ≤′
,这说明
T′
也是最优树。 但
)
~
()( TfkTf =>′
（注意由于
121
,,,
k
eee null 在
*
T
上且
*
Te
k
′,故
12 1
{,,,}
kk
eee e
′? null
） 。这与
T
~
的取法矛盾。证毕。
4,Kruskal 算法的实现及其计算复杂度分析
20
Kruskal 算法的计算量主要在第二步。算法共需执行 1υ? 次第二步，在第 i 次执行第二步时，须比较集合
12
()\{,,,}
i
EG e e enull 中所有边的权以求得一条权最小的边，并检验该边是否与已有边构成圈，如果构成圈，还需再找新的最小权边，这是比较浪费的。
在实际应用 Kruskal 算法时，一般先将所有的边按权由小到大排序，这需要大约
2
logε ε
次比较（见 [26]） 。每次执行算法第二步时，不必再比较边的权，而是直接选取此前尚未考虑过的权最小的边，检验它是否与已有边构成圈即可。这样可省去许多次循环比较。
[26] D.E,Knuth,The art of computer programming,Vol.3,Sorting and Searching,
Addison-Wesley,Reading,Mass.,(1973)184,
接下来的问题是如何检验所选边是否与已有边构成圈。这可通过给顶点标号来实现。设算法在 i 次循环后选出的边集合为 E
i
。算法开始时，给所有顶点标不同的标号：顶点
k
v 标号为 k,（ 1,2,,k υ= null ） 。当算法执行第 i+1 次循环选出一边
1i
e
+
添加进 G[E
i
]形成 G[E
i+1
]
时,用该边两端点标号的较小者给这条边所连的 G[E
i+1
]的两个连通分支的顶点重新标号 （连通分支有可能仅由
1i
e
+
的一个端点组成） 。按这个标号方案，在任意一步中，两个顶点属于已选边形成的同一连通分支当且仅当它们有相同的标号。这意味着当我们考虑向 G[E
i
]添加某条边 e是否会形成圈时，只要检查 e的两个端点是否有相同的标号即可。如果有相同的标号，则抛弃该边（以后的循环中不再使用）,再检验权稍大些的下一个候选边；如果标号相异，则取 e 作为
1i
e
+
添加进 G[E
i
]。在这个过程中，对每条候选边只需做一次比较就能决定是否抛弃它。算法全过程至多需要 ε
(1)
2
υ υ?
≤ 次这样的比较。
当添加
1i
e
+
进入 G[E
i
]时，顶点重新标号最多需要 υ次比较，因此对 1υ? 条边最多需要
(1)υ υ? 次比较。
可见算法执行过程约需要 ε + (1)υ υ? 次计算。
由以上分析可得如下结论。
定理 1.4.3 若事先将顶点按权排序，则 Kruskal 算法的计算复杂度为
2
O( )υ ；若加上事先排序的计算量，则 Kruskal 算法的计算复杂度为
2
2
O( log )υ υ 。
证明,算法执行过程中需要的主要计算量为 ε + (1)υ υ?
(1)
2
υ υ?
≤ + (1)υ υ? =
3
(1)
2
υυ?,
事先排序需要的计算量为
2
logε ε
2
22
(1) (1)
log log
22
υ υυυ
υ υ
≤≤。故知定理结论成立。证毕。
例 1.4.1 欲建设一个连接 5 个城市的光纤通信网络。各城市间线路的造价如图所示，求一个使总造价最少的线路建设方案。
v
3
v
4
12
87
9
10
6
6
5
8.5
6.4
v
1
v
2
v
5
21
解,算法执行过程如下所示。
（二） Prim 算法 (Robert Clay Prim,1957)
1,算法思想,先从图 G 中找出权最小的一条边作为最小生成树的边,在算法任一轮循环中，
设已经选出的边导出的子图为 G′，从 G′的顶点向 G′以外顶点的连边为 E′，则选择 E′中权最小的边向 G′中添加，如此反复循环直至选出 (G) 1υ? 条边为止。
Prim 算法与 Kruskal 算法的根本区别在于,Kruskal 算法在保持无圈的基础上选边，而在保持连通的基础上选边。 Prim 算法的添边过程实际上是树的生长过程。 Kruskal 算法的添边过程一般情况下是森林合并为树的过程。
在一些文献中,Kruskal 算法也称为避圈法,Prim 算法也称为边割法。
2,算法步骤,输入：赋权连通 υ阶图 G。输出,G 的最小生成树 T。
step1,任取 )(
0
GVv ∈,令
00
{}Sv=,
00
()\SVGS=,,0i =,
0
E φ= 。
step2,求
i
S 到
i
S 间权最小的边
1i
e
+
，设
1i
e
+
的属于
i
S 的端点为
1i
v
+
，令
11
:{}
iii
SSv
++
= ∪,
11
\)(
++
=
ii
SGVS,
11
:{}
iii
EEe
++
= ∪
Step3,当 i+1= ()1Gυ? 时,输出最小生成树 G[E
i+1
]=G[{
12 1
,,,ee e
υ?
null }]，算法停止 ;
否则，令 1,+= ii,转 step2。
3,算法正确性,
定理 1.4.4 设
12 1
,,,ee e
υ?
null 是 Prim 算法获得的边，则边导出子图 G[{
12 1
,,,ee e
υ?
null }]是 G
的最小生成树。
证明：用
k
T 表示 Prim 算法第 k 次循环得到的边集所构成的子图，即
k
T = G[E
k
]=G[{
12
,,,
k
ee enull }],1,2,1k υ=?null 。
我们用归纳法来证明，对每个 k ( 1,2,1k υ=?null ),
k
T 必含于 G 的某个最小生成树中。
当 k=1 时，
1
T 仅由边
1
e 生成。注意到
1
e 是 G 中权最小的边，因此，对 G 的任一棵最小生成树 T
，若 T
不含有
1
e,则
1
Te
+ 有一个圈 C,C 上每条边的权都不小于
1
e 的权
1
()we 。设
e是 C上一条异于
1
e 的边,则
1
TTee
′=+?也是 G的一棵生成树,且其权
*
() ( )wT wT′ ≤ 。
可见 T′也是 G 的一棵最小生成树，并且含有边
1
e 。即
1
T 含于最小生成树 T′中。
假设 k = m 时（ 11m υ≤<?）,结论成立，即
m
T 含于 G 的某个最小生成树 T
*
中。考虑最后一条进入
112 1
[{,,,}]
mmm
TGeeee
++
= null 的边
1m
e
+
。 若
1m
e
+
在 T
*
中,则
11mmm
TTe
++
=+
含于最小生成树 T
*
中。若
1m
e
+
不在 T
*
中，则
1m
Te
+
+ 有一个圈 C。由于
11mmm
TTe
++
=+
v
3
v
4
12
87
9
10
6
6
5
8.5
6.4
v
1
v
2
v
5
v
3
v
4
12
8 7
9
10
6
6
5
8.5
6.4
v
1
v
2
v
5
v
3
v
4
12
8 7
9
10
6
6
5
8.5
6.4
v
1
v
2
v
5
v
3
v
4
12
87
9
10
6
6
5
8.5
6.4
v
1
v
2
v
5
22
无圈，故 C 上必有边属于 T
*
而不属于
m
T,但
m
T 是 T
*
的子图，故 C 上必可找到一条异于
1m
e
+
的边 euv=,使得
m
uT∈ 而
m
vT? 。由算法步骤知，权
1
() ( )
m
we we
+
≥ 。于是
1m
TTe e
+
′=+?也是 G 的一棵最小生成树，并且含有边
1m
e
+
。再注意到
m
T 的边全在 T
*
中，因此上述结论表明
11mmm
TTe
++
=+ 含于最小生成树 T′中。归纳法完成。证毕。
4,计算复杂度分析,
Prim 算法的主要计算量在第二步。在算法第 i 轮循环执行第二步时，
i
S 中有 i 个顶点，
i
S 中有 iυ? 个顶点，故
i
S 到
i
S 间最多有 ()iiυ? 条边。从这些边中选出一条权最小的边
1i
e
+
，需要 ()1iiυ次比较。算法需循环执行第二步 1υ? 次，因此总的计算量为
-1 -1
11
1
[ ( ) 1] ( ) ( 1)( +1)
6
ii
ii ii
υυ
υυ
==
≤?=?
∑∑
。
由此可见,Prim 算法的计算复杂度为
3
()O υ 。与 Kruskal 算法类似，使用顶点标号法可进一步降低 Prim 算法的计算复杂度。
（三） Prim 算法的标号形式―标号 Prim 算法
1,算法思想,给图的顶点赋以标号，该标号与边的权有关，在执行 Prim 算法的过程中，通过修改顶点标号和比较顶点的权，来选择满足 Prim 算法要求的最小权边。
顶点 v 的标号记为 ()lv 。用 ()wuv 表示边 euv= 的权，若,uv两点间没有边，则
()wuv =∞。
2,算法步骤,输入：赋权连通 ν 阶图 G。输出,G 的最小生成树 T。
step1,任取 )(
0
GVv ∈,令
000
() 0,(),( ),{}lv lv v v S v= =∞ ≠ =,
00
()\SVGS=,
00
Tv=,,0i = 。
step2,对 ()
Gi i
vNv S?∈ ∩,若 () ()
i
wvv lv<,则令 (),( )
i
lv wvv= 。
Step3,选取
1ii
vS
+
∈ 使得
1
()min()
i
i
vS
lv lv
+
∈
= 。设
11
,( )
ii i
euvuS
++
= ∈ 使得
11
()()
ii
we lv
++
=,
令
11
:{}
iii
SSv
++
= ∪,
11
\)(
++
=
ii
SGVS,
11
:{}
iii
TTe
++
= ∪ 。
Step4,当 i+1= 1)(?Gν 时,输出最小生成树
1
T
ν?
，算法停止 ; 否则，令 1,+= ii,转 step2。
3,算法正确性,
标号 Prim 算法是 Prim 算法的标号实现,因此由 Prim 算法的正确性即知标号 Prim 算法结束时必能得到图 G 的最小生成树。
4,计算复杂度分析,
算法的主要计算量在第 2 步和第 3 步。算法第一次执行 Step3 需做 n?2 次比较，第二次执行 Step3 需做 n?3 次比较,，因此执行 Step3 共需做
1
(2)(1)
2
υυ 次比较；同样，
执行 Step2 共需不超过
1
(2)(1)
2
υυ次比较。 于是标号 Prim 算法的时间复杂性为 O(υ
2
)。
标号 Prim 算法将 Prim 算法每次循环中比较
1i
S
+
到
1i
S
+
间所有边的权，改为修改
()
Gi i
Nv S∩ 中点的标号并比较
i
S 中点的标号，因此节省了计算量。
23
一些文献中将标号 Prim 算法称为 Dijkstra 最小生成树算法。
5,Prim 算法的矩阵实现―求最小树的权矩阵法
Prim 算法可以通过权矩阵来实现。给定一个赋权的连通 n 阶简单图 G，其各边上的权组成的 n 阶 ()
ij n n
Ww
×
= 称为 G 的权矩阵，其中元素
ij
w 定义如下,
(1),1,2,,
ii
wi n=∞ = null ； (2) 若边 ()
ij
vv E G∈,则 ()
ij i j
wwvv= ； (3)若边 ()
ij
vv E G?,
则
ij
w =∞。
算法步骤为,
Step0,划掉矩阵 W 的第一列（将 W 第一列元素全改为 ×）,并在第一行剩下的每个元素下面画一条横线。
Step1,在画横线的元素中找一个最小的元素
ki
w,并将其圈起来。然后把第 i 列其它元素全部划去（改为 ×）,并在第 i 行没有被划掉的元素下面画上横线。
Step2,若矩阵 W 的所有元素要么已被划去要么已被圈起来，则算法结束，圈起来的元素即对应于所求最小生成树的边。否则，转 Step1。
例 1.4.2 用权矩阵法求如下赋权图 G 的一棵最小生成树。
解：求解过程如下。
W=
20 30 25 50
20 40 30
30 40 10 20
25 30 10 15
50 20 15
∞
∞∞
∞
∞
∞∞
→
20 30 25 50
40 30
40 10 20
30 10 15
20 15
×
×∞ ∞
×∞
×∞ ∞
→
(20) 30 25 50
40 30
10 20
10 15
20 15
×
× ×∞
××∞
×× ∞
× ×∞
→
(20) 30 (25) 50
40
20
10 15
20
×
×× ×∞
××∞×
×× ×
×× ×∞
→
(20) (25) 50
20
(10) 15
××
×× × ×∞
×× × ×
×× ×
×× × ×∞
→
(20) (25)
(10) (15)
× ××
× ××××
× ××××
×× ×
× ××××
。
最后得到的最小生成树由边 v
1
v
2
,v
1
v
4
,v
4
v
3
,v
4
v
5
构成，其权为 20+25+10+15=70。
在实际应用中，往往需要求图的满足某种约束条件的最小生成树。这一类问题统称为约束最小生成树问题（ Constrained minimum spanning tree problems） 。常见的有顶点度约束最小生成树、直径约束最小生成树、边容量约束最小生成树、最多叶子最小生成树等，详细可参阅下列文献 [27]或 [28]~[42]。约束最小生成树问题大多数是 NPC 问题，因此对这些问题主要是设计好的近似算法。
20
30
25
10
30
40
20
50
15
v
1
v
2
v
3
v
4
v
5
24
约束最小生成树问题参考文献
[27] N,Deo and N,Kumar,Computation of constrained spanning trees,a unified approach,
Network Optimization (P.M.Pardalos,D.W.Hearn,and W.W.Hager eds.),Lecture Notes in
Economics and Mathematical Systems,450,Springer-Verlag,Berlin Heidelberg,1997,
[28] D,Kleitman and D.West,Spanning trees with many leaves,SIAM Journal on Discrete
Mathematics,4(1) (1991) 99-106,
[29] N,Deo and N,Kumar,Constrained spanning tree problems,approximate methods and
parallel computation,in Network Design,connectivity and facilities location (P.M,Pardalos and
Ding-zhu Du eds.),DIMACS Series in Discrete Mathematics and Theoretical Computer Science,
Vol.40,(1998) 191-216,
[30]A,Abdallah,N,Deo,N,Kumar,and T,Terry,Parallel computation of a diameter-constrained
MST and related problems,Technical Report CS-TR-97-04,Department of Computer Science,
University of Central Florida,Orlando,(1997),
[31] B,Boldon,N.Deo,and N,Kumar,Minimum-weight degree-constrained spanning tree
problem,heuristics and implementation on an SIMD parallel machine,Parallel Comput,
22(1996)369-382,
[32] G,Craig,M.Krishnamoorthy,and M.Palaniswami,Comparison of heuristic algorithms for the
degree constrained minimum spanning tree,In Meta-heuristics,Theory and Applications
(I.H.Osman and J.P.Kelly eds.),(1996)83-96,
[33] N,Kumar,Parallel computation of constrained spanning trees,heuristics and SIMD
implementations,Ph.D,Dissertation,Department of Computer Science,University of Central
Florida,Orlando,(1997),
[34] B.M.E.Moret,and H.D.Shapiro,An empirical analysis of algorithms for constructing
minimum spanning tree,Lect,Notes on Comp,Science,519(1991)400-411,
[35] G,Galbiati,F,Maffioli,A,Morzenti,A short note on the approximability of the maximum
leaves spanning tree problem,Info,Proc,Lett,52(1994)45-49,
[36] L,Gouveia,A 2n constraint formulation for the capacitated minimal spanning tree problem,
Operation Research,43(1995) 130-141,
[37] H,I,Lu,R,Ravi,The power of local optimization,Approximation algorithms for
maximum-leaf spanning tree,in Proc,30
th
Allerton Conference,(1992)533-542,
[38] K,Malik,G,Yu,A branch and bound algorithm for the capacitated minimum spanning tree
problem,Networks,23(1993) 525-532,
[39] W,Xu,Quadratic minimum spanning tree problems and related topics,Ph.D,Dissertation,
Dept,of Math.,Univ,of Maryland,College Park,MD,(1984),
[40] M.R,Henzinger and V,King,Maintaining minimum spanning forests in dynamic graphs,
SIAM J,on Computing,31:2(2001) 364-374,
[41] G,Robins and J.S,Salowe,Low-degree minimum spanning trees,Discrete and
Computational Geometry,14:2(1995)151-166,
[42] 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,
有关随机生成树问题可参阅,
[43] D.J,Bertsimas,The probabilistic minimum spanning tree problem,Networks,20 (1990),
245-275,
25
[44] S.Geetha,K.P.K.Nair,On stochastic spanning tree problem,Networks,23(1993)675-679,
[45] H,Ishii,S,Shiode,T,Nishida,Y,Namasuya,Stochastic spanning tree problem,Discrete
Applied Mathematics,3(1981) 263-273,
[46] I.B,Moret,Interval elimination method for stochastic spanning tree problem,Appl,Math,
And Computation,66(1994) 325-331,
有时需要考虑欧氏距离下图的最小生成树问题，这方面可参考文献,
[47] C,Monna,and S.Suri,Transitions in geometric minimum spanning trees,Discrete and
Computational Geometry,8:2(1992)265-293,
[48] J.M,Ho,D.T.Lee,C.H,Chang,C.K,Wong,Minimum diameter spanning trees and related
problems,SIAM J,Computing,20:5(1991) 987-997,
[49] S,Khuller,B.Raghavachari,and N.Young,Low degree spanning tree of small weights,SIAM
J,Computing,25:2(1996) 355-368,
[50] G,Robins and J.S,Salowe,On the maximum degree of minimum spanning trees,Discrete
and Computational Geometry,14:2(1995)151-166,
关于最小生成树的更全面的介绍请参看文献,
[51] R.K,Ahuja,T.L,Magnanti,and J.B,Orlin,Network Flows,Prentice Hall,1993,
[52] D.R,Karger,P.N,Klein,and R.E,Tarjan,A randomized linear-time algorithm to find
minimum spanning trees,J,Assoc.Comp,Mach.,42(1995) 321-328,
[53] R.E.Tarjan,A simple version of Karzanov’s blocking flow algorithm,Operation Research
Letters,2(1984) 265-268,
[54] H.N.Gabow,Z.Galil,T.Spencer,and R.E.Tarjan,Efficient algorithms for finding minimum
spanning trees in undirected and directed graphs,Combinatorica,6(1986) 109-122,
[55] J.B.Jr.Kruskal,On the shortest spanning subtree of a graph and the Traveling Salesman
Problem,Proceedings of the American Mathematical Society,7(1956) 48-50,
[56] R.C.Prim,Shortest connection networks and some generalizations,Bell Systems Technical
Journal,36(1957) 1389-1401,
[57] S,Khuller,B,Raghavachari,N,Young,Balancing minimum spanning and shortest path trees,
Algorithmica,14:4(1995)305-321,
[58] D,Jungnickel,Graphs,Networks and Algorithms,(Algorithms and Computation in
Mathematics,Vol.5),Springer,1998。
§ 1.5 图的中心与重心
一、基本概念
设 G 是一个赋权图，每条边 v
i
v
j
上的权为 0
ij
w ≥,每个顶点
i
v 也有一个权 () 0
i
qv ≥ 。
(,)duv表示在考虑边赋权下图 G 中顶点 u 到 v 的距离。
图 G 的 半径 (radius)：
() ()
rad min max (,)
uVG vVG
Gdu
∈ ∈
= 。
图 G 的 直径 (diameter)：
() ()
max max (,) max{ (,) |,( )}
uVG vVG
diam G d u v d u v u v V G
∈∈
==?∈。
图中顶点 v 的 离心率 (eccentricity)：
()
() max () (,)
uVG
ev quduv
∈
= 。
图 G 的 中心 （ center）,图 G 中具有最小离心率的顶点。
图 G 的 重心 （ barycenter,）,,设
()
() () (,)
uVG
gv quduv
∈
=
∑
，使 g(v)达到最小的顶点称为图 G
26
的重心。重心也称为中位点（ median） 。
注,（ 1）一个图的中心一般不唯一，重心一般也不唯一；中心和重心未必相同。
（ 2）对于顶点无赋权的图，可将每个顶点的权看作 1,即得到离心率、中心、重心的相应定义。此时，图的半径
()
rad min ( )
vVG
Gev
∈
=,图的直径
()
diam max ( )
vVG
Gev
∈
= 。进一步地，如果图的边也无赋权，则将每条边上的权视为 1,便得到半径、直径、离心率、中心、重心的相应定义。此时，距离 (,)duv实际上是在边非赋权情况下顶点 u 到 v 的距离。
例 1.5.1 求如下非赋权图 G 的半径、直径、所有的中心、重心以及点 v
10
的离心率。
解,按定义求得，中心集合为 v
3
和 v
4
，半径 rad (G) = 4，直径 diam (G) =7，离心率 e(v
10
)=5.。
重心 v
3
，因为 g(v
3
)=30 是所有 g(v)中最小的。
二、求图的中心和重心的算法
根据中心和重心的定义不难得出如下算法。
1．求中心的算法
算法1,求图 G 的中心
第 1 步 利用最短路算法求出 G 中所有顶点间的距离。
第 2 步 对 G 的每个顶点 v，计算离心率
()
() max () (,)
uVG
ev quduv
∈
= 。
第 3 步 比较各顶点的离心率，求出离心率最小的顶点。
第 4 步 结束。
该算法可以通过距离矩阵实现。
算法 2,求图 G 的中心(距离矩阵形式)
第 1 步 利用最短路算法求出 G 中所有顶点间的距离，并组成距离矩阵 ()
ij
Dd=,其元素
d
ij
是图 G 中顶点 v
i
与顶点 v
j
间的距离,,1,2,,ij υ= null 。
第 2 步 对 j=1,2,···,υ,给矩阵 D 的第 j 列乘以 ()
j
qv ； 并求出所得矩阵每一行的最大元素：
()
i
ev,1,2,,i υ= null 。
第 3 步 比较所有 ()
i
ev,（ 1,2,,i υ= null ）,其中最小者所在的行对应的顶点即为 G 的中心。
第 4 步 结束。
上述算法的正确性是显然的。如果第 1 步中求距离使用 Floyd 最短路算法，则上述算法的时间复杂度为 O(n
3
),
2．求重心的算法
v
5
v
11
v
8
v
9
v
10
v
12
v
6
v
7
v
1
v
2
v
3
v
4
v
13
v
14
27
算法1,求图 G 的重心
第 1 步 利用最短路算法求出 G 中所有顶点间的距离。
第2步 对 G 的每个顶点 v，计算
()
() () (,)
uVG
gv quduv
∈
=
∑
。
第 3 步 比较各顶点的 ()gv值，求出使 ()gv达到最小的顶点。
第 4 步 结束。
算法2,求图 G 的重心(距离矩阵形式)
第 1 步 利用最短路算法求出 G 中所有顶点间的距离，并组成距离矩阵 ()
ij
Dd=,其元素
d
ij
是图 G 中顶点 v
i
与顶点 v
j
间的距离,,1,2,,ij υ= null 。
第 2 步 对 j=1,2,···,υ,给矩阵 D 的第 j 列乘以 ()
j
qv ；并求出所得矩阵各行和行和：
1
() ( )
ijij
j
gv qv d
υ
=
=
∑
,1,2,,i υ= null 。
第 3 步 比较所有行和 ()
i
gv,（ 1,2,,i υ= null ）,其中最小者所在的行对应的顶点即为 G 的中心。
第 4 步 结束。
该算法的正确性也是显然的。如果第 1 步中求距离使用 Floyd 最短路算法，则上述算法的时间复杂度为 O(n
3
),
例 1.5.2 设某市有 7 个化工厂，已知这些工厂间的公路及距离（公里）如图所示。现拟建一个消防队负责这些工厂的消防工作。问消防队应设在哪个工厂，以便任一个工厂失火时都能及时赶去灭火？
解,为了使消防队能在最短时间赶到任一个工厂灭火,需要消防队离最远点的距离尽可能短。
因此这是一个确定图的中心的问题。此例中图的顶点无赋权，故可将所有顶点的权视为 1。
利用最短路算法求得图 G 的距离矩阵为
0 3 5 9.3 6.3 4.5 6
3 0 2 6.3 3.3 1.5 3
520522.54
9.3 6.3 5 0 3 4.8 6.3
6.3 3.3 2 3 0 1.8 3.3
4.5 1.5 2.5 4.8 1.8 0 1.5
6 3 4 6.3 3.3 1.5 0
D
=
求得 D 的各行最大元分别为 9.3,6.3,5,9.3,6.3,4.8,6.3，其最小者为 4.8，对应于第 6 行，故中心为 v
6
，因此应将消防队设在 v
6
处。
v
5
2
v
6
v
7
v
1
v
2
v
3
v
4
3
2
6
3
2.5
1.8
1.5
1.5
28
例 1.5.3 设某能源集团有若干煤矿，集团打算在这些矿点之一建一个火力发电厂。已知这些煤矿间的道路连接及距离（公里）如图所示，各煤矿每年可供应给该电厂的原煤预计产量
（万吨）为（ 0.5,1.08,0.7,1,1.3,0.3,0.6） 。问发电厂应建在哪个矿点，才能使发电厂每年的原煤运费最省？
解,这是一个确定图的重心的问题。利用最短路算法求得图 G 的距离矩阵为
0 305093634560
30 0 20 63 33 15 30
50 20 0 50 20 25 40
93 63 50 0 30 48 63
63 33 20 30 0 18 33
45 15 25 48 18 0 15
60 30 40 63 33 15 0
D
=
各列分别乘以相应顶点的产量，得
1
0 32.4 35 93 81.9 13.5 36
15 0 14 63 42.9 4.5 18
25 21.6 0 50 26 7.5 24
46.5 68.04 35 0 39 14.4 37.8
31.5 35.64 14 30 0 5.4 19.8
22.5 16.2 17.5 48 23.4 0 9
30 32.4 28 63 42.9 4.5 0
D
=
D
1
的行和依次为,291.8,157.4,154.1,240.74,136.34,136.6,200.8，其最小者为 136.34，
对应于第 5 行，故中心为 v
5
，因此发电厂应设在 v
5
处，每年原煤总运费为 136.34 万吨公里乘以单位运价。
三、树的中心和重心
本部分我们对顶点和边均无赋权的树讨论其中心和重心。 在这种情况下树 T 中顶点的离心率为
()
() max (,)
uVT
ev duv
∈
=,树的中心是具有最小离心率的顶点，而树的重心是使
()
() (,)
uVT
gv duv
∈
=
∑
达到最小的顶点。
定理 1.5.1(Jordan,1869) 一棵树要么只有一个中心，要么有两个相邻的中心。
证明,当 2υ ≤ 时，结论显然成立。
设结论对所有 kυ ≤ 的树都成立。我们来证明结论对 1kυ = + 的树也成立。
v
5
20
v
6
v
7
v
1
v
2
v
3
v
4
30
20
60
30
25
18
15
15
29
设树 T 是一棵顶点数 12kυ =+>的树。由于 () 2Tυ >,故 T 的中心不会是叶子（ 1
度顶点） 。设
T
V′是 T 的所有叶子的集合，则删去 T 的所有叶子所得之图
T
TTV′′=? 仍是树。
我们来证明 T′与 T 具有相同的中心。
首先因 () 2Tυ >,故 T 的顶点不全是 1 度的，因而 ()VT′ 非空。对 ()uVT′? ∈,必有
()uVT∈ 。 设 v
是 T 中到 u 距离最远的顶点,即
()
(,) max (,) ()
TT
vVT
duv duv eu
∈
==，（ ()
T
eu
表示 u 在 T 中的离心率）,则 v
必是 T 的叶子（否则 u 到 v
的最短路通过 v
仍可延伸,v
不会是到 u 的最远点） 。由于 T′是由 T 删去所有叶子顶点后形成的，上述结论表明 T′中每个顶点的离心率比 T 中减少 1，即
() () 1,( )
TT
eu eu uVT
′
′=∈ 。
可见 ()uVT
′∈ 使
()
() min ()
TT
uVT
eu eu
′′
′∈
= 当且仅当
()
() min ()
TT
uVT
eu eu
∈
=,因此 T′与 T 具有相同的中心。
由于 ()Tkυ ′ ≤,按照归纳假设,T′要么只有一个中心，要么有两个相邻的中心。因此
T 也只有一个中心或有两个相邻的中心。归纳法完成，证毕。
对树的重心有类似的结论。
定理 1.5.2(Jordan,1869) 一棵树要么只有一个重心，要么有两个相邻的重心。
证明留作习题。
设 T 是一棵树。对 T 中任一个顶点 u，若 ()du k=,则 T 可分解成由 u 出发的 k 个分支（每个分支都含有 u 作为其一个叶子）,其中具有最多边数的那个分支中所含的边数，称为顶点 u 的 分支权,记为 ()qu
定理 1.5.3 设 T 是一棵树,uT∈ 。 u 是 T 的重心当且仅当 u 是 T 中具有最小分支权的顶点，
即
()
() min ()
vVT
qu qv
∈
= 。
证明：按定义，树的重心是使
()
() (,)
uVT
gv duv
∈
=
∑
达到最小的顶点。我们只需证明，对
()vVT?∈,() ()gu gv≤ 当且仅当 () ()qu qv≤ 。
事实上，由于 T 是树，故 u,v 两点间仅有唯一一条路相连，记此路为 P。假定从 u 出发不含 v 的分支有 k 个，分别为 J
1
+u,J
2
+u,···,J
k
+u；从 v 出发不含 u 的分支有 r 个，分别为 H
1
+v,H
2
+v,···,H
r
+v,并设
12 k
JJ J J= ∪∪null∪ 共含有 n
1
个顶点，
12 r
HH H H= ∪∪null∪
共含有 n
2
个顶点；
P
u
v
J
1
J
k
J
2
H
1
H
r
H
2
30
则显然
()
() (,)
xVT
gu dxu
∈
=
∑
＝
()
(,)
xV J
dxu
∈
∑
+
2
()
(,) (,)
yVH
dyv nduv
∈
+
∑
,
()
() (,)
xVT
gv dxv
∈
=
∑
＝
()
(,)
xV J
dxu
∈
∑
+
1
()
(,) (,)
yVH
dyv nduv
∈
+
∑
。
由此可见,
若 () ()gu gv≤,则
21
nn≤,此时 v 出发的最大分支必定是含 x 的那个分支，因而
() ()qu qv≤ 。
反之，若 () ()qu qv≤,我们分两种情况来证明 () ()gu gv≤ 。
（ 1）如果 u 的最大分支是不含 v 的某个分支，无妨设为 J
1
＋ u。则显然
11
()nJυ≥≥u 的含有 v 的那个分支的顶点数 ─1
2
n>,从而 () ()gu gv≤ 。
（ 2）如果 u 的最大分支是含 v 的那个分支，则 v 的最大分支必是含 u 的分支（若不然，假定 v 的最大分支是 H
i
，则 ()qu =u 的含 v 的分支所含点数－ 1
1
() ()Hqvυ>=，与前提条件
矛盾） 。但此时,
()qu =
12
() ( ) ( ) ()
r
PH H Pnε υυε+ ++ = +null
()qv =
11
() ( ) ( ) ()
k
PJ J Pnε + ++ = +null
因 () ()qu qv≤,故
21
nn≤,从而 () ()gu gv≤ 。证毕。
这个定理的结论使我们能够较容易地确定树的重心。实际上，该充分必要条件往往作为树的重心的另一种定义。一些著作中将这样定义的重心称为树的形心（ centroid） 。
值得一提的是，树的中心和重心未必重合，例如下图中所示的树的中心为 v，而重心为
w。这也说明一般情况下，图的中心和重心未必重合。
还需指出，树 T 中所有顶点对的距离之和
,()
() (,)
uv V T
WT duv
∈
=
∑
称为该树的 Wiener 指数，它是树的一个重要参数，在化学和通信理论中有重要的应用，读者可参看文献,
[59] A.A,Dobrynin,R,Entringer,and I,Gutman,Wiener Index of trees,theory and applications,
Acta Applicandae Mathematicae,66(2001) 211-249,
[60] M,Diudea,I.Gutman,and L.Jantschi,Molecular Topology,Nova Publishers,Huntington,
New York,2001,
[61] I,Gutman,E,Estrada,and O,Ivanciuc,Some properties of the Weiner polynomial of trees,
Graph Theory Notes of New York,36(1999) 7-13,
[62] J,Rada,Variation of the Wiener index under tree transformations,Discrete Applied
Mathematics,148(2005),135-146,
[63] J,Rada,and C,Uzcátehui,Randi? ordering of chemical tree,Discrete Applied Mathematics,
150(2005),232-250,
[64] M,Fischermann,A,Hoffmann,D,Rautenbach,L,Székely and L,Volkmann,Wiener index
versus maximum degree in trees,Discrete Applied Mathematics,122(2002),127-137,
v w
31
[65] W.C,Shiu,P.C,Bor Lam,and K.K,Poon,On Wiener numbers of polygonal nets,122(2002),
251-261,
图的中心和重心属于图论和网络最优化的一个研究专题－选址问题（ location problem）
的研究范畴，实际应用中常见的 k 中心问题,k 重心问题，以及各种限制条件下求中心和重心的问题，都属于这一研究方向。在这一研究专题上已有丰富的研究成果，有兴趣的读者可查阅参考文献 [66~73]。
[66] Nicos Christofides,Graph theory –an algorithmic approach,Academic Press,INC.,1990,
[67] Z.Drezner,Facility location-a survey of applications and methods,Springer Ser,Oper,Res.,
Springer,New York,1995,
[68] G.Y.Handler,P.B,Mirchandani,Location in networks,theory and algorithms,MIT Press,
Massachusetts,1979,
[69] R.F.Love,Facility location –models and methods,North-Holland,1988,
[70] P.B,Mirchandani,R.L.Francis,Discrete location theory,John Wiley & Sons,Inc.,New York,
1990,
[71] J,Bar-Ilan et al,How to allocate network center,J,Algorithms,15(1993)385-415,
[72] J,Plesnik,A heuristic for the p-center problem in graphs,Discrete Applied Math.,
17(1987)262-268,
[73] S,Guha,S,Khuller,Connected facility location problems,in Network Design,connectivity
and facilities location (P.M,Pardalos and Ding-zhu Du eds.),DIMACS Series in Discrete
Mathematics and Theoretical Computer Science,Vol.40,(1998) 179-190
§ 1.6 图的矩阵表示
设图 G=(V,E)，其中
12
{,,,}Vvv v
υ
= null,
12
{,,,}Eee e
ε
= null 。定义 G 的关联矩阵和邻接矩阵如下,
（ 1）关联矩阵
=)(GM
12
111 12 1
221 2 2
12
ee e
vm m m
vm m m
vm m m
ε
ε
ε
υ υυ υε
null
null
null
nullnull nullnullnull
null
,
其中
ij
m 表示顶点
i
v 与边
j
e 关联的次数。
（ 2）邻接矩阵
=)(GA
12
111 12 1
221 2 2
12
vv v
va a a
va a a
va a a
υ
υ
υ
υ υυ υ
null
null
null
nullnullnullnullnull
null
,
32
其中
ij
a 表示顶点
i
v 与
j
v 相邻的次数。
例 1.6.1 求下图的关联矩阵和邻接矩阵。
解,
=
0211000
1001100
0000111
1010011
)(GM,
=
1101
1011
0102
1120
)(GA 。
通过观察容易看出，图 G 的关联矩阵 M(G)和邻接矩阵 A(G)有如下特点,
（ 1） M(G)的元素是 0,1 或 2，其中元素 2 是由环边导致的； A(G)的元素也是 0,1 或 2，
其中 2 是由重边导致的（若两点间有多于两条重边，则会出现大于 2 的元素） 。如果图 G 是简单图，则关联矩阵 M(G)和邻接矩阵 A(G)中只有元素 0 和 1。
（ 2）邻接矩阵 A(G)是对称矩阵。
（ 3） M(G)中每列之和＝ 2； M(G)中第 i 行之和＝ v
i
的度；
若 G 中无环边，则 A(G)的主对角线元素全为 0，且 A(G)中第 i 行（列）之和＝ v
i
的度。
定理 1.6.1 设 A 是 υ阶图 G 的邻接矩阵，则 A
n
的第 i 行第 j 列元素
()n
ij
a 等于 G 中从 v
i
到 v
j
的长度为 n 的路的数目,(1 n υ≤<)。
证明：对 n 作数学归纳法。
n=1 时,A 的第 i 行第 j 列元素
(1)
ij ij
aa= 表示顶点 v
i
到 v
j
的边数，即 v
i
到 v
j
的长度为 1
的路的数目，结论成立。
假设 n = k 时结论成立，即 A
k
的第 i 行第 j 列元素
()k
ij
a 等于 G 中从 v
i
到 v
j
的长度为 k 的路的数目。
当 n = k +1 时,A
n
= A
k+1
=AA
k
，故
() ( 1) ()
1
nk k
ij ij ir rj
r
aa aa
υ
+
=
==
∑
。
由于
ir
a 是 G 中顶点 v
i
到 v
r
的长度为 1 的路的数目，
()k
rj
a 是 G 中顶点 v
r
到 v
j
的长度为 k 的路的数目，故
()k
ir rj
aa 是 G 中从顶点 v
i
经过 v
r
到 v
j
的长度为 k+1 的路的数目，因而
()
1
k
ir rj
r
aa
υ
=
∑
是 G 中从顶点 v
i
到 v
j
的长度为 k+1 的路的总数，可见定理结论对 n = k +1 成立。
归纳法完成。
推论 1.6.1 设 A 是图 G 的邻接矩阵，则
（ 1） A
2
的对角线元素
(2)
ii
a 是 G 中顶点 v
i
的度数；
e
1
e
2
e
3
e
4
e
5
e
6
e
7
v
1 v2
v
4
v
3
33
（ 2） A
3
的对角线元素
(3)
ii
a 是 G 中含顶点 v
i
的三角形的数目的两倍；
（ 3）若 G 是连通图，则 G 中任二相异点 v
i
与 v
j
间的距离等于使 A
n
的元素
()
0
n
ij
a ≠ 的最小的整数 n。
推论 1.6.2 图 G 中三角形的数目等于 A
3
的迹除以 6。
推论 1.6.3 设 A 是 υ阶图 G 的邻接矩阵，
2
()
k
ij
AA A r+++=null,则 r
ij
就是 G 中从顶点
v
i
到 v
j
的长度不超过 k 的路的数目。
以上推论由读者自行给出证明。
推论 1.6.4 设 A 是 υ阶图 G 的邻接矩阵 (3)υ ≥,
21
R AA A
υ?
= +++null,则图 G 连通的充分必要条件是矩阵 R 中每个元素均不为零。
证明：设
() ()
(),( ),()
kk
ij ij ij
A aA a Rr===。
必要性：设 G 是连通图，则 G 中任二顶点 v
i
与 v
j
之间都有路相连，取一条 (v
i
,v
j
)路，设其长度为 k（显然 11k υ≤≤?）,则
()
1
k
ij
a ≥,故由 R 的定义，
()
1
k
ij ij
ra≥≥；而对
{1,2,,}i υ?∈ null,因 G 连通且 3υ ≥,故
(2)
() 1
ii ii i
ra dv≥= ≥。可见 R 中没有零元素。
充分性：设 v
i
与 v
j
是 G 中任二相异顶点。因
(2) ( 1)
0
ij ij ij ij
raa a
υ?
= +++ ≠null,故必有某
()
0
k
ij
a ≠ 。因此在 G 中有至少一条长为 k 的 (v
i
,v
j
)路，由此可见 G 是连通图。
推论 1.6.5 设 A 是图 G 的邻接矩阵，
2 k
k
R AA A= +++null,则 G 的顶点 v
i
的离心率 e(v
i
)
等于使得矩阵 R
k
的第 i 行没有零元素的最小 k 值。
推论 1.6.6 设 A 是连通图 G 的邻接矩阵，
2 k
k
R AA A= +++null,则 G 的半径 rad(G)等于使得矩阵 R
k
中至少有一行没有零元素的最小 k 值。
推论 1.6.7 设 A 是连通图 G 的邻接矩阵，
2 k
k
R AA A= +++null,则 G 的直径 D(G)等于使得矩阵 R
k
中没有零元素的最小 k 值。
这三个推论的证明留给读者。
推论 1.6.6 不仅给出了求图的半径的方法，同时也给出了求无赋权图的中心的方法：在依次计算
12 1
,,R RR
υ?
null 的过程中，当遇到某个 k 对应的 R
k
中至少有一行没有零元素时，非零行对应的顶点即为图的中心。
图在计算机上处理时，可以以关联矩阵或邻接矩阵的形式存于计算机中。因邻接矩阵比关联矩阵小且又是对称矩阵，故在计算机存储时通常使用邻接矩阵的上三角部分。
