集合与图论学习笔记08

定义

定义 8.1 树

一个联通无回路的图称为树

树种中度数为 \(1\) 的顶点称为树叶

度数大于 \(1\) 的顶点称为分枝点或内点

定理 8.1.1 树的等价定义

\(T\) 有 \(n\) 个顶点，以下 \(6\) 中定义等价：

• \(T\) 是无回路的连通图
• \(T\) 是无回路图，并且 \(e=n-1\)，其中 \(e\) 是边数
• \(T\) 是连通图，并且 \(e=n-1\)
• \(T\) 是无回路图，并且在 \(T\) 的任何两个不相邻的顶点之间添加一边，恰得一条回路（也称 \(T\) 的最大无回路图）
• \(T\) 是连通图，但删去人一条边后，便不连通（也称 \(T\) 为最小连通图）
• \(T\) 的每一对不同顶点之间有唯一的一条路

证明： 点击查看证明

\((1)\rightarrow(2)\) 对 \(n\) 进行归纳：\(n=1\) 显然，当 \(n=k+1\) 时。\(T\) 是无回路的连通图，所以 \(e \ge k\)，若 \(e \ge k+1\)，则由抽屉定理，至少存在一个度数为 \(1\) 的顶点 \(v\)

删去 \(v\)，此时 \(T-\{v\}\) 至少有 \(k\) 条边，与归纳假设矛盾，故 \(e=k\)

\((2)\rightarrow(3)\) 假设 \(T\) 不连通，则由 \(k\) 个连通分支 \(T_1,T_2,...T_k\)，这几个连通分支都是无回路的连通图，所以他们都是树，累加有 \(e=n-k\) 矛盾！

\((3)\rightarrow(4)\) 首先证明 \(T\) 无回路：\(n=1,2\) 时显然，假设 \(n=k-1\) 时成立，当 \(n=k\) 时，至少有一个顶点 \(v\) 的度数为 \(1\)，删去 \(v\) 和与 \(v\) 相连的边，得到 \(T'\)，由归纳假设 \(T'\) 无回路，所以 \(T\) 也无回路

其次证明在 \(T\) 的任何两个不相邻的顶点之间添加一条边，恰得一条回路：设 \(u,v\) 是 \(T\) 中的两个不相邻的顶点，在 \(u,v\) 之间添加一条边 \(e\)，则 \(T+e\) 有 \(n\) 个顶点和 \(n\) 条边，故 \(T+e\) 中至少有一个回路，若有两个回路，则删去 \(e\) 后，\(T\) 中仍有回路，与 \(T\) 无回路矛盾，故 \(T+e\) 恰有一个回路

\((4)\rightarrow(5)\) 设 \(e\) 是 \(T\) 的任意一条边，删去 \(e\) 后，若 \(T-e\) 连通，则在 \(T-e\) 的两个端点之间添加一条边，仍然得到一个回路，与 (4) 矛盾，故 \(T-e\) 不连通，若 \(T\) 不连通，则在 \(T\) 的两个不连通的顶点之间添加一条边，仍然得不到回路，与 (4) 矛盾，故 \(T\) 连通

\((5)\rightarrow(6)\) 设 \(u,v\) 是 \(T\) 中的任意两个不同顶点，\(u,v\) 之间至少有一条路，若有两条以上的路，则删去其中一条路上的一条边，仍然连通，与 (5) 矛盾，故 \(u,v\) 之间有唯一的一条路

\((6)\rightarrow(1)\) 设 \(u,v\) 是 \(T\) 中的任意两个不同顶点，\(u,v\) 之间有唯一的一条路，故 \(T\) 连通，若 \(T\) 中有回路，则回路上任意两点之间有两条路，与假设矛盾，故 \(T\) 无回路

定理 8.1.2

树的中心是指使得 \(\max\{d(u,v)\}\) 最小的顶点 \(u\)，其中 \(v\) 是 \(T\) 中的任意顶点，证明：一棵树或者恰有一个中心，或者恰有两个相邻的中心

证明： 点击查看证明

选择树种最长路径 \(P\)，长度为 \(l\)，则 \(P\) 的中点（或中点的两个邻接点）即为树的中心

考虑节点 \(c\)，从 \(c\) 到任意节点 \(v\) 的最长距离，要么通过直径一部分，要么直接到达叶节点，若直接到达叶节点更长，则可以选出一条更长的路径，与 \(P\) 矛盾，故最长路径必须通过直径的一部分

因此，从 \(c\) 到树上任意节点的最长距离不会超过从直径两端到 \(c\) 的距离

所以，如果 \(c\) 是唯一的中心，则 \(c\) 必须是直径的中点，也是树的唯一中心

如果 \(c_1\) 和 \(c_2\) 是两个中心，则它们必须是直径的两个中点，且相邻

同上面可证

若 \(c_1\) 和 \(c_2\) 不是相邻的，由于 \(c_1\) 和 \(c_2\) 都是中心，所以从 \(c_1\) 到 \(c_2\) 的路径上任意一点到树上任意节点的最长距离都不会超过从 \(c_1\) 或 \(c_2\) 到该节点的最长距离

此时取路径上 \(c_1\) 和 \(c_2\) 之间的中点 \(c\)，则 \(c\) 的最长距离小于 \(c_1\) 或 \(c_2\) 的最长距离，矛盾

定理 8.1.3

正整数序列 \(d_1,d_2,\ldots,d_n\) 是某棵树的度数序列的充分必要条件是 \(\sum_{i=1}^nd_i=2(n-1)\)

证明： 点击查看证明

