返回：0100 离散数学课程总目录 · 上一章：0107 欧拉图与哈密顿图 · 下一章：0109 图的矩阵表示

1、资料来源与学习目标

本章对应北大离散数学刘田老师“集合论与图论”第八章。Auto_Tutor 中整理到的资料包括：

资料 内容
8.1 树 树、森林、树叶、分支点、树的六个等价定义、生成树、基本回路、基本割集、生成树计数、Cayley 公式
008 习题与答案 习题 9.2、9.6、9.11，重点考察握手定理、树的边数、森林边数上界、最大度与树叶数量

本章的核心目标：掌握树 = 连通 + 无圈这条主线，并能在“连通、无圈、边数 n-1、唯一路径、极小连通、极大无圈”之间自由切换。

2、颜色标注

颜色 含义
粉色 必背、必会证明、后续章节反复使用
蓝色 核心术语和定义
橙色 易错点、边界条件
绿色 理解提示和后续连接

3、章节主线

模块 本章要会什么 后续连接
树与森林 会用连通性和圈判定树/森林 图论基础
等价定义 会在六种树定义之间转换 证明题
树叶 会用握手定理证明非平凡树至少两片叶 结构计数
生成树 会用破圈法从连通图中取生成树 网络骨架
基本回路 每条弦加回生成树得到唯一回路 回路空间
基本割集 每条树枝删去得到唯一割集 割集空间
生成树计数 会用删除-收缩公式和 Cayley 公式 组合计数

4、树与森林

树：

1
连通无回图。

常用 T 表示树。

树叶：

1
树中 1 度顶点。

分支点：

1
树中 2 度以上顶点。

平凡树：

1
平凡图 K_1；它没有树叶，也没有分支点。

森林：

1
无回图。

森林的每个连通分支都是树。

树是“连通的森林”；森林允许不连通。做题时看到“无圈”还不够，要看是否给了连通条件。

5、树的等价定义

定理 9.1：设 G=<V,E> 是 n 阶 m 边无向图，则以下六个命题等价：

1
2
3
4
5
6
(1) G 是树，即连通无回。
(2) G 中任何两个顶点之间有唯一路径。
(3) G 无圈，且 m=n-1。
(4) G 连通，且 m=n-1。
(5) G 极小连通：G 连通，且所有边都是桥。
(6) G 极大无回：G 无圈，且增加任何新边都会产生唯一圈。

这六条可以按链式证明：

1
(1)⇒(2)⇒(3)⇒(4)⇒(5)⇒(6)⇒(1)

5.1 从树到唯一路径

若 G 是树，则 G 连通，所以任意两点之间至少有路径。

如果两点之间有两条不同路径，把它们合起来就能得到一个回路，与“无回”矛盾。因此路径唯一。

5.2 唯一路径推出无圈与边数

唯一路径推出无圈：

1
若有圈，则圈上任意两个不同顶点之间至少有两条路径。

边数 m=n-1 可用归纳证明。n=1 时 m=0。当 n=k+1 时，任选一条边 e，删去后 G-e 有两个连通分支；若两边分别有：

1
2
n_1,m_1
n_2,m_2

则：

1
m=m_1+m_2+1=(n_1-1)+(n_2-1)+1=n_1+n_2-1=n-1

5.3 无圈加边数推出连通

若 G 无圈，且 m=n-1。设 G 有 s 个连通分支，每个分支都是树。于是：

1
2
m=(n_1-1)+(n_2-1)+...+(n_s-1)
 =n-s

又 m=n-1，所以：

1
2
n-s=n-1
s=1

因此 G 连通。

5.4 连通加边数推出所有边都是桥

若 G 连通且 m=n-1，任取一条边 e。若 G-e 仍连通，则它是 n 阶 n-2 边连通图，但连通图至少有 n-1 条边，矛盾。

所以每条边都是桥。

5.5 极小连通推出极大无回

若所有边都是桥，则任何边都不在圈上，所以 G 无圈。

又因为 G 连通，任意不相邻两点 u,v 之间有唯一路径 P(u,v)。加上新边 (u,v) 后：

1
P(u,v)∪{(u,v)}

形成唯一圈。

5.6 极大无回推出树

若 G 无圈，且增加任意新边都会产生唯一圈。任取两点 u,v，加边 (u,v) 后产生的圈去掉这条新边，剩下的就是 u 到 v 的路径。因此 G 连通。

所以 G 连通且无圈，是树。

