3.1 树的有关定义
给定一个图 G = (V ，E)，如果它不含任何回路，
图 3.1
我们就称它是林；如果 G 又是连通的，即这个林只有
一个连通支，就称它是树。树是图论中最重要的概念
之一，在自然科学和社会科学的许多领域都有广泛的
应用。
例 3.1.1 网球单打比赛前，当抽签之后为说明
各选手间的相遇情况，往往画一张图，如图 3.1所示。
它是一棵树。
例 3.1.2 中子轰击原子核时产生的裂变过程，
也可以形象地用图 3.2 示意，它也是一棵树。
图 3.2
定义 3.1.1 一个不含任何回路的连通图称为树，用 T 表示。T 中的边称为树枝，度
为 1 的顶点称为树叶。
对于树，如果去掉一条边，该边原来所在的图就会被分成不连通的两部分，所以树的
每条边都是割边。
定理 3.1.1 e = (u，v) 是割边，当且仅当 e 不属于 G 的任何回路。
证明：先证明必要性，再证明充分性，采用反证法进行证明。
若 e = (u，v) 属于 G 的某个回路，则 G′ = G . e 中仍存在 u 到 v 的道路，故顶点
u 和 v 属于同一连通支，e 不是割边；反之，若 e 不是割边，则 G′ 与 G 的连通支数一样。
于是 u 和 v 仍属于同一连通支，故 G′ 中存在道路 P(u，v)，P(u，v) + e 就是 G 的一个
回路。
图论与代数结构（第 2 版）
下面给出树的等价定义。
定理 3.1.2 设 T 是顶点数为 n . 2 的树，则下列性质等价。
(1) T 连通且无回路。
(2) T 连通且每条边都是割边。
(3) T 连通且有 n . 1 条边。
(4) T 有 n . 1 条边且无回路。
(5) T 的任意两顶点间有唯一道路。
(6) T 无回路，但在任两顶点间加上一条边后恰有一个回路。
证明：
(1) → (2) T 无回路，即 T 的任意边 e 都不属于回路，由定理 3.1.1，e 是割边。
(2) → (3) 对顶点数 n 进行归纳。令 n(T)、m(T) 分别表示树 T 的顶点数与边数。
当 n = 2 时命题成立，设 n . k 时，m(T) = n(T) . 1 成立。则 n = k + 1 时，由于任
一边 e 都是割边，故 G′ = G . e 有两个连通支 T1 和 T2。由于 n (Ti) . k，i = 1，2，故
m(Ti) = n (Ti) . 1。所以 m(T) = n(T) . 1 也成立。
(3) → (4) 假定 T 有回路，设 C 是其中一条含有 k(< n) 个顶点的初级回路。因为 T
连通，所以 V (T) . V (C) 中一定有顶点 u 与 C 上某点 v 相邻，即存在边 (u，v) ∈ E(T)，
以此类推，最终 V (T) . V (C) 中的 n . k 个顶点需要 n . k 条边才可能保持 T 连通，但
| E(T). E(C) |= n . 1 . k < n . k。矛盾。
(4) → (5) 设 u、v 是 T 的任意两顶点，先证道路 P(u，v) 的存在性：如果不存在
P(u，v)，则 u、v 属于不同连通支 T1 和 T2。由 m(T) = n . 1，则至少有一个支，例如
T1，使 n (T1) . m(T1) 成立。这样 T1 则有回路，亦即 T 中有回路。反之，若 T 无回
路，则因为各连通支都有 m(Ti) . n (Ti) . 1，从而使 m(T) < n . 1。均产生矛盾，因此
P(u，v) 一定存在。再证唯一性：若存在两条不同的道路 P(u，v) 和 P′(u，v)，则其对称
差 P(u，v) ⊕ P′(u，v) 至少含有一个回路。故而得证。
(5) → (6)，(6) → (1) 均显然。因此等价定理得证。
定理 3.1.2 对判断和构造树 T 将带来很大方便。
R启发与思考
在这 6 条树的性质中，最常用的 3 条性质是连通、无回路、n . 1 条边（顶数比
边数多 1）。若图 T 满足其中任意两条，就可以判定 T 是树（定理中的等价条件 (1)、
(3)、(4)）。
定理 3.1.3 树 T 中一定存在树叶顶点。
证明：（反证法）
由于 T 是连通图，所以任一顶点 vi ∈ V (T)，都有 d (vi) . 1。若无树叶，则 d (vi) . 2。
根据树的性质 (3)，T 连通且有 n . 1 条边，这样 n . 1 = m =
1
2 Pd (vi) . n. 矛盾。
· 60 ·
第 3 章 树
定义 3.1.2 如果 T 是图 G 的支撑子图，而且又
是一棵树，则称 T 是 G 的一棵支撑树，或称生成树，又
简称为 G 的树。
例如图 3.3 的粗线边构成了 G 的一棵支撑树 T。显
然 G 有支撑树的充要条件为 G 是连通图，而且如果连通
图 G 本身不是树，那么它的支撑树不唯一，例如图 3.3 中
还有许多不同的支撑树。给定图 G 的一棵树 T，我们称
G.T，即 G 删去 T 中各边后的子图为 T 的余树，用 T
表示。例如在图 3.3 中，E(T) = {e2，e6，e8，e9，e10}。
一般情况下，余树不是一棵树。
图 3.3
3.2 基本关联矩阵及其性质
本节讨论的对象是有向连通图 G。
定义 3.2.1 在有向连通图 G = (V ，E) 的关联矩阵 B 中划去任意顶点 vk 所对应
的行，得到一个 (n . 1) × m 的矩阵 Bk，Bk 称为 G 的一个基本关联矩阵。
例如图 3.3 中顶点 v6 所对应的基本关联矩阵是
B6 = 266664
377775
v1 1 1 0 0 0 1 0 0 0 0
v2 .1 0 .1 1 0 0 1 0 0 0
v3 0 .1 1 0 0 0 0 .1 1 0
v4 0 0 0 .1 .1 0 0 0 0 0
v5 0 0 0 0 1 .1 0 1 0 .1
e1 e2 e3 e4 e5 e6 e7 e8 e9 e10
基本关联矩阵与 G 的支撑树之间有密切联系。我们首先分析关联矩阵的性质。
定理 3.2.1 有向图 G = (V ，E) 关联矩阵 B 的秩 rankB < n。
证明：由于 B 中每列都只有 1 和 .1 两个非零元素，故 B 的任意 n . 1 行加到第 n
行上后，第 n 行为全零，即 B 的 n 个行向量线性相关，故 rankB < n。
R启发与思考
有向连通图 G 的关联矩阵删去一行不会造成关联矩阵信息的丢失，为什么？
定理 3.2.2 设 B0 是有向图 G 关联矩阵 B 的任意一 k 阶子方阵，则 det (B0) 为
0、1 或 .1。
证明：因为 B0 是 B 的某一 k 阶子阵，显然 B0 每列最多只有 2 个非零元。若其中
某列全为零元，则 det (B0) = 0；若 B0 每列都有 2 个非零元，显然也有 det (B0) = 0；否
则 B0 中存在只有 1 个非零元的列，按该列展开得到 det (B1) = {± det (B0)}，但 B1 的
阶为 k . 1。以此类推，可知最终 det (B0) 或为 0，或为 1，或为 .1。
· 61 ·
图论与代数结构（第 2 版）
定理 3.2.3 设 B 是有向连通图 G 的关联矩阵，则 rankB = n . 1。
证明：由定理 3.2.1 知 rankB < n，现只需要证明 rankB . n.1。不失一般性，设 B 中
最少的线性相关的行数为 l，显然 l . n，而且这 l 行分别与顶点 v (i1) ，v (i2) ， · · · ，v (il)
相对应，因此有
k1b (i1) + k2b (i2) + · · · + klb (il) = 0 kj .= 0，j = 1，2， · · · ，l (3-1)
由于矩阵 B 每列只有 2 个非零元，所以在这 l 个行向量 b (ij) 中，其第 t(t = 1，2， · · · ，m)
个分量最多只有 2 个非零元。当然也可能全为 0。但是可以断言：不可能只有 1 个非零元。
否则，由于 ki .= 0，式 (3-1) 不会成立。这样可以对矩阵 B 分别进行行、列交换，使前 l
行是线性相关的诸行；这在 l 行中每列都有 2 个非零元换到前 r 列，其余 m.r 列全都是
零元。这样矩阵 B 变换为
B′ ="P 0 # l
0 Q n . l
r m . r
但 rankB′ = rankB，而且 B′ 依然是 G 的一个关联矩阵，与 B 相比只是顶点与边的编
号不同而已。若 n . l > 0，由 B′ 可见，G 至少分为 2 个连通支：其中 r 条边只与 l 个顶
点相关，而其余 m. r 条边只与另外 n . l 个顶点相关。这与 G 是连通图矛盾。因此，一
定有 n.l = 0，即 l = n，也就是说 B 中最少需要 n 行才能线性相关，而任何 n.1 行都
将线性无关，因此 rankB . n . 1。
由此，我们立刻得到定理 3.2.4。
定理 3.2.4 连通图 G 基本关联矩阵 Bk 的秩 rank Bk = n . 1。
推论 3.2.1 n 个顶点树 T 的基本关联矩阵的秩是 n . 1。
树是包含边数最少的连通图。对于连通图 G，显然满足 m . n . 1。既然连通图基本
关联矩阵 Bk 的秩是 n.1，那么 Bk 中一定存在 n.1 个线性无关的列，究竟哪些列会是
线性无关的，哪些列又必定线性相关呢?
定理 3.2.5 设 Bk 是连通图 G 的基本关联矩阵，C 是 G 中的一个回路，则 C 中
各边所对应 Bk 的各列线性相关。
证明：只需要针对 C 是初级回路进行讨论，设 C 包含了 G 的 l 个顶点和 l 条边 (不
妨 l < n)，这 l 条边对应关联矩阵 B 的 l 列，它们构成 B 的子阵 B(Gc)。由于 C 本身
也是连通图，所以 B(C) 是 l 阶方阵，而 rankB(C) = l . 1，故 B(C) 的 l 列线性相关，
但它又是 B(Gc) 的子阵。由于 B(Gc) 对应的各边只经过回路 C 的顶点，因此 B(Gc) 中
其余顶点所对应的行元素全为零。这样，B(Gc) 的 l 列仍是线性相关，显然 Bk(Gc) 的各
列也线性相关。
推论 3.2.2 设 H 是连通图 G 的子图，如果 H 含有回路，则 H 的各边对应的 G 的
基本关联矩阵各列线性相关。
定理 3.2.6 令 Bk 是有向连通图 G 的基本关联矩阵，那么 Bk 的任意 n.1 阶子
阵行列式非零的充要条件是其各列所对应的边构成 G 的一棵支撑树。
· 62 ·
第 3 章 树
证明：必要性。如果某个 n.1 阶子阵 Bk (GT ) 的行列式非零。则由推论 3.2.2，T 中
不含回路，它包含 n 个顶点和 n . 1 条边，根据定理 3.1.2 的等价定义 (4)，T 是 G 的一
棵树。充分性。设 T 是 G 的一棵树，子图 T 的基本关联矩阵 Bk(T) 是 n . 1 阶的方阵，
其行列式非零，它又恰好对应 Bk 的某个 n . 1 阶子阵，即 Bk 所对应的该 n . 1 阶行列
式非零。
定理 3.2.6 说明图 G 基本关联矩阵中行列式非零的 n . 1 阶子阵的数目与 G 不同的
支撑树数目之间存在一种对应关系。
3.3 支撑树的计数
本节讨论连通图 G 中支撑树的数目以及根树的数目。
定理 3.3.1（Binet-Cauchy 定理） 已知两个矩阵 A = (aij)m×n
和 B = (bij)n×m
，
满足 m . n，则 det(AB) =Xi
AiBi，其中 Ai、Bi 都是 m 阶行列式，Ai 是从 A 中取
不同的 m 列所成的行列式，Bi 是从 B 中取相应的 m 行构成的行列式，然后再对全部组
合求和。
定理的证明从略。现举一例进行说明和验证。
例 3.3.1 已知
A = " 4 3 2
.2 4 3 # B =2664
5 1
0 3
4 2
3775
求 det(AB)。
解：由矩阵乘法
AB = " 28 17
2 16 #
所以 det(AB)=414。由比内-柯西定理计算，
det(AB) =Xi
AiBi
=
4 3
.2 4
5 1
0 3
+
4 2
.2 3
5 1
4 2
+
3 2
4 3
0 3
4 2
= 414
从例中显然可见，用比内-柯西定理计算乘积矩阵的行列式比通常的方法复杂，但该定
理揭示了乘积矩阵的行列式与各矩阵的子阵行列式之间的关系，连通图 G 不同支撑树的计
数恰好利用了这种关系，从而使计数问题很容易地得到解决。下面针对不同的对象分别讨
论树的计数。
· 63 ·
图论与代数结构（第 2 版）
3.3.1 有向连通图的树计数
定理 3.3.2 设 Bk 是有向连通图 G = (V ，E) 的某一基本关联矩阵，则 G 的不
同树的数目是 det ..BkBT
k 。
证明：设 Bk = (bij)(n.1)×m
，由于 G 是连通图，故 n . 1 . m，由比内–柯西定理
det ..BkBT
k =Xi
|Bi|
BT
i
(3-2)
其中 |Bi| 是 Bk 的某一 n . 1 阶子阵的行列式，
BT
i
是对应的 BT
k 的 n . 1 阶子阵的
行列式，由于 BT
k 是 Bk 的转置矩阵，所以
BT
i
的第 j 行正好是 |Bi| 的第 j 列，亦即
|Bi| =
BT
i
，式 (3-2) 可写成
det ..BkBT
k =Xi
|Bi|2 (3-3)
由定理 3.2.6，如果 |Bi| .= 0，则其所对应的边构成 G 的一
图 3.4
棵树，由定理 3.2.2，此时 |Bi| = 1 或 .1，因此 |Bi|2 = 1。
这说明如果 Bi 的各列所对应的边构成 G 的一棵树，则对
det ..BkBT
k 中的贡献为 1。而式 (3-3) 是对 |Bi|2 的全部组
合求和。因此 det ..BkBT
k 恰是 G 中不同树的数目。
例 3.3.2 求图 3.4 的树的数目。
解：任取一个基本关联矩阵，例如 B4，
B4 =2664
1 1 0 0 0
.1 0 .1 .1 0
0 0 0 1 .1
3775
所以 det ..B4BT
4 = det2664 2 .1 0
.1 3 .1
0 .1 2
3775
= 8
有时根据需要，还要计算 G 中不含或必含某特定边 e = (u，v) 的树的数目。如果不
含边 e，则 G′ = G . e 的树就与之一一对应，因此只需计算 G′ 的支撑树数目。如果必含
e = (u，v)。可以将顶点 u 和 v 收缩成一个顶点，记为 uv，得到 n . 1 个顶点的新图 G′，
原图 G 中某点 t 如果与 u( 或 v) 相邻，则在 G′ 中与顶点 uv 仍相邻，且方向不变。如果
t 与 u、v 都相邻，则 G′ 里 t 与 uv 之间存在 2 条有向边。这样，G′ 的树就与 G 中必含 e
的树一一对应。
例 3.3.3 求图 3.4 中不含 e4 的树数目。
· 64 ·
第 3 章 树
解：做 G . e4，得到图 3.5。
det ..B4BT
4 = det2664
2 .1 0
.1 2 0
0 0 1
3775
= 3
故 G 中不含 e4 的树有 3 棵。
例 3.3.4 求图 3.4中必含 e3 的树数目。
解：将顶点 v2、v4 收缩为 v2，4，得到图 3.6。
det ..B3BT
3 = det " 2 .2
.2 4 #= 4
故 G 中必含 e3 的树有 4 棵。
图 3.5 图 3.6
这 4 棵树显然分别由 {e1，e4}、{e1，e5}、{e2，e4}、{e2，e5} 构成。返回到图 G，再
分别加入 e3 就是 G 的树。
通过上述计算不难发现，C = BkBT
k 的元素 cij 十分易求，若 i = j，则 cij = d (vi)，
即 Bk 里 vi 所对应行中的非零元数目；若 i .= j，则 .cij 是图 G 中 (vi，vj) 或 (vj，vi)
形式的边数目。这对计算那些较难写出关联矩阵的图的树计数问题会带来方便。
3.3.2 无向连通图的树计数
无向连通图同样有其支撑树，但是它的关联矩阵 B 中不存在 .1 元素，因此不能直接
采用比内-柯西定理的方法进行树计算。对无向连通图 G 的每边任给一方向，便得到相应
的有向连通图 G′，显然 G′ 的树一定与 G 的树一一对应，这样无向连通图 G 的树计数问
题便迎刃而解了。
例 3.3.5 求完全图 kn 中不同树的数目。
解：对 kn 各边任给一方向，得到有向完全图 G，设 G 中顶点 vk 所对应的基本关联
矩阵是 Bk。于是可以得到
det ..BkBT
k = det2664
n . 1 .1 · · · .1
.1 n . 1 · · · .1
.1 .1 · · · n . 1
3775
= nn.2
· 65 ·
图论与代数结构（第 2 版）
3.3.3 有向连通图 G 根树的计数
定义 3.3.1 T 是有向树，若 T 中存在某顶点 v0 的负度为 0，其余顶点的负度为 1，
则称 T 是以 v0 为根的外向树，或称根树，用
.
T 表示。
例如图 3.7 就是一棵根树。树根 v0 所对应的基本关联矩阵是
B0 =266664
.1 0 1 1
0 0 .1 0
0 0 0 .1
0 .1 0 0
377775
由于 v0 的负度为 0，其余顶点的负度为 1，因此任何以 v0 为根的根树的基本关联矩阵 B0
中一定是每行每列都只有一个 .1 元素。如果对根树的顶点和边序号重新编号，使得每条
边 e = (vi，vj) 都满足 vi 的编号小于 vj 的编号，同时边 e = (vi，vj) 的编号为 ej。例如
图 3.7 的重新编号可以是图 3.8。
图 3.7 图 3.8
它的基本关联矩阵是
B′0
=266664
.1 0 0 0
0 .1 1 1
0 0 .1 0
0 0 0 .1
377775
事实上它只是对 B0 的行、列分别进行若干次初等变换的结果。它们的行列式是相等的。但
从 B′0
看出，它是一个上三角方阵，.1 元全是对角元。如果把矩阵中的 1 元改为 0，它的
行列式也不变。这正是根树的特征。如果 T 不是根树，它的基本关联矩阵绝不会有 B′0
的
形式。因此，如果把其中 1 元素改为 0，它的行列式将是 0。
令
.B
k 表示有向连通图 G 的基本关联矩阵 Bk 中将全部 1 元素改为 0 之后的矩阵。
我们有定理 3.3.3。
定理 3.3.3 有向连通图 G 中以 vk 为根的根树数目是 det .B
kBT
k 。
证明：由比内–柯西定理
det .B
kBT
k =Xi
.B
i
BT
i
· 66 ·
第 3 章 树
若
BT
i .= 0，说明这 n.1 条边构成 G 的一棵树，此时如果
.B
i .= 0，说明这棵树是
以 vk 为根的根树。这时
.B
i
=
BT
i
，因此它们在 det .B
kBT
k 中的贡献为 1，由于遍历
了所有 n . 1 条边的组合，所以 vk 为根的根树数目是 det .B
kBT
k 。
例 3.3.6 计算图 3.9 中以 v1 为根的根树数目。
解：v1 所对应的基本关联矩阵是
B1 = 264
.1 0 0 1 0 1
0 0 .1 0 .1 .1
0 .1 0 .1 1 0
375
.B
1BT
1 =264
.1 0 0 0 0 0
0 0 .1 0 .1 .1
0 .1 0 .1 0 0
375
26666666664
.1 0 0
0 0 .1
0 .1 0
1 0 .1
0 .1 1
1 .1 0
37777777775
=2664
1 0 0
.1 3 .1
.1 0 2
3775
所以 det .B
1BT
1 = 6
例 3.3.7 求图 3.9 以 v1 为根不含边 e5 的根树数目。
解：做 G′ = G . e，则 G′ 的以 v1 为根的根树数目正是所求，于是
B1 =2664
.1 0 0 1 1
0 0 .1 0 .1
0 .1 0 .1 0
3775
det .B
1BT
1 = det2664
1 0 0
.1 2 0
.1 0 2
3775
= 4
计算 G 中以 v0 为根必含某特定边 e = (u，v) 的根树数目，可以先计算以 v0 为根的
根树数，再计算不含 e 的根树数，其差即是。这里再介绍另一种计算方法。由于根树的特
征是任意一个非根的顶点 vi，其负度都是 1。如果要求根树必含 e = (u，v)，即
.
T 中顶点
v 的进入边已定，因而任何其他 (t，v) 形式的边都不会在根树中出现。所以可作 G′ = G.
{(t，v) | t .= u}，G′ 中以 v0 为根的根树数目即为所求。
· 67 ·
图论与代数结构（第 2 版）
注意：由于无法确定被收缩边的方向，故不能使用缩点的方法。
例 3.3.8 求图 3.9 以 v1 为根必含 e5 的根树数目。
解：做 G′ = G . e3 . e6，得图 3.10。
B1 =2664
.1 0 1 0
0 0 0 .1
0 .1 .1 1
3775
det .B
1BT
1 = det2664
1 0 0
0 1 .1
.1 0 2
3775
= 2
即 G 中有 2 棵以 v1 为根必含 e5 的根树。
图 3.9 图 3.10
3.4 回路矩阵与割集矩阵
有向连通图 G = (V ，E) 的回路矩阵与割集矩阵都与 G 的支撑树有密切关系，同时
在网络，特别是电路网络中有广泛的应用。
3.4.1 回路矩阵及其性质
设 T 是有向连通图 G = (V ，E) 的一棵支撑树，对任意的边 e ∈ E(G).E(T)，T +e
都构成了 G 的一个唯一回路 C，如果给回路 C 确定一个参考方向，那么该回路的边，如
果其方向与回路方向一致，就称它是正向边，否则称为反向边。
定义 3.4.1 有向连通图 G 的全部初级回路构成的矩阵，称为 G 的完全回路矩阵，
记为 Ce，它的元素是
cij =8>
><>
>:
1， ej ∈ Ci 且与回路 Ci 方向一致
.1， ej ∈ Ci 且与回路 Ci 方向相反
0， 其他
例 3.4.1 图 3.11的完全回路矩阵是
· 68 ·
第 3 章 树
Ce =
266666666666664
1 1 0 1 0 0
.1 0 1 0 .1 0
0 0 0 .1 1 1
0 1 1 0 0 1
0 1 1 1 .1 0
.1 0 1 .1 0 1
1 1 0 0 1 1
377777777777775
由于 k(1 . k . m . n + 1) 条余树枝可能与 T 构
图 3.11
成一个初级回路，因此完全回路矩阵 Ce 中最多可能包含
2m.n+1 . 1 个不同的初级回路。但是这些回路不一定都
是独立的。例如例 3.4.1 中 C1 ⊕C3 = C7。那么哪些回路
是独立的呢?
定义 3.4.2 当有向图 G = (V ，E) 的树 T 确定
以后，每条余树边 e 所对应的回路称为基本回路，该回
路的方向与 e 的方向一致。由全部基本回路构成的矩阵
称为 G 的基本回路矩阵，记为 Cf。
例 3.4.2 给定图 3.11的一棵树 T = {e1，e5，e6}，
则其基本回路矩阵是
Cf =264
375
1 1 0 0 1 1
.1 0 1 0 .1 0
0 0 0 1 .1 .1
e1 e2 e3 e4 e5 e6
显然基本回路矩阵中每个回路都是独立的，因此 rankCf = m.n+1。进而，如果将
Cf 的行、列分别进行一下交换，使树枝边放在后，余树边放在前且次序与它所构成的回路
一致，就可以写成分块矩阵形式，比如上例
Cf =264 375
1 0 0 1 1 1
0 1 0 .1 .1 0
0 0 1 0 .1 .1
e2 e3 e4 e1 e5 e6
亦即
Cf = I Cf12 其中，Cf12 是树枝边所对应的子阵。
定理 3.4.1 有向连通图 G = (V ，E) 的关联矩阵 B 和完全回路矩阵 Ce 的边次
序一致时，恒有
· 69 ·
图论与代数结构（第 2 版）
BCT
e = 0
证明：设 D = BCT
e ，dij =
m Xk=1
bik · cjk；其中 bik 是顶点 vi 与边 ek 的关联状况，cjk
是回路 Cj 与边 ek 的相关情况。回路 Cj 与顶点 vi 的相处只有两种可能。
(1) Cj 不经过 vi，如图 3.12(a) 所示，则与 vi 关联的任一边都不是 Cj 中的边，所以
dij = 0。
(2) Cj 经过 vi，如图 3.12(b) 所示，则必定经过与 vi 关联的 2 条边 ep 和 eq，若 ep 和
eq 在 Cj 中方向一致，则对 vi 来说它们是一进一出，因此 dij = 0；如果 ep 和 eq 在 Cj 中
方向相反，对 vi 它们却是同进同出，同样 dij = 0。
由于 dij 的任意性，故定理得证。
定理 3.4.2 有向连通图 G = (V ，E) 完
图 3.12
全回路矩阵 Ce 的秩是 m . n + 1。
证明：由于 Cf 是 Ce 的子阵且 rankCf =
m.n+1，故 rank Ce . m.n+1。现证 rankCe .
m.n+1，Sylvester 定理指出，两个矩阵 An×s 和
Bs×m，如果 AB = 0，则 rankA + rankB . s。
因此，由定理 3.4.1，得到 rankB + rankCe . m，
即 rankCe . m . n + 1。
定义 3.4.3 由连通图 G 中 m. n + 1 个互相独立的回路组成的矩阵，称为 G 的回
路矩阵。记为 C。
也就是说，只用 m . n + 1 个相互独立的回路就足以表示所有初级回路。回路矩阵在
完全回路矩阵的基础上只保留其中一小部分，但仍然可以通过回路矩阵中各行的组合得到
所有回路，这大大减少了完全回路矩阵的冗余信息。
R提示
在计算机存储与处理过程中，信息冗余是需要付出的必要成本代价，也是提升系
统鲁棒性的手段。
回路矩阵 C 有以下 3 个简单性质。
(1) 基本回路矩阵 Cf 是回路矩阵。
(2) BCT = 0（其中 B 与 C 的边次序一致）。
(3) C = PCf，其中 P 是非奇异的方阵，C 与 Cf 的边次序一致。
定理 3.4.3 连通图 G 的回路矩阵 C 的任一 m. n + 1 阶子阵行列式非零，当且
仅当这些列对应于 G 的某一棵余树。
证明：充分性。设已知 G 的某一棵余树 T，则可构造基本回路矩阵 Cf = (I Cf12)，
对给定的回路矩阵 C 进行列交换，使其与 Cf 的边次序一致，这样可写成块矩阵形式 C =
(C11 C12)，其中 C11 对应 T. 由性质 (3)，C = PCf，即 (C11 C12) = P (I Cf12) = (P
· 70 ·
第 3 章 树
PCf12 )，因此 C11 = P 是非奇异的，即其行列式非零。再证必要性。将 C 的这 m.n+1
列换到前面，成 C = (C11 C12)。现只需证 C12 对应 G 的一棵树。假设 C12 对应的不是
树，则一定含有回路，这种回路只由 C12 中的某些边构成。这样经过行变换可得
C′ = " C′11 C′12
0 C′′ 12 #
其中，C′′ 12 .= 0。于是
det (C11) = det " C′11
0 #= 0
与 detC11 .= 0 矛盾。
该定理揭示了 G 的余树与其回路矩阵之间的关系。
定理 3.4.4 若有向连通图 G = (V ，E) 的基本关联矩阵 Bk 和基本回路矩阵 Cf
的边次序一致，并设 Cf = (I Cf12) ，Bk = (B11 B12)，则
Cf12 = .BT
11B.T
12
证明：由定理 3.4.1 即得 BkCT
f = 0，写成块矩阵形式，有
(B11 B12) " I
CT
f12 #= 0
B12CT
f12 = .B11
由于 B12 对应的边构成 G 的一棵树。根据定理 3.2.6，B12 存在逆矩阵 B.1
12 。由此定理
得证。
本定理说明如果 Bk 已知，而且确定了一棵树，则可以直接经过计算求得 G 的基本回
路矩阵 Cf。
例 3.4.3 已知图 3.11 基本关联矩阵
B4 =264
375
1 .1 1 0 0 0
0 1 0 .1 0 .1
.1 0 0 1 1 0
e1 e2 e3 e4 e5 e6
其中，e1、e5、e6 所对应的子阵行列式非零，求 Cf。
解：由 e1、e5、e6 可构成 G 的一棵树。对 B4 进行列交换，得到
B4 =264
375
.1 1 0 1 0 0
1 0 .1 0 0 .1
0 0 1 .1 1 0
e2 e3 e4 e1 e5 e6
= B11 B12
· 71 ·
图论与代数结构（第 2 版）
其中
B11 =2664
.1 1 0
1 0 .1
0 0 1
3775
B12 =2664
1 0 0
0 0 .1
.1 1 0
3775
B.1
12 =2664
1 0 0
1 0 .1
0 1 0
3775
因此
Cf12 = .BT
11B.T
12 =264
1 1 1
.1 .1 0
0 .1 .1
375
即
Cf =24
35
1 0 0 1 1 1
0 1 0 .1 .1 0
0 0 1 0 .1 .1
e2 e3 e4 e1 e5 e6
3.4.2 割集矩阵及其性质
定义 3.4.4 设 S 是有向图 G = (V ，E) 的边子集，若
(1) G′ = (V ，E . S) 比 G 的连通支数多 1。
(2) 对任意 S′ . S，G 与 G′′ = (V ，E . S′) 的连通支数相同。则称 S 是 G 的一个
割集。
一般给割集 S 确定一个方向，称它是有向割集。这样 S 中的每条边 e，或者与 S 方
向一致，或者方向相反。
例 3.4.4 图 3.13 中，S1 = {e2，e3，e4} ，S2 = {e4，e5} 是割集，而 S3 = {e6，e7}
不是割集。在 S1 中，e2 与 S1 方向相同，而 e3 与 e4 方向相反。
图 3.13
定义 3.4.5 有向连通图 G 的全部割集组成的矩阵，称为完全割集矩阵，记作 Se。
其元素
· 72 ·
第 3 章 树
Sij =8>
><>
>:
1， ej 在Si 中且方向一致
.1， ej 在Si 中且方向相反
0， 其他
例 3.4.5 图 3.14 的完全割集矩阵是
Se =
2666666666666664
3777777777777775
1 .1 1 0 0 0
.1 0 0 .1 0 1
0 1 0 1 1 0
0 0 .1 0 .1 .1
.1 1 0 0 1 1
1 0 1 1 1 0
0 .1 1 .1 0 1
e1 e2 e3 e4 e5 e6 图 3.14
由于割集将连通图的顶点划分成连通的两部分，其顶点数分别为 i，n . i，1 . i . n . 1。
因此 G 最多有
1
2
(2n . 2) = 2n.1 .1 个不同的割集。但这些割集不一定都是独立的，例如
上例中 S7 = S1 ⊕ S2。
定义 3.4.6 设 T 是连通图 G 的一棵树，ei 是一个树枝。对应 ei 存在 G 的割集 Si，
Si 只包括一条树枝边 ei 及某些余树枝，且与 ei 的方向一致。这时称 Si 为 G 的对应树 T
的一个基本割集。
定义 3.4.7 给定有向连通图 G 的一棵树 T，则由全部基本割集组成的矩阵称为基
本割集矩阵。记为 Sf。
例 3.4.6 T = {e2，e3，e4} 是图 3.14的一棵树，其基本割集矩阵是
Sf =264
375
.1 1 0 0 1 1
0 0 1 0 1 1
1 0 0 1 0 .1
e1 e2 e3 e4 e5 e6
在基本割集矩阵中如果把余树边对应的列放在前，树枝边对应的列放在后且与割集次
序一致，例如上例中
Sf =264
375
.1 1 1 1 0 0
0 1 1 0 1 0
1 0 .1 0 0 1
e1 e5 e6 e2 e3 e4
· 73 ·
图论与代数结构（第 2 版）
则基本割集矩阵可写成分块矩阵形式 Sf = (Sf11 I)，其中单位矩阵对应一棵树。显然
rank Sf = n . 1。
定理 3.4.5 当有向连通图 G 的完全回路矩阵 Ce 和完全割集矩阵 Se 的边次序一
致时，有 SeCT
e = 0。
证明：设 D = SeCT
e ，dij =
m Xk=1
sik · cjk。其中，sik 是第 i 个割集的第 k 条边，cjk 是
第 j 个回路的第 k 条边。割集 Si 与回路 Cj 的相处只有两种。
(1) Si 与 Cj 不相交，即 Cj 中的边在 Si 中不出现，自然 dij = 0。
(2) Si 与 Cj 相交，显然它们有偶数条共同的边，如图 3.15(b) 所示，其中相邻两条边
ep 和 eq 组成一对，如果它们在 Si 中方向一致，则在 Cj 中方向相反，反之亦然。因此，
dij = 0。
图 3.15
由 dij 的任意性，定理得证。
定理 3.4.6 连通图 G 的完全割集矩阵 Se 的秩是 n . 1。
证明：由于 Sf 是 Se 的子矩阵，而 rank Sf = n . 1，因此 rankSe . n . 1。又由定
理 3.4.5，SeCT
e = 0，根据 Sylvester 定理，rankSe + rankCe . m，故 rank Se . n . 1。
因此，rank Se = n . 1。
定义 3.4.8 连通图 G 的 n . 1 个互相独立的割集构成的矩阵称为 G 的割集矩阵。
记为 S。
割集矩阵 S 有以下简单性质。
(1) 基本割集矩阵 Sf 是割集矩阵。
(2) SCT = 0，S 和 C 的边次序一致。
(3) S = PSf，其中 P 是非奇异方阵，S 与 Sf 的边次序一致。
定理 3.4.7 连通图 G = (V ，E) 的割集矩阵 S 的任一 n . 1 阶子阵行列式非零，
当且仅当这些列对应于 G 的某棵树。
证明：充分性。设已知 G 的某棵树 T，则可构造基本割集矩阵 Sf = (Sf11 I)。对给
定的割集矩阵 S 进行列交换，使其与 Sf 的边次序一致，于是可写成分块矩阵形式 S =
(S11 S12)，其中 S12 对应树 T。由性质 (3)，S = PSf，即 (S11 S12) = P (Sf11 I) =
(PSf11 P)。因此，S12 = P，是非奇异的，即其行列式非零。必要性。调整 S 的这 n.1
· 74 ·
第 3 章 树
列构成 S12，使 S = (S11 S12)。假定 S12 的各列对应的不是树，则一定含有 l(< n) 条边
的初级回路 C. 由于 C 是 G 的连通子图，因此 C 的割集矩阵的秩是 l . 1，亦即 S12 对
应的这 l 列线性相关，故 |S12| = 0，矛盾。
定理 3.4.8 设 Sf 和 Cf 分别是连通图 G 中关于某棵树 T 的基本割集矩阵和基
本回路矩阵，且边次序一致。并设 Sf = (Sf11 I) ，Cf = (I Cf12)，则 Sf11 = .CT
f12
。
证明：由定理 3.4.5，有
SfCT
f = 0
(Sf11 I) " I
CT
f12 #= 0
故得证。
推论 3.4.1 当连通图 G 的基本割集矩阵与基本关联矩阵的边次序一致时，有
Sf11 = B.1
12 B11
例 3.4.7 已知图 3.15的基本关联矩阵
B1 =2664
3775
.1 0 0 .1 0 1
0 1 0 1 1 0
0 0 .1 0 .1 .1
e1 e2 e3 e4 e5 e6
其中，{e2，e3，e4} 构成 G 的树，求对应的基本割集矩阵。
解：对 B1 的列重新调整如下：
B1 =2664
3775
.1 0 1 0 0 .1
0 1 0 1 0 1
0 .1 .1 0 .1 0
e1 e5 e6 e2 e3 e4
B11 =2664
.1 0 1
0 1 0
0 .1 .1
3775
B12 =2664
0 0 .1
1 0 1
0 .1 0
3775
B.1
12 =2664
1 1 0
0 0 .1
.1 0 0
3775
所以
Sf = ..B.1
12 B11 I) =2664
3775
.1 1 1 1 0 0
0 1 1 0 1 0
1 0 .1 0 0 1
e1 e5 e6 e2 e3 e4
· 75 ·
图论与代数结构（第 2 版）
3.5 Huffman 树
首先介绍最优二叉树。
定义 3.5.1 除树叶外，其余顶点的正度最多为 2 的外向树称为二叉树。如果它们的
正度都是 2，称为完全二叉树。
例如图 3.16 是一棵完全二叉树，v0 是根，每条有向边的方向都是朝下的。如果二叉树
T 的每个树叶顶点 vi 都分别赋以一个正实数 wi，则称 T 是赋权二叉树。从根到树叶 vi 的
路径 P (v0，vi) 所包含的边数计为该路径的长度 li，这样二叉树 T 带权的路径总长是
WPL =Xi
liwi，vi是树叶
反过来，如果给定了树叶数目以及它们的权值，可以构造许多不同的赋权二叉树。在
这些赋权二叉树中，必定存在路径总长最小的二叉树，这样的树称为最优二叉树。
例 3.5.1 已知英文字符串 adacatedecade。试用二进制字符串代替某个字母，并保证
该英文字符串与二进制串构成一一对应。
解：该字符串中有字母 a、d、e、c、t，它们分别出现 4、3、3、2、1 次。令每个字母
对应二叉树的一个树叶，根到树叶的路径是唯一的，而且这条路径绝不会是根到另一个树
叶路径的一部分。这样根到树叶的路径与该字母构成一一对应。如果在树 T 中令向左的边
为 0，向右的边为 1。那么这些路径又与二进制串构成了一一对应。
例如令 d、a、e、c、t 分别对应图 3.16中的 v3、v5、v6、v7、v8，则 d ← 00，a ← 010，e ←
011，c ← 10，t ← 11。该英文字符串对应 010000101001011011000111001000011。
如果字母与树叶的对应情况如图 3.17所示，即 a ← 00，t ← 010，c ← 011，e ← 10，
d ← 11，则对应字符串是 00110001100010101110011001110。这两种情况下字符串的总长
分别是 33 和 29。
图 3.16 图 3.17
给定了 n 个树叶的权值，如何构造带权路径总长最短的最优二叉树呢? 哈夫曼给出了
一个算法。由该算法得到的二叉树称为 Huffman 树。
算法描述如下。
· 76 ·
第 3 章 树
a. 对 n(. 2) 个权值进行排序，满足
wi1 . wi2 . · · · . win
b. 计算 wi = wi1 + wi2 作为中间顶点 vi 的权，vi 的左儿子是 vi1，右儿子是 vi2。在
权序列中删去 wi1 和 wi2，加入 wi，n ← n . 1。若 n = 1，结束；否则转 a。
例 3.5.2 权序列为 (4，3，3，2，1) 的 Huffman 树的构造过程如图 3.18所示。
图 3.18
算法的计算复杂性主要取决于步骤 a，而且是 n 个权值的第一次排序，它一般需进行
n log n 次比较。之后每当产生 wi 时，只需在新序列中进行插入运算，其复杂性是 log n，由
于总共只进行 n . 2 次迭代，因此整个算法的计算复杂性是 O(n log n)。
定理 3.5.1 由 Huffman 算法得到的二叉树是最优二叉树。
证明：假定 n . 3，w1 . w2 . · · · . wn，并设 T 是最优树，则一定有 l1 = max
i {li}；
否则，若 wk > w1 而 lk < l1。那么将 wk 与 w1 对调得到 T′。有 WPL (T′).WPL(T) < 0，
与 T 最优矛盾。于是可得到结论：只要 T 是最优树，w1 就一定离根最远。同时立即可知，
w1 必有兄弟。否则让 w1 赋值给该树叶的父亲顶点，就可得到路径总长更小的树。由于 w2
是序列中次最小的权，故可令 w1 的兄弟是 w2。因此，分枝 w1 +w2 (见图 3.19) 可以是最
优树 T 的子图。
设 Tn 是 n 个树叶的最优树，收缩分枝 w1 +w2 后是对应的 n.1 个树叶的 T′n
.1，如
图 3.20 所示。
图 3.19 图 3.20
在 n . 1 个权 (其中之一是 w1 + w2 ) 时，亦有其最优二叉树 Tn.1，然后将 w1 + w2
分枝展开后又得到有 n 个权的二叉树 T′n
，如图 3.21所示。
· 77 ·
图论与代数结构（第 2 版）
因为 Tn 和 Tn.1 分别是最优树，所以 WPL (Tn) . WPL (T′n
) ， WPL (Tn.1) .
WPL ..T′n
.1。由于
WPL ..T′n
.1= WPL (Tn) . (w1 + w2)
WPL (Tn.1) = WPL (T′n
) . (w1 + w2)
可得 WPL ..T′n
.1. WPL (Tn.1)。亦即 T′n
.1 和 T′n
都是最优树。
图 3.21
当算法执行到 n = 2 时，自然是一棵最优树。再与分枝收缩的过程相反进行展开，最
后得到的 T′n
一定是最优二叉树。
3.6 最 短 树
在赋权连通图中，有时需要计算其总长最小或最大的支撑树。这就是最短树和最长树
问题。例如要在若干加油站之间铺设输油管道，已知任意两个加油站之间输油管道的铺设
费用，如果让每个站都能保证油的供应，那么最少的建造费用就应该是计算它的最短树。
以下介绍关于赋权连通图 G 最短树的两个好算法：Kruskal 算法和 Prim 算法。
3.6.1 Kruskal 算法
Kruskal 算法的描述如下。
1. T ← Φ
2. while |T| . n . 1 且 E .= Φ do
begin
3. e←E 中最短边
4. E ← E . e
5. 若 T + e 无回路，则 T ← T + e
end
6. 若 |T| < n . 1 打印“非连通”，否则输出最短树
该算法的思路是不断往 T 中加入当前的最短边 e，如果增加这条边会构成回路，则无
法构成树，删之，直至最后达到 n . 1 条边为止。这时 T 中不包含任何回路，因此是树。
· 78 ·