本节对应原书 PDF 第 197–201 页。习题题干与答案书原答案逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。
习题
7.1 证明：树都是二部图.
7.2 证明：除平凡树外，树都不是欧拉图.
7.3 证明：除平凡树外，树都不是哈密顿图.
7.4 证明：树都是平面图.
7.5 哪些完全二部图是树？
7.6 无向完全图 K_n(n\geqslant 1) 中有树吗？
7.7 2,3,4,5 阶非同构的无向树各有多少棵？画出图形来.
7.8 树 T 有 2 个 4 度顶点，3 个 3 度顶点，其余顶点全是树叶，问 T 有几片树叶？
7.9 无向树 T 有 7 片树叶，3 个 3 度顶点，其余顶点的度数均为 4，求 T 的阶数 n.
7.10 无向树 T 中有 n_i 个顶点的度数为 i，i=2,3,\cdots,k，其余顶点全为树叶，问 T 中有几片树叶？
7.11 下面两组数中，哪个（些）可以为无向树的度数列？若是树的度数列，请画出两棵非同构的无向树.
(1) 1,1,2,3,3,4.
(2) 1,1,1,1,1,1,3,3,4.
7.12 设 T 为任意的无向树，问 T 的点连通度 \kappa 和边连通度 \lambda 分别为几？
7.13 图 7.16 所示无向图共有几棵非同构的生成树？画出它们来.
7.14 图 7.17 所示无向图共有几棵非同构的生成树？
7.15 图 7.18 所示无向图共有几棵非同构的生成树？
图 7.16 图 7.17 图 7.18
7.16 求图 7.19 所示两个带权图中的最小生成树，并计算它们的权.
7.17 求图 7.20 所示带权无向图的最小生成树，并计算它的权.
图 7.19 图 7.20
7.18 锅炉房到各楼可铺设暖气管道的线路及距离（m）如图 7.21 所示，试设计暖气管道的线路使得管道总长度最短.
7.19 根据图 7.22 所示根树 T 回答下列问题.
(1) T 有几个内点？
(2) T 有几个分支点？
(3) T 有几片树叶？
(4) T 的高度 h(T) 为几？
(5) T 是几元树？
图 7.21 图 7.22
7.20 画出 4 阶所有非同构的根树，并指明它们都是几元树.
7.21 设 m 和 t 分别为 2 元正则树 T 的边数和树叶数，证明：m=2(t-1)，阶数 n 为奇数.
7.22 设 T 是 r(r\geqslant 2) 元正则树，i 和 t 分别为分支点数和树叶数，证明：t=(r-1)i+1.
7.23 求高为 h 的 2 元完全正则树 T 的顶点数 n，边数 m 和树叶数 t.
7.24 求高为 h 的 r 元完全正则树 T 的树叶数 t 和分支点数 i.
7.25 画一棵权为 0.5,1,2,3,5,4,5,6,8,7,2,10 的最优 2 元树，并计算它的权.
7.26 下面给出的符号串集合中，哪些是前缀码？
7.27 用图 7.23 中的 2 元树产生一个 2 元前缀码.
图 7.23
7.28 设 7 个字母在通信中出现的频率如下.
(1) 以频率（或乘 100）为权，求最优 2 元树.
(2) 利用所求 2 元树找出每个字母的前缀码.
(3) 传输 10 000 个按上述比例出现的字母需要传输多少个二进制数位？比用长度为 3 的等长码子传输省了多少个二进制数位？
7.29 图 7.24 所示的 2 元树表达一个算式.
(1) 按中序行遍法写出算式.
(2) 用波兰符号法表示算式.
(3) 用逆波兰符号法表示算式.
图 7.24
习题解答与分析
7.1 树是连通无回路的无向图，这里所谓回路是指初级或简单回路，因而树中若有回路，一定是复杂回路，在其上的每条边均出现偶数次，所以树中没有奇数长度的回路. 由二部图的判别定理可知树都是二部图.
7.2 从不同的角度有多种方法证明非平凡树不是欧拉图，比如：
方法 1 利用 T 中有奇度顶点. 设 T 为一棵非平凡的树，由定理 7.2 可知，T 至少有两片树叶，因而 T 有奇度顶点. 由无向欧拉图的判别定理可知，T 不是欧拉图.
方法 2 利用 T 中有割边（桥）证明. 由定理 7.1 可知，T 的每条边都是桥，再由题 6.43 可知，非平凡树 T 不是欧拉图.
7.3 若 T 是 2 阶树，同构意义下，T 为 K_2，K_2 显然不是哈密顿图.
为了证明 n(n\geqslant 3) 阶树不是哈密顿图，先证明下面命题.
命题 在无向树 T 中，非树叶顶点都是割点.
证明 只有阶数 n\geqslant 3 的树中才有非树叶顶点. 设 u 为 T 中非树叶顶点，u 与 v 和 w 相邻，设 e_1=(v,u),e_2=(u,w)，则 e_1,e_2 均为桥，于是 p(T-u)\geqslant 2，故 u 为割点.
由此命题可知，阶数 n\geqslant 3 的树 T 中有割点，由主教材中定理 6.10 的推论可知，T 不是哈密顿图.
7.4 设 T 为任何一棵树，则 T 中既没有简单回路，也没有初级回路. 而与 K_5 或 K_{3,3} 同胚的图均有初级和简单回路，因而 T 中既没有与 K_5 同胚的子图，也无与 K_{3,3} 同胚的子图，由库拉图斯基定理可知，T 是平面图.
T 是特殊的平面图，T 只有一个外部面，无任何内部面. 外部面 R_0 的边界是由所有边构成的复杂回路组成（每条边在回路中恰好出现两次）.
7.5 完全二部图 K_{1,r}(r\geqslant 1) 和 K_{s,1}(s\geqslant 1) 为树. 在 K_{r,s} 中，若 r\geqslant 2 且 s\geqslant 2，则 K_{r,s} 中必含圈，所以，当 r\geqslant 2,s\geqslant 2 时，K_{r,s} 不是树.
以 K_{1,r} 为例说明这些树的特点. 设 K_{1,r} 的互补顶点子集为 V_1 和 V_2，且 V_1=\{v\},V_2=\{u_1,u_2,\cdots,u_r\}，其中，d(v)=r,d(u_i)=1,i=1,2,\cdots,r，即 u_i 全是树叶，称这样的树为星形图，v 为形心. 图 7.10(a) 所示为 K_{1,4}，图 7.10(b) 所示为 K_{1,7}.
图 7.10
7.6 无向完全图 K_n(n\geqslant 1) 中只有 K_1 与 K_2 是树，K_1 是平凡树.
7.7 给定阶数 n，求所有非同构的 n 阶无向树的步骤如下：
(1) 由树的性质可知，树的边数 m=n-1；
(2) 由握手定理可知，\sum\limits_{i=1}^{n}d(v_i)=2m=2n-2；
(3) 将 2n-2 度分给 n 个顶点，且每份均 \geqslant 1，求出所有的不同的分配方案，由不同的方案产生的树当然非同构；
(4) 注意有的方案也可能生成多棵非同构的无向树.
根据以上步骤可得：
n=2 时，度数列为 1,1，产生一棵树，如图 7.11(a) 所示.
n=3 时，度数列为 1,1,2，产生一棵树，如图 7.11(b) 所示.
n=4 时，度数列为 1,1,1,3 和 1,1,2,2，产生两棵非同构的树，如图 7.11(c)、(d) 所示.
n=5 时，度数列为 1,1,1,1,4 和 1,1,1,2,3，以及 1,1,2,2,2，产生 3 棵非同构的树，见图 7.11(e)、(f)、(g) 所示.
在以上 7 棵树中，每种度数方案都产生一棵非同构的树. 问：度数列为 1,1,1,1,2,2,2,4 的 8 阶树共有几棵非同构的树？
不难看出，4 度顶点和一个 2 度顶点相邻，和两个 2 度顶点相邻，以及和 3 个 2 度顶点相邻所产生的树是非同构的，所产生的 3 棵非同构的树如图 7.12(a)、(b)、(c) 所示.
图 7.11
图 7.12
7.8 T 共有 9 片树叶.
分析 解本题时应该应用树的阶数 n 与边数 m 的关系，即 m=n-1，以及握手定理.
设 T 有 t 片树叶，则 T 的阶数 n=2+3+t=5+t，于是边数 m=4+t，应用握手定理得
解出 t=9，于是 T 的度数列应为
7.9 T 的阶数 n=11.
分析 依然应用握手定理和树的性质 m=n-1，m 为边数.
设 4 度顶点的个数为 x，则阶数 n=7+3+x=10+x，于是边数 m=9+x，由握手定理得
解出 x=1，即 T 有 1 个 4 度顶点，阶数 n=10+1=11. T 的度数列为：
7.10 T 有 \sum\limits_{i=3}^{k}(i-2)n_i+2 片树叶.
分析 用握手定理及树的性质解答本题.
设 T 有 t 片树叶，则 T 的阶数 n=\sum\limits_{i=2}^{k}n_i+t，于是边数 m=n-1=\sum\limits_{i=2}^{k}n_i+t-1，由握手定理得
解得
7.11 (1) 中各数不能组成无向树的度数列；
(2) 中各数可以组成无向树的度数列.
分析 (1) 论证 1,1,2,3,3,4 不能成为树的度数列. 用归谬法证明. 若它们能成为某无向树的度数列，则 T 的阶数 n=6，边数 m=n-1=5. 由握手定理应有：
10=14 是个矛盾.
(2) 图 7.13(a)、(b) 中的树均以(2)中的数为度数列，且这两棵树是非同构的.
图 7.13
7.12 当 T 为平凡树时，\kappa=\lambda=0；当 T 为非平凡树时，\kappa=\lambda=1.
分析 当 T 为平凡树时，T 为完全图 K_1，而完全图 K_n 的点连通 \kappa 与边连通 \lambda 都等于 n-1，所以，\kappa=\lambda=0.
当 T 为非平凡树时，又分两种情况讨论.
① T 是 2 阶树，此时 T 为 K_2，所以 \kappa=\lambda=1.
② 当 T 的阶数 n\geqslant 3 时，T 一定有非树叶顶点，非树叶顶点都是割点，所以 \kappa=1，又 T 的每条边都是桥，所以 \lambda=1.
7.13 图 7.1 所示无向图 G 共有 3 棵非同构生成树.
分析 图 7.1 所示图为 5 阶无向连通简单图，由定理 7.3 可知 G 一定有生成树. 5 阶非同构的树共有 3 棵，它们的度数列分别为
① 1,1,1,1,4；
② 1,1,1,2,3；
③ 1,1,2,2,2.
于是 G 最多有 3 棵非同构的生成树. 经过观察发现 G 确实有 3 棵非同构的生成树. 图 7.14 中给出了这 3 棵生成树，其中图 7.14(a) 所示为度数列①所对应，图 7.14(b) 所示为度数列②所对应，图 7.14(c) 所示为度数列③所对应.
图 7.14
7.14 图 7.2 所示的无向图共有 2 棵非同构的生成树.
分析 图 7.2 所示无向图 G 也是连通图，因而它一定有生成树. 与题 7.13 类似讨论可知，它也最多有 3 棵非同构生成树，但因为最大度 \Delta(G)=3，因而它不可有对应度数列为 1,1,1,1,4 的生成树，但它有度数列为 1,1,1,2,3 和 1,1,2,2,2 的生成树，见图 7.15(a)、(b) 所示的 5 阶树.
7.15 图 7.3 所示图 G 只有一棵非同构的生成树.
分析 同题 7.13 和题 7.14 类似分析，该图 G 连通，所以一定有生成树，但因为 \Delta(G)=2，所以，G 不可能有对应度数列 1,1,1,1,4 和 1,1,1,2,3 的生成树，它只有度数列为 1,1,2,2,2 的生成树，见图 7.16 所示.
再讨论一下如下的问题：将图 7.3 所示 5 阶无向图顶点标定，见图 7.17(a) 所示的图，问：G 有多少棵不同的生成树？这里所谓不同生成树，是指两棵生成树 T_1 与 T_2 中只要有不同边就认为是不同的，也就是说是不同构意义上的. 易知图 7.17(a) 所示的图有 5 棵不同的生成树（当然它们彼此间都同构），见图 7.17(b)\sim(f) 所示.
图 7.15 图 7.16
图 7.17
7.16 用避圈法容易求出图 7.4 所示两个图的最小生成树，它们分别为图 7.18(a)、(b) 所示，它们的权分别为 10 和 28.
7.17 图 7.5 所示图的最小生成树如图 7.19 所示，其权为 118.
7.18 按照图 7.6 的最小生成树铺设管道，其总长度最短. 记锅炉房为顶点 0，用避圈法，依次取边：
总长度为
7.19 将图 7.7 所示根树标定顶点，所得树如图 7.20 所示.
图 7.18 图 7.19 图 7.20
(1) T 有 4 个内点，它们分别是 c,e,f,h.
(2) T 有 5 个分支点：a,c,e,f,h，其中 a 为树根.
(3) T 有 5 片树叶：b,d,g,i,j.
(4) T 的高度 h(T)=5，在树叶 i,j 处达到.
(5) T 是 3 元树.
7.20 4 阶非同构的根树共有 4 棵.
分析 将有向图 D 的所有边的箭头全去掉，即将有向边全变成无向边，所得无向图 G 称为 D 的基图. 设两棵同阶根树为 T_1、T_2，它们的基图为 G_1 与 G_2. 若 G_1\not\cong G_2，则 T_1\not\cong T_2，但当 G_1\cong G_2 时，T_1 与 T_2 不一定同构. 对于本题来说，n=4，应先求 4 阶非同构的无向树，由题 7.7 可知，4 阶非同构的树只有两棵，见图 7.21(a)、(b) 所示. 由图 7.21(a) 中树派生两棵非同构的根树，其中一棵是高为 1 的 3 元树，见图 7.21(c) 所示；另一棵是高为 2 的 2 元树，见图 7.21(d) 所示. 由图 7.21(b) 派生两个非同构的根树，其中一棵是高为 3 的 1 元树，见图 7.21(e) 所示，另一棵是高为 2 的 2 元树，见图 7.21(f) 所示.
图 7.21
7.21 m 和 t 分别为 2 元正则树 T 的边数和树叶数，再令 n 和 i 分别为 T 的阶数和分支点数.
方法 1 用定义直接证明. 由定义可得
① n=i+t；
② m=2i（2 元正则树定义）；
③ n=m+1（树的性质）.
由①和③可得 i+t=m+1\Rightarrow i=m+1-t，代入②可得
方法 2 对分支点数 i 做归纳法.
① 当 i=1 时，此时 2 元正则树由树根（分支点）和两片树叶组成，具有 2 条边，所以 m=2=2(2-1)=2(t-1)，即 i=1 时结论为真.
② 设 i=k(k\geqslant 1) 时结论为真，证明 i=k+1 时结论也为真. 分支点数为 k+1 的 2 元正则树 T 一定存在分支点 u，具有两个儿子都是树叶，设树叶分别为 v_1、v_2，并设 T 的边数和树叶数分别为 m 和 t. 令 T'=T-\{v_1,v_2\}，所得树 T' 具有 k 个分支点，边数 m'=m-2，树叶数 t'=t-2+1=t-1（注意，在 T' 中 u 成了树叶）. 由归纳假设可知
在以上两种方法的证明中，还是方法 1 较为方便.
由于 n=m+1=2(t-1)+1，故 n 必为奇数.
7.22 与题 7.21 类似，也可以用定义或归纳法证明.
方法 1 用定义直接证明.
① T 的边数 m=ir（r 元正则树的定义）；
② T 的阶数 n=i+t；
③ m=n-1=i+t-1.
由①和③，得 ir=i+t-1\Rightarrow t=(r-1)i+1.
方法 2 对分支点数 i 做归纳法.
① i=1 时，T 由树根和 r 片树叶构造，即
② 设 i=k 时，结论为真，证明 i=k+1 时，结论也为真.
设 r 元正则树 T 有 (k+1) 个分支点，边数为 m，树叶数为 t.
在 T 中必存在顶点 u，它的儿子们全是树叶，不妨设 u 的儿子为 v_1,v_2,\cdots,v_r. 考虑
则 T' 有 k 个分支点，树叶数 t'=t-r+1（在 T' 中 u 也为树叶了）. 由归纳假设可知
将 t'=t-r+1 代入上式得
7.23 高为 h(h\geqslant 0) 的 2 元完全正则树 T 中，阶数 n=2^{h+1}-1，m=2(2^h-1)，树叶数 t=2^h，分支点数 i=2^h-1.
分析 用公比为 q(q\neq 1) 的等比级数前 s+1 项之和的计算公式 1+q+q^2+\cdots+q^s=(1-q^{s+1})/(1-q) 来先计算出高为 h 的 2 元完全正则树 T 的阶数 n.
易知，在 T 中第 0 层、第 1 层、\cdots、第 h 层上的顶点数分别为 1,2,2^2,\cdots,2^{h-1},2^h，于是
因而
又，第 h 层上的顶点全是树叶，其他层上无树叶，所以，t=2^h，分支点数 i=n-t=2^h-1.
7.24 树叶数 t=r^h，分支点数 i=(r^h-1)/(r-1).
分析 与题 7.23 类似讨论.
在高为 h 的 r(r\geqslant 2) 元完全正则树 T 中，在 0 层、1 层、\cdots、h 层上的顶点数分别为 1,r,r^2,\cdots,r^h，于是
树叶数 t=r^h，于是
7.25 画出的最优树如图 7.22 所示，其权 W(T)=114.8.
图 7.22
7.26 B_1、B_2、B_4 是前缀码. 而 B_3 和 B_5 不是前缀码.
分析 在 B_3 中，1 是 11 和 101 的前缀，001 是 0011 的前缀，所以 B_3 不是前缀码.
在 B_5 中，a 是 aa 和 ac 的前缀，所以 B_5 也不是前缀码.
7.27 在每个分支点引出的 2 条边上，左边的标 0，右边的标 1. 当只有一条边时标 0. 这样在每片树叶得到的 0-1 串组成一个前缀码，如图 7.23 所示. 得到的前缀码是
分析 若 2 元树不是正则的，当从分支点只引出一条边时，可以标 0，也可以标 1. 例如，将图 7.23 中所有这样的边都标 1，得到前缀码
当然也可以有的标 0，另一些标 1，得到不同的前缀码.
图 7.23
7.28 (1) 最优 2 元树如图 7.24 所示.
(2) a-11，b-01，c-101，d-100，e-001，f-0001，g-0000.
(3) W(T)=255，这说明传输 100 个按给定的比例出现的 7 个字母 a\sim g 需要 255 个二进制数位，传输 10 000 个需要 25 500 个二进制数位. 而用等长的二进制数位传输，如用 000 传 a，001 传 b，\cdots，110 传 g，传 10 000 个需要 30 000 个二进制数位. 这样一来用前缀码传输，比用等长码传输节省了 4500 个二进制数位.
图 7.24
7.29 (1) 按中序行遍法还原算式.
根据先乘除后加减的运算法则，上式可省去一些括号，变为
(2) 用波兰符号法表示算式（前序行遍法访问）：
(3) 用逆波兰等号法表示算式（后序行遍法访问）：
解读：第 7 章习题的解法几乎都压在两条工具上——握手定理 \sum d(v_i)=2m 配树的 m=n-1 用来反解度数分布（7.8–7.11），而正则树/完全正则树的计数则靠「边数 = 分支点数 × 分支度」加归纳（7.21–7.24）。7.13–7.15 三题用的是同一招：先枚举同阶非同构树，再用最大度 \Delta(G) 把不可能的度数列筛掉。