考试里最常用的三角关系是：树 ⇔ 连通且 m=n-1 ⇔ 无圈且 m=n-1。看到其中任意两项，就可以推出第三项。

6、树叶与度数公式

定理 9.2：

1
非平凡树至少有 2 个树叶。

证明：设树 T 有 n 个顶点、m 条边、x 个树叶。树有：

1
m=n-1

由握手定理：

1
sum d(v)=2m=2(n-1)=2n-2

树叶贡献 x，其余 n-x 个顶点度数至少为 2，所以：

1
sum d(v) ≥ x+2(n-x)=2n-x

于是：

1
2
2n-2 ≥ 2n-x
x≥2

树叶证明的常用套路：一边用 2m=2n-2，另一边用“树叶度数为 1，非树叶度数至少为 2”做下界。

更一般地，如果树中各类顶点数量已知，可以用：

1
sum d(v)=2(n-1)

直接列方程。

7、树的计数与枚举

设：

1
t_n = n 阶非同构无向树的个数。

前几项：

n t_n
1 1
2 1
3 1
4 2
5 3
6 6
7 11
8 23
9 47
10 106

星图：

1
S_n=K_{1,n-1}

它是一棵中心度数为 n-1、其余顶点都是树叶的树。

非同构树的枚举通常先按度数列分组，再按直径、分支位置继续细分。只看度数列不一定能区分所有非同构树。

8、生成树

8.1 生成树、树枝与弦

生成树：

1
T⊆G，V(T)=V(G)，且 T 是树。

设 G 是 n 阶 m 边无向连通图，T 是 G 的生成树。

树枝：

1
2
e∈E(T)
共有 n-1 条。

弦：

1
2
e∈E(G)-E(T)
共有 m-n+1 条。

余树：

1
G[E(G)-E(T)]

也就是由所有弦导出的子图。

Auto_Tutor 的 OCR 把一处“弦/余树边数 m-n+1”混到了生成树上。正确结论是：生成树边数为 n-1，弦数为 m-n+1。

8.2 连通图存在生成树

定理 9.3：

1
无向图 G 连通 ⇔ G 有生成树。

证明：

方向 思路
有生成树⇒连通 生成树是连通生成子图，所以原图连通
连通⇒有生成树 破圈法：若有圈，就删去圈上一条边，连通性不变；重复到无圈为止

破圈法：

1
2
3
4
连通图 G 若不是树，就含圈。
删去某个圈上的一条边，图仍连通。
不断删圈边，直到无圈。
最终得到连通无圈的生成子图，即生成树。

8.3 生成树的三个常用结论

结论 1：

1
n 阶 m 边无向连通图满足 m≥n-1。

结论 2：

1
2
T 是 n 阶 m 边无向连通图 G 的生成树
⇒ |E(T)|=n-1，弦数为 m-n+1。

结论 3：

1
2
T 是无向连通图 G 的生成树，C 是 G 中的圈
⇒ (E(G)-E(T))∩E(C)≠∅。

更常用的说法是：

1
任何一个圈中至少含有一条弦。

因为如果某个圈的所有边都在 T 中，则 T 内含圈，违背树的定义。

定理 9.13：

1
2
设 T 是连通图 G 的生成树，S 是 G 中的割集，
则 E(T)∩S≠∅。

证明思路：若 E(T)∩S=∅，则删去割集 S 后，生成树 T 仍完整地保留在 G-S 中，所以 G-S 仍连通，矛盾。

9、基本回路与基本割集

9.1 基本回路

设 G 是 n 阶 m 边无向连通图，T 是 G 的生成树。若 e 是 T 的弦，则：

1
T∪{e}

中存在唯一一个由弦 e 和若干树枝组成的圈。

这个圈称为弦 e 对应的基本回路。

不同的弦对应不同的基本回路，因此基本回路系统有：

1
m-n+1

个基本回路。

圈秩：

1
ξ(G)=m-n+1

9.2 基本割集

若 e 是生成树 T 的树枝，则删去 e 后，T-e 分成两个连通分支 T_1,T_2。在原图 G 中，所有跨越这两个分支的边构成一个割集：

1
S_e=E(G)∩(V(T_1)&V(T_2))

这个割集由树枝 e 和若干弦组成，称为树枝 e 对应的基本割集。

不同的树枝对应不同的基本割集，因此基本割集系统有：

1
n-1

个基本割集。

割集秩：

1
η(G)=n-1

一条弦加回生成树，会制造一个唯一圈；一条树枝从生成树中删掉，会制造一个唯一割集。这是基本回路和基本割集的对偶记忆法。

10、生成树计数

设：

1
τ(G)=标定图 G 的生成树个数。

删除-收缩公式：

1
若 e 不是环，则 τ(G)=τ(G-e)+τ(G\e)。

含义：

类型 对应数量
不含 e 的生成树 τ(G-e)
含 e 的生成树 τ(G\e)

Cayley 公式：

1
n≥2 ⇒ τ(K_n)=n^{n-2}

证明思路是 Prüfer 序列：

1
2
3
标号为 {1,2,...,n} 的生成树
↔
长度为 n-2 的序列

每个位置有 n 种选择，所以共有：

1
n^{n-2}

棵标定树。

11、习题与答案

习题 9.2：树叶和度数列

题目：无向树 T 有 9 片树叶，3 个 3 度顶点，其余顶点的度数均为 4。问 T 中有几个 4 度顶点？根据 T 的度序列，你能画出多少棵非同构的无向树？

答案：

1
2
T 中有 2 个 4 度顶点。
共有 14 棵非同构的无向树。

设有 x 个 4 度顶点，则顶点数：

1
n=x+9+3=x+12

树有：

1
m=n-1=x+11

由握手定理：

1
2m = 2x+22

另一方面，按度数求和：

1
sum d(v)=9×1+3×3+4x=18+4x

所以：

1
2
2x+22=18+4x
x=2

于是 T 是 14 阶树，度序列为：

1
1,1,1,1,1,1,1,1,1,3,3,3,4,4

按答案图给出的分类：

1
2
3
4
直径为 6 的树：6 种
直径为 5 的树：7 种
直径为 4 的树：1 种
合计：14 种

习题 9.6：图或补图必含圈

题目：设 G 为 n≥5 阶简单图，证明 G 或 Ḡ 必含圈。

证明：设 G 的边数为 m，补图 Ḡ 的边数为 m'。由于：

1
m+m'=C(n,2)=n(n-1)/2

所以 m,m' 中至少有一个不小于一半：

1
max(m,m') ≥ n(n-1)/4

因为 n≥5，所以：

1
n(n-1)/4 ≥ n

于是 G 或 Ḡ 中至少有一个图边数不小于 n。

但一个 n 阶无圈图是森林。若森林有 s≥1 个连通分支，则：

1
m_forest = n-s ≤ n-1

因此任何 n 阶边数至少为 n 的图必含圈。

所以 G 或 Ḡ 必含圈。

习题 9.11：最大度推出树叶数量

题目：设 T 为非平凡的无向树，Δ(T)≥k，证明 T 至少有 k 片树叶。

证明：若 k=0 或 k=1，结论显然。下面设 k≥2。

由 Δ(T)≥k，存在顶点 v 满足：

1
d_T(v)=Δ(T)≥k

删除顶点 v 后，树 T-v 至少产生 k 个连通分支：

1
T_1,T_2,...,T_k,...

因为树中连接不同分支的唯一通道都经过 v。

对每个连通分支 T_i：

  1. 若 T_i 是平凡树，则它唯一的顶点在原树 T 中是树叶。
  2. 若 T_i 非平凡，则 T_i 至少有两片树叶，其中至少有一片不是与 v 相邻的那个端点，因此也是原树 T 的树叶。

所以每个分支至少能贡献一片 T 的树叶。分支数至少为 k，故 T 至少有 k 片树叶。

12、复盘清单

  1. 树就是连通无圈图。
  2. 森林就是无圈图，每个连通分支都是树。
  3. n 阶树一定有 n-1 条边。
  4. 连通且 m=n-1 可以推出树。
  5. 无圈且 m=n-1 也可以推出树。
  6. 树中任意两点之间有唯一路径。
  7. 非平凡树至少有两片树叶。
  8. 连通图一定有生成树，生成树有 n-1 条树枝。
  9. 弦数为 m-n+1，每条弦对应一个基本回路。
  10. 树枝数为 n-1，每条树枝对应一个基本割集。
  11. 删除-收缩公式：τ(G)=τ(G-e)+τ(G\e)。
  12. Cayley 公式：τ(K_n)=n^{n-2}。

13、下一步

第九章进入图的矩阵表示。复习第八章时，先把树的六个等价定义背熟，再练习用 sum d(v)=2(n-1) 处理树叶和度数列题。