Bóna · 枚举与解析组合学导论 · 第 5 章 图的计数

5.1　树与森林Trees and forests

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

在本节中，我们将对那些顶点集（vertex set）为 \([n]=\{1,2,\dots,n\}\) 的树（tree）以及其他图进行计数。

本节目标先把“树”这个对象讲清楚：它其实有三种互相等价的说法——“去掉任意一条边就不再连通”“没有圈”“\(n\) 个顶点恰有 \(n-1\) 条边”。本节先证明这三种说法描述的是同一类图，再给出树、森林（forest）、叶子（leaf）的正式定义。这是后面对树进行计数的出发点。

5.1.1　树

在搭建任何一种网络时，连通（connected）当然是一条非常值得拥有的性质，但它本身是有代价的。因此，研究那些既连通、又没有任何“冗余”的图，就成了一个自然的研究方向。为了把这个想法说得更精确，我们称一个图 \(G\) 是极小连通的（minimally connected），如果 \(G\) 是连通的，但只要删去 \(G\) 的任意一条边，\(G\) 就不再连通。正如我们前面提到过的，图 5.1 中的图 \(B\) 就是极小连通的。

图 A：连通但有冗余 删一条圈上的边仍连通 图 B：极小连通（树） 删任意一条边都断成两块 圈 C 出发点 = 终点，中途不重复
图 A 含一个圈，圈上任一条边都是“多余”的（删掉后仍连通）；图 B 没有冗余，删任何一条边都会断开，这就是极小连通；右侧是“圈”的样子。

极小连通的图在图论中扮演着核心角色。为了理解它们的重要性，我们证明下面的引理；它为同一个概念提供了三种等价的定义。请注意这三种定义是多么简单而自然。我们把圈（cycle）定义为一条起点与终点相同、但除此之外没有重复顶点的途径（walk）。例如，图 5.1 中的 \(C_1\) 与 \(C_2\) 都是圈。

引理 5.3设 \(G\) 是一个有 \(n\) 个顶点的连通简单图（connected simple graph）。则以下三条等价：
  1. 图 \(G\) 是极小连通的；
  2. \(G\) 中没有圈；
  3. \(G\) 恰好有 \(n-1\) 条边。
“三条等价”是什么意思“等价”指：在 \(G\) 连通的前提下，这三句话要么同时成立、要么同时不成立。证明的办法是绕成一个圈：先证 (i)\(\Rightarrow\)(ii)，再 (ii)\(\Rightarrow\)(iii)，最后 (iii)\(\Rightarrow\)(i)。这样从任意一条出发都能推到其余两条。
证明.

(i)\(\Rightarrow\)(ii)　假设 \(G\) 中存在一个圈 \(C\)。那么 \(G\) 就不可能是极小连通的：因为 \(C\) 上的任意一条边 \(e\) 都可以被删去，删去后所得的图仍然连通。事实上，若原来从 \(u\) 到 \(v\) 的某条路径用到了边 \(e\)，那么仍存在一条从 \(u\) 到 \(v\) 的途径——只要把边 \(e\) 替换成圈 \(C\) 上其余那些（不等于 \(e\) 的）边即可。

(ii)\(\Rightarrow\)(iii)　在 \(G\) 中任取一个顶点 \(x\)，朝某个方向开始行走，并且绝不重复经过任何顶点。由于 \(G\) 中没有圈，我们最终一定会“走到尽头”，也就是会碰到一个度（degree）为 \(1\) 的顶点。这说明：一个没有圈的连通简单图必含有一个度为 \(1\) 的顶点。把这样一个顶点（连同与它相连的那条唯一的边）从 \(G\) 中删去，就得到一个图 \(G^{*}\)，它比 \(G\) 少一个顶点、少一条边。于是命题可对 \(n\) 用归纳法证明。

(iii)\(\Rightarrow\)(i)　这一条是说：若 \(n\) 个顶点的简单图连通且有 \(n-1\) 条边，则它是极小连通的；换句话说，\(n\) 个顶点、\(n-2\) 条边的图不可能连通。假设这不成立，并取一个顶点数最少的反例 \(H\)（请读者自行验证：为此 \(H\) 必须多于三个顶点）。由于 \(H\) 有 \(n-2\) 条边，其中必有一个度为 \(1\) 的顶点 \(y\)；否则 \(H\) 至少要有 \(n\) 条边（因为这时所有顶点的度之和将至少为 \(2n\)）。把 \(y\) 从 \(H\) 中删去，我们就得到了一个顶点数更少的反例，与“\(H\) 是最小反例”矛盾。♦