充分性：设 \(d_1,d_2,\ldots,d_n\) 是某棵树 \(T\) 的度数序列，则由图的度数和定理知 \(\sum_{i=1}^n d_i=2e=2(n-1)\)

必要性：

设正整数序列 \(d_1,d_2,\ldots,d_n\) 满足 \(\sum_{i=1}^n d_i=2(n-1)\)，则存在一棵树 \(T\) 的度数序列为 \(d_1,d_2,\ldots,d_n\)

用数学归纳法证明：

当 \(n=2\) 时，\(d_1=d_2=1\)，显然成立

假设当 \(n=k\) 时结论成立，现证明当 \(n=k+1\) 时结论也成立

由于 \(\sum_{i=1}^{k+1}d_i=2k\)，所以至少存在一个 \(d_j=1\)，删去 \(d_j\) 并把 \(d_i\) 减 \(1\)，其中 \(d_i\) 是不等于 \(1\) 的任意一个度数，得到新的度数序列 \(d_1',d_2',\ldots,d_k'\)，则有 \(\sum_{i=1}^kd_i'=2(k-1)\)

由归纳假设，存在一棵树 \(T'\) 的度数序列为 \(d_1',d_2',\ldots,d_k'\)，在 \(T'\) 中选取度数为 \(d_i'\) 的顶点 \(v\)，并添加一个新顶点 \(v_j\) 及边 \(vv_j\)，则得到的树 \(T\) 的度数序列为 \(d_1,d_2,\ldots,d_{k+1}\)

定理 8.1.4

一个连通图是树当且仅当它的每条边都是割边

证明： 点击查看证明

设 \(G\) 是树且 \(e\) 是树的边，由于 \(G\) 是无圈图，所以删去 \(e\) 后，\(G\) 不连通，故 \(e\) 是割边

反之，假设\(G\) 连通但不是树，则 \(G\) 包含一个圈 \(C\)，则删去 \(C\) 上的任意一条边后，\(G\) 仍然连通，与每条边都是割边矛盾，故 \(G\) 是树

定义 8.2 生成树 最小生成树

图 \(G\) 的生成子图是树 \(T\)，则称 \(T\) 为 \(G\) 的生成树

从 \(G\) 中删去 \(T\) 的边，得到的图称为 \(G\) 的余树（余枝）

设 \(G(V,E,\omega)\) 是带权连通简单图，\(\omega\) 是从 \(E\) 到正实数集的函数，又设 \(T\) 是 \(G\) 的生成树，则 \(T\) 的权重定义为 \(T\) 的所有枝的权重之和

记为 \(W(T)=\sum_{\{i,j\}\in T}\omega(i,j)\)

具有权重最小的生成树称为 \(G\) 的最小生成树

用 \(\tau(G)\) 记 \(G\) 的生成树的棵数

定理 8.2.1

若 \(T\) 是连通图 \(G\) 的生成树，并且 \(e\) 是 \(G\) 的不在 \(T\) 中的一条边，则 \(T+e\) 包含唯一的圈，这个圈称为 \(T\) 关于 \(e\) 的基本回路

设 \(T\) 是一颗生成树，\(\overline{e}\) 是一条不在 \(T\) 中的边（弦），则 \(T+ \overline{e}\) 恰有一个回路 \(C\)，且对于 \(C\) 上且 \(T\) 的任意一条边 \(e\)，\(T+\overline{e}-e\) 是 \(G\) 的另一颗生成树

即

设 \(T\) 是连通图 \(G\) 的生成树， \(\overline{e}\) 是 \(\overline{T}\) 的任意一边，则

• \(T\) 不包含 \(G\) 的割边
• \(T+\overline{e}\) 包含 \(G\) 的唯一的圈

定理 8.2.2

设 \(T\) 是连通图 \(G\) 的生成树， \(e\) 是 \(T\) 的任意一边，则

• 余树 \(\overline{T}\) 不包含 \(G\) 的键
• \(\overline{T}+e\) 包含 \(G\) 的唯一的键

把收缩一条边定义为把该边删去并把该边的两个端点合并为一个新顶点，这样的到的图记为 \(G\cdot e\)

则 \(n(G\cdot e)=n(G)-1,e(G\cdot e)=e(G)-1,\omega(G\cdot e)=\omega(G)\)

定理 8.2.3

若 \(e\) 是连通图 \(G\) 的一条边，则有 \(\tau(G)=\tau(G-e)+\tau(G\cdot e)\)

证明： 点击查看证明

定理 8.2.4

\(\tau(K_n)=n^{n-2}\)

证明： 点击查看证明

对于生成树 \(T\) 的每一条边 \(e\)，\(K_n\cdot e=K_{n-1}\)，所以由定理 8.2.3 有

\[\tau(K_n)=\tau(K_n-e)+\tau(K_{n-1})\]

由于 \(K_n-e\) 是连通图，且有多条边，所以对于任意一条边 \(f\)，\((K_n-e)\cdot f\) 仍然是 \(K_{n-1}\)，所以继续应用定理 8.2.3 可得

\[\tau(K_n-e)=\tau(K_n-e-f)+\tau(K_{n-1})\]

继续这样下去，直到删去 \(n-2\) 条边后，得到的图是 \(K_{n-1}\) 的一棵生成树，有且仅有一棵生成树，所以有

\[\tau(K_n-e)= (n-2)\tau(K_{n-1})\]

因此有

\[\tau(K_n)=(n-1)\tau(K_{n-1})\]

由 \(\tau(K_2)=1\) 可得 \(\tau(K_n)=n^{n-2}\)

定义 8.3 有向树 有根树

定义 8.4 二分树 霍夫曼树