例：用一棵 5 顶点的树核对引理取顶点集 \([5]=\{1,2,3,4,5\}\)，边为 \(\{1\text{–}2,\;2\text{–}3,\;2\text{–}4,\;4\text{–}5\}\)。
  1. 数边：共 \(4\) 条边，而 \(n=5\)，恰好 \(4=n-1\)，满足 (iii)。
  2. 找圈：从任意点出发都走不出一条“绕回起点又不重复”的路，没有圈，满足 (ii)。
  3. 删边试连通：删掉 \(2\text{–}4\)，则 \(\{1,2,3\}\) 与 \(\{4,5\}\) 被切成两块，不再连通；其余每条边删掉也都会断。所以是极小连通，满足 (i)。
  4. 三条同时成立，与引理一致。
无圈连通图 G 度=1 ⟶ 删去叶子与其边 G* 少 1 点少 1 边
(ii)\(\Rightarrow\)(iii) 与 (iii)\(\Rightarrow\)(i) 的共同手法：无圈连通图里一定有度为 \(1\) 的顶点，删掉它（及其唯一的边）后顶点数与边数各减一，于是可以对 \(n\) 做归纳。
为什么“没有度 1 的点就至少有 \(n\) 条边”这是 (iii)\(\Rightarrow\)(i) 里关键的一步，用到第 5 章前面讲过的握手引理：所有顶点的度之和等于边数的 \(2\) 倍。
  1. 若每个顶点的度都 \(\ge 2\)，则度之和 \(\ge 2n\)。
  2. 度之和 \(=2\times(\text{边数})\)，于是 \(2\times(\text{边数})\ge 2n\)，即边数 \(\ge n\)。
  3. 但反例 \(H\) 只有 \(n-2\) 条边 \(

满足引理 5.3 中那些等价条件的图，在图论中具有核心地位。因此，它们拥有自己专属的名字。

定义 5.4一个极小连通的简单图称为树（tree）。
等价地，一个连通且无圈的简单图称为树。
等价地，一个有 \(n\) 个顶点、连通且恰有 \(n-1\) 条边的简单图称为树。

一个图，如果它的每个连通分支（connected component）都是树，那么——并不意外地——它被称为森林（forest）。不同的树看上去可以差别很大，参见图 5.6 的一些例子。

一个森林 = 若干棵互不相连的树 树① 树②（星形） 树③ 树④（单顶点也是树） 树⑤（一条边）
森林是“若干棵树的不相交并”。上图中五个连通分支各自都是树，合在一起就是一个森林。注意单个顶点（没有边）也满足“连通且 \(n-1=0\) 条边”，因此它是一棵树。

在引理 5.3 的证明中，我们谈到了树里度为 \(1\) 的顶点。这样的顶点将被称为叶子（leaf，复数 leaves）。因此，我们在那条证明第二部分里的论证表明：每一棵树都至少有一片叶子。这个结论还可以被大大加强，相关方向的一些问题见补充习题 4 与习题 5。

例：数叶子仍取前面 \([5]\) 上的那棵树，边为 \(\{1\text{–}2,\;2\text{–}3,\;2\text{–}4,\;4\text{–}5\}\)。逐个看各顶点的度：
  1. 顶点 \(1\)：只与 \(2\) 相连，度 \(=1\)，是叶子。
  2. 顶点 \(2\)：与 \(1,3,4\) 相连，度 \(=3\)，不是叶子。
  3. 顶点 \(3\)：只与 \(2\) 相连，度 \(=1\)，是叶子。
  4. 顶点 \(4\)：与 \(2,5\) 相连，度 \(=2\)，不是叶子。
  5. 顶点 \(5\)：只与 \(4\) 相连，度 \(=1\)，是叶子。
共有 \(3\) 片叶子（顶点 \(1,3,5\)），印证了“树至少有一片叶子”——事实上一棵有边的树至少有两片叶子。

返回 全书目录