第 16章 树离 散 数 学哈尔滨工程大学本科生课程软件与理论教研室本章说明
树是图论中重要内容之一。
本章所谈 回路均指初级回路（圈）或简单回路,
不含复杂回路（有重复边出现的回路）。
16.1 无向树及其性质
16.2 生成树
16.3 根树及其应用本章小结习 题作 业本章说明
16.1 无向树及其性质定义 16.1
无向树 —— 连通无回路的无向图，简称树，用 T表示。
平凡树 —— 平凡图。
森林 —— 若无向图 G至少有两个连通分支（每个都是树）。
树叶 —— 无向图中悬挂顶点。
分支点 —— 度数 大于或等于 2的顶点。
举例 如图为九个顶点的树。
定理 16.1 设 G＝ <V,E>是 n阶 m条边的无向图,则下面各命题是等价的：
（ 1） G是树 。
（ 2） G中任意两个顶点之间存在唯一的路径 。
（ 3） G中无回路且 m＝ n?1。
（ 4） G是连通的且 m＝ n?1。
（ 5） G是连通的且 G中任何边均为桥 。
（ 6） G中没有回路，但在任何两个不同的顶点之间加一条新边，
在所得图中得到唯一的一个含新边的圈。
无向树的等价定义
(1)?(2)
如果 G是树,则 G中任意两个顶点之间存在唯一的路径 。
存在性。
由 G的连通性及定理 14.5的推论（ 在 n阶图 G中，若从顶点 vi到
vj(vi?vj)存在通路，则 vi到 vj 一定存在长度小于等于 n-1的初级通路 (路径 )）可知，
u,v∈ V,u与 v之间存在路径。
唯一性 （反证法）。
若路径不是唯一的，设 Г1与 Г2都是 u到 v的路径，
易知必存在由 Г1和 Г2上的边构成的回路，
这与 G中无回路矛盾。
(2)?(3)
如果 G中任意两个顶点之间存在唯一的路径,
则 G中无回路且 m＝ n-1。
首先证明 G中无回路。
若 G中存在关联某顶点 v的环，
则 v到 v存在长为 0和 1的两条路经
(注意初级回路是路径的特殊情况 )，
这与已知矛盾。
若 G中存在长度大于或等于 2的圈，
则圈上任何两个顶点之间都存在两条不同的路径，
这也与已知矛盾。
(2)?(3)
如果 G中任意两个顶点之间存在唯一的路径,
则 G中无回路且 m＝ n-1。
其次证明 m＝ n-1。 （归纳法）
n＝ 1时,G为平凡图，结论显然成立。
设 n≤ k(k≥1) 时结论成立，
当 n=k+1时，设 e＝ (u,v)为 G中的一条边，
由于 G中无回路，所以 G-e为两个连通分支 G1,G2。
设 ni,mi分别为 Gi中的顶点数和边数，则 ni≤ k,i＝ 1,2，
由归纳假设可知 mi＝ ni-1,于是
m＝ m1+m2+1＝ n1-1+n2-1+1＝ n1+n2-1＝ n-1。
只需证明 G是连通的。（采用反证法）
假设 G是不连通的，由 s(s≥ 2)个连通分支 G1,G2,…,Gs组成
,并且 Gi中均无回路，因而 Gi全为树 。
由 (1)?(2)?(3)可知,mi＝ ni-1。 于是,
由于 s≥ 2,与 m＝ n-1矛盾 。
1 1 1
( 1 )
s s s
i i i
i i i
m m n n s n s
(3)?(4)
如果 G中无回路且 m＝ n-1,则 G是连通的且 m＝ n -1。
如果 G是连通的且 m＝ n?1,则 G是连通的且 G中任何边均为桥 。
只需证明 G中每条边均为桥 。
e∈ E,均有 |E(G-e)|＝ n-1-1＝ n-2，
由习题十四题 49（ 若 G是 n阶 m条边的无向连通图，则 m≥n-1） 可知,G-e已不是连通图,
所以,e为桥 。
(4)?(5)
如果 G是连通的且 G中任何边均为桥,则 G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈 。
因为 G中每条边均为桥，删掉任何边，将使 G变成不连通图，
所以,G中没有回路，也即 G中无圈。
又由于 G连通，所以 G为树，由 (1)?(2)可知，
u,v∈ V,且 u≠v,则 u与 v之间存在唯一的路径 Г，
则 Г∪ (u,v)（ (u,v)为加的新边 ） 为 G中的圈，
显然圈是唯一的。
(5)?(6)
如果 G中没有回路，但在任何两个不同的顶点之间加一条新边，
在所得图中得到唯一的一个含新边的圈,则 G是树 。
只需证明 G是连通的。
u,v∈ V,且 u≠v,则新边 (u,v)∪ G产生唯一的圈 C，
显然有 C -(u,v)为 G中 u到 v的通路，故 u～ v，
由 u,v的任意性可知,G是连通的。
(6)?(1)
定理 16.2 设 T是 n阶非平凡的无向树,则 T中至少有两片树叶 。
设 T有 x片树叶,由握手定理及定理 16.1可知,证明
2 ( 1 ) ( ) 2 ( )in d v x n x
由上式解出 x≥ 2。
无向树的性质例 16.1
例 16.1 画出 6阶所有非同构的无向树。
解答 设 Ti是 6阶无向树。
由定理 16.1可知,Ti的边数 mi＝ 5，
由握手定理可知,∑ dTi(vj)＝ 10,且 δ( Ti)≥1,△ (Ti)≤5 。
于是 Ti的度数列必为以下情况之一。
(1) 1,1,1,1,1,5
(2) 1,1,1,1,2,4
(3) 1,1,1,1,3,3
(4) 1,1,1,2,2,3
(5) 1,1,2,2,2,2
(4)对应两棵非同构的树，
在一棵树中两个 2度顶点相邻，
在另一棵树中不相邻，
其他情况均能画出一棵非同构的树。
例 16.1
人们常称只有一个分支点，且分支点的度数为 n-1的
n(n≥3) 阶无向树为 星形图,称唯一的分支点为 星心 。
例 16.2
例 16.2 7阶无向图有 3片树叶和 1个 3度顶点，其余 3个顶点的度数均无 1和 3。试画出满足要求的所有非同构的无向树。
解答 设 Ti为满足要求的无向树，则边数 mi＝ 6,于是
∑ d(vj)＝ 12＝ e+3+d(v4)+d(v5)+d(v6)。
由于 d(vj)≠1∧d( vj)≠3,而且 d(vj)≥1 且 d(vj)≤6,j＝ 4,5,6，
可知 d(vj)＝ 2,j＝ 4,5,6。 于是 Ti 的度数列为
1,1,1,2,2,2,3
由度数列可知,Ti中有一个 3度顶点 vi,vi的邻域 N(vi)中有 3个顶点，这 3个顶点的度数列只能为以下三种情况之一：
1,1,2 1,2,2 2,2,2
设它们对应的树分别为 T1,T2,T3。此度数列只能产生这三棵非同构的 7阶无向树。
例 16.2
例题例题 已知无向树 T中,有 1个 3度顶点,2个 2度顶点,其余顶点全是树叶,试求树叶数,并画出满足要求的非同构的无向树 。
解答 设有 x片树叶,于是结点总数为
n＝ 1+2+x＝ 3+x
由握手定理和树的性质 m＝ n?1可知,
2m＝ 2(n?1)＝ 2× (2+x)
＝ 1× 3+2× 2+x
解出 x＝ 3,故 T有 3片树叶。
故 T的度数应为 1,1,1,2,2,3。
例题 已知无向树 T有 5片树叶,2度与 3度顶点各 1个，其余顶点的度数均为 4,求 T的阶数 n,并画出满足要求的所有非同构的无向树。
解答 设 T的阶数为 n,则边数为 n?1,4度顶点的个数为 n?7。
由握手定理得
2m = 2(n?1) = 5?1+2?1+3?1+4(n?7)
解出 n = 8,所以 4度顶点为 1个 。
故 T的度数列为 1,1,1,1,1,2,3,4。
例题小节结束例题
16.2 生成树定义 16.2 设 G为无向图，
（ 1） T为 G的 树 — T是 G的子图并且是树 。
（ 2） T为 G的 生成树 — T是 G的生成子图并且是树 。
（ 3） e为 T的 树枝 — 设 T是 G的生成树,?e∈ E(G),若 e∈ E(T)。
（ 4） e为 T的 弦 — 设 T是 G的生成树,?e∈ E(G),若 e?E(T)。
（ 5） 生成树 T的 余树 — 导出子图 G[E(G)-E(T)] 。 记作 T
注意,不一定连通，也不一定不含回路。T
说明定理 16.3 无向图 G具有生成树当且仅当 G连通 。
证明 必要性,显然 。
充分性 （ 破圈法 ） 。
若 G中无回路,G为自己的生成树 。
若 G中含圈,任取一圈,随意地删除圈上的一条边,
若再有圈再删除圈上的一条边,直到最后无圈为止 。
易知所得图无圈 (当然无回路 ),连通且为 G的生成子图,
所以为 G的生成树 。
生成树的存在条件推论 1 G为 n阶 m条边的无向连通图,则 m≥ n?1。
证明 由定理 16.3可知,G有生成树，设 T为 G的一棵生成树，
则 m＝ |E(G)|≥| E(T)|＝ n-1。
推论 2 设 G是 n阶 m条边的无向连通图,T为 G的生成树，
则 T的余树中含有 m-n+1条边（即 T有 m-n+1条弦） 。
推论 3 设 T是连通图 G的一棵生成树,T为 T的余树,
C为 G中任意一个圈,则 E(T)∩ E(C)≠?。
证明 若 E(T)∩ E(C)＝?,则 E(C)?E(T)，
这说明 C为 T中圈，与 T为 树 矛盾。
所以推论正确。
推论定理 16.4 设 T为无向连通图 G中一棵生成树,e为 T的任意一条弦,则 T∪ e中含 G中只含一条弦其余边均为树枝的圈,而且不同的弦对应的圈也不同 。
证明 T∪ e中含 G中只含一条弦其余边均为树枝的圈。
设 e＝ (u,v),由定理 16.1可知，
在 T中,u,v之间存在惟一的路径?(u,v)，
则?(u,v)∪ e为所要求的圈。
不同的弦对应的圈也不同是显然的。
定理 16.4
定义 16.3 设 T是 n阶 m条边的无向连通图 G的一棵生成树,设 e?1,
e?2,…,e?m?n+1为 T的弦 。 设 Cr为 T添加弦 e?r产生的 G中只含弦 e?r
,其余边均为树枝的圈,称 Cr为 G的对应 T的弦 e?r的基本回路或 基本圈,r＝ 1,2,…,m?n+1。
称 {C1,C2,…,Cm?n+1}为 G对应 T的基本回路系统,称 m?n+1为 G
的圈秩,记作?(G)。
求基本回路的算法设弦 e=(u,v),先求 T中 u到 v的路径?(u,v),再并上弦 e,即得对应 e的基本回路 。
基本回路与基本回路系统的定义对应生成树的弦分别为
e6,e7,e8,e10,e11。
设它们对应的基本回路分别为 C1,C2,C3,C4,C5,从对应的弦开始，按逆时针（也可都按顺时针）的顺序写出它们，分别为此图的圈秩为 5，基本回路系统为 {C1,C2,C3,C4,C5}。
无向连通图 G的圈秩与生成树的选取无关，但不同生成树对应的基本回路系统可能不同。
说明求下图中的 基本回路系统。
举例
C1＝ e6e4e5 C2＝ e7e2e1 C3＝ e8e9e2e1 C4＝ e10e3e5e2 C5＝ e11e3e5e2e9
定理 16.5
定理 16.5 设 T是连通图 G的一棵生成树,e为 T的树枝,则 G中存在只含树枝 e,其余边都是弦的割集,且不同的树枝对应的割集也不同 。
证明 由定理 16.1可知,e是 T的桥,
因而 T?e有两个连通分支 T1和 T2，
令 Se＝ {e|e?E(G)且 e的两个端点分别属于 V(T1)和 V(T2)}，
由构造显然可知,Se为 G的割集,e?Se且 Se中除 e外都是弦。
不同的树枝对应的割集也不同是显然的。
基本割集与基本割集系统的定义定义 16.4 设 T是 n阶连通图 G的一棵生成树,e?1,e?2,…,e?n?1为
T的树枝,Si是 G的 只含树枝 e?i的割集,则称 Si为 G的对应于生成树 T由树枝 e?i生成的基本割集,i＝ 1,2,…,n?1。
称 {S1,S2,…,Sn?1}为 G对应 T的基本割集系统,称 n?1为 G的割集秩,记作?(G)。
求基本割集的算法设 e?为生成树 T的树枝,T?e?为两棵小树 T1与 T2,令
Se? ＝ {e|e?E(G)且 e的两个端点分别属于 T1与 T2}，
则 Se?为 e?对应的基本割集 。
树枝为 e1,e2,e3,e4,e5,e9。
设它们对应的基本割集分别为
S1,S2,S3,S4,S5,S6。
此图的割集秩为 6，基本割集系统为 {S1,S2,S3,S4,S5,S6}。
S1＝ {e1,e7,e8}
无向连通图 G的割集秩与生成树的选取无关，但不同生成树对应的基本割集系统可能不同。
说明求下图中的 基本 割集 系统。
举例
S2＝ {e2,e7,e8,e10,e11} S3＝ {e3,e10,e11}
S4＝ {e4,e6} S5＝ {e5,e6,e10,e11} S6＝ {e9,e8,e11}
最小生成树定义 16.5 设 T是无向连通带权图 G＝ <V,E,W>的一棵生成树,
T的各边权之和称为 T的权,记作 W(T)。
G的所有生成树中权最小的生成树称为 G的 最小生成树 。
求最小生成树的算法 （ 避圈法 (Kruskal)）
(1)设 n阶无向连通带权图 G＝ <V,E,W>有 m条边 。 不妨设 G中没有环 （ 否则,可以将所有的环先删去 ）,将 m条边按权从小到大排序,e1,e2,…,em。
(2)取 e1在 T中 。
(3)依次检查 e2,…,em,若 ej(j≥ 2)与已在 T中的边不构成回路,
取 ej也在 T中,否则弃去 ej。
(4)算法停止时得到的 T为 G的最小生成树为止。
例 16.3
例 16.3 求下图所示两个图中的最小生成树。
W(T1)＝ 6 W(T2)＝ 12
例题例如 求所示图的一棵最小生成树 。 解答最小生成树 W(T)=38
小节结束
16.3 根树及其应用
设 D是有向图，若 D的基图是无向树，则称 D为有向树。
在所有的有向树中，根树最重要，所以我们只讨论根树。
二叉树的应用根树的定义定义 16.6 T是 n(n≥ 2)阶有向树,
(1) T为根树 — T中有一个顶点入度为 0,其余顶点的入度均为 1
(2) 树根 —— 入度为 0的顶点
(3) 树叶 —— 入度为 1,出度为 0的顶点
(4) 内点 —— 入度为 1,出度不为 0的顶点
(5) 分支点 —— 树根与内点的总称
(6) 顶点 v的层数 —— 从树根到 v的通路长度
(7) 树高 —— T中层数最大顶点的层数
(8) 根树 —— 平凡树根树的画法树根放上方,省去所有有向边上的箭头 。
树叶 —— 8片内点 —— 6个分支点 —— 7个高度 —— 5
家族树常将根树看成家族树,家族中成员之间的关系如下定义 。
定义 16.7 设 T为一棵非平凡的根树,
vi,vj∈ V(T),若 vi可达 vj,则称 vi为 vj的 祖先,vj为 vi的 后代 。
若 vi邻接到 vj（ 即 <vi,vj>∈ E(T)）,则称 vi为 vj的 父亲,而 vj为 vi
的 儿子 。
若 vj,vk的父亲相同,则称 vj与 vk是 兄弟 。
定义 16.8 设 v为根树 T中任意一顶点,称 v及其后代的导出子图为以 v为根的 根子树 。
根树的分类
(1)设 T为根树,若将 T中层数相同的顶点都标定次序,
则称 T为 有序树 。
(2)分类,根据根树 T中每个分支点儿子数以及是否有序
r叉树 —— 每个分支点至多有 r个儿子
r叉有序树 —— r叉树是有序的
r叉正则树 —— 每个分支点恰有 r个儿子
r叉正则有序树 —— r叉正则树是有序的
r叉完全正则树 —— 树叶层数均为树高的 r叉正则树
r叉完全正则有序树 —— r叉完全正则树是有序的最优二叉树定义 16.9 设 2叉树 T有 t片树叶 v1,v2,…,vt,权分别为 w1,w2,
…,wt,称 为 T的权,其中 l(vi)是 vi的层数,
在所有有 t片树叶,带权 w1,w2,…,wt的 2叉树中,权最小 的
2叉树称为 最优 2叉树 。
1
( ) ( )t ii
i
W t w l v
举例下图所示的三棵 2叉树 T1,T2,T3都是带权为 2,2,3,3,5的 2叉树
。
W(T1)=2× 2+2× 2+3× 3+5× 3+3× 2=38
W(T2)=3× 4+5× 4+3× 3+2× 2+2× 1=47
W(T3)=3× 3+3× 3+5× 2+2× 2+2× 2=36
求最优树的算法 (Huffman算法 )
给定实数 w1,w2,…,wt,且 w1≤w2≤… ≤ wt。
① 连接权为 w1,w2的两片树叶，得一个分支点，其权为 w1+w2。
② 在 w1+w2,w3,…,wt中选出两个最小的权,连接它们对应的顶点 （ 不一定是树叶 ）,得新分支点及所带的权 。
③ 重复 ②,直到形成 t?1个分支点,t片树叶为止 。
算法举例例如,求带权为 1,1,2,3,4,5的最优树。
解答
W(T)=38
(1)最佳前最码的定义定义 16.10 设?1,?2,…,?n-1,?n是长度为 n的符号串,
称其子串?1,?1?2,…,?1?2…?n?1 分别为该字符串的长度为 1,2,
…,n的 前缀 。
设 A={?1,?2,…,?m}为一个符号串集合,若对于任意的?i,?j?A，
i?j,?i,?j互不为前缀,则称 A为 前缀码 。
若?i(i=1,2,…,m)中只出现 0与 1两个符号,则称 A为 二元前缀码 。
(2)如何产生二元前缀码？
定理 16.6 由一棵给定的 2叉正则树,可以产生唯一的一个二元前缀码 。
最佳前缀码方法：
将每个分支点引出的两条边分别标上 0和 1。
结果：
图所示树产生的前缀码为 {00,10,11,011,0100,0101}。
用 Huffman算法产生最佳前缀码例 16.6 在通信中,八进制数字出现的频率如下：
0,25% 1,20%
2,15% 3,10%
4,10% 5,10%
6,5% 7,5%
求传输它们的最佳前缀码？
求传输 10n（ n≥2） 个按上述比例出现的八进制数字需要多少个二进制数字？
若用等长的 （ 长为 3） 的码字传输需要多少个二进制数字？
解答 以 100乘各频率为权，并按小到大排列，得 w1=5,w2=5,w3=10,
w4=10,w5=10,w6=15,w7=20,w8=25。 产生的最优树如下。
0 —— 01
1 —— 11
2 —— 001
3 —— 100
4 —— 101
5 —— 0001
6 —— 00000
7 —— 00001
传 100个按比例出现的八进制数字所需二进制数字个数 W(T)=285
,所以传 10n(n?2)个所用二进制数字应为 2.85?10n。
用等长码 （ 长为 3） 应该用 3?10n个数字 。
由于在每一步选择两个最小的权的选法不唯一。
因为两个权对应的顶点所放左右位置不同。
画出的最优树可能不同，最佳前缀码并不唯一，但有一点是共同的，就是它们的权应该相等，即它们都应该是最优树。
说明
3,波兰符号法与逆波兰符号法
对一棵根树的每个顶点都访问且仅访问一次称为行遍或周游一棵树 。
对 2叉有序正则树的周游方式：
① 中序行遍法 —— 次序为：左子树,树根,右子树
② 前序行遍法 —— 次序为：树根,左子树,右子树
③ 后序行遍法 —— 次序为：左子树,右子树,树根中序行遍法,b a (f d g) c e
前序行遍法,a b (c (d f g) e)
后序行遍法,b ((f g d) e c) a
例如：
用 2叉有序正则树存放算式：
最高层次的运算符放在树根上 。
依次将运算符放在根子树的根上 。
参加运算的数放在树叶上，
规定：被除数、被减数放在左子树树叶上。
例如,用二叉有序正则树表示算式 ((b+(c+d))?a)?((e?f)?(g+h)?(i?j))
解答
波兰符号法按前序行遍法访问存放算式的 2叉有序正则树,其结果不加括号,规定每个运算符号与其后面紧邻两个数进行运算,运算结果正确 。 称此算法为 波兰符号法或前缀符号法 。
上图前序行遍法的访问结果为
b + c d a e f? + g h? i j
逆波兰符号法按后序行遍法访问,规定每个运算符与前面紧邻两数运算,称为 逆波兰符号法或后缀符号法 。
上图后序行遍法的访问结果为
b c d + + a? e f? g h + i j 小节结束本章主 要内容
无向树的定义及其性质 。
生成树的定义及存在定理 。
基本回路及基本回路系统 。
基本割集及基本割集系统 。
最小生成树 。
根树及其分类 。
最优树,Huffman算法 。
最佳前缀码 。
波兰符号法与逆波兰符号法 。
本章学习要求
深刻理解树的定义和性质 。
熟练地求解无向树 。
准确地求解最小生成树 。
深刻理解基本回路,基本割集,基本回路系统,基本割集系统等概念 。
深刻理解根树,分类,家族树等诸多概念 。
会画阶数 n较小的非同构的根树 。
熟练掌握用 Huffman算法求最优树的方法 。
熟练掌握求最佳前缀码的方法 。
会用二叉树表示算式 。
会求算式的波兰符号法和逆波兰符号法表示的算式 。 小节结束习 题
1、无向树 T有 ni个 i度顶点,i=2,3,…,k,其余顶点全是树叶
，求 T的树叶数。
提示：用树的性质 m=n?1及握手定理 。
解答
2
k
i
i
n n t t
为 树 叶 数（ 1）
2
1k i
i
m n t
（ 2）
2 1 2
2 2 2 2 ( )k n ki i i
i i i
m n t d v i n t
（ 3）
3
( 2) 2k i
i
t i n
从而解出 。
2、设 n阶非平凡的无向树 T中,?(T)? k,k? 1。 证明 T至少有 k片树叶。
证明反证法 。
假设 T至多有 s片树叶,即 s < k，
由于?(T)? k,故存在 v0,d(v0)? k。 于是,
1
2 2 2 ( ) 2 ( 1 )n i
i
m n d v n s k s
由此解出 s? k,这与 s < k矛盾 。
3、画出基图为右图所示无向树的所有非同构的根树。
解答
4、设 T是正则 2叉树,T有 t片树叶，证明 T的阶数 n=2t?1。
证明方法一,利用正则 2叉树的定义及树的性质直接证明 。
（ 1） n = t+i (i为分支点数 )
（ 2） n = m+1 （ m为 T的边数 ）
（ 3） m = 2i （ 正则 2叉树定义 ）
由 （ 2） 和 （ 3） 得,代入 （ 1） 得 n = 2t?1.1
2
ni
方法二,利用握手定理及树的性质证明 。
T的树根为 2度顶点,所有内点为 3度顶点,而树叶为 1度顶点,所以有
（ 1） 2m = 2+3(i?1)+t
（ 2） n = m+1 = i+t
由 （ 1） 和 （ 2） 可解出 n = 2t?1。
小节结束作业习题十六,
1,2,3,20,21,23,35
结束
树是图论中重要内容之一。
本章所谈 回路均指初级回路（圈）或简单回路,
不含复杂回路（有重复边出现的回路）。
16.1 无向树及其性质
16.2 生成树
16.3 根树及其应用本章小结习 题作 业本章说明
16.1 无向树及其性质定义 16.1
无向树 —— 连通无回路的无向图，简称树，用 T表示。
平凡树 —— 平凡图。
森林 —— 若无向图 G至少有两个连通分支（每个都是树）。
树叶 —— 无向图中悬挂顶点。
分支点 —— 度数 大于或等于 2的顶点。
举例 如图为九个顶点的树。
定理 16.1 设 G＝ <V,E>是 n阶 m条边的无向图,则下面各命题是等价的：
（ 1） G是树 。
（ 2） G中任意两个顶点之间存在唯一的路径 。
（ 3） G中无回路且 m＝ n?1。
（ 4） G是连通的且 m＝ n?1。
（ 5） G是连通的且 G中任何边均为桥 。
（ 6） G中没有回路，但在任何两个不同的顶点之间加一条新边，
在所得图中得到唯一的一个含新边的圈。
无向树的等价定义
(1)?(2)
如果 G是树,则 G中任意两个顶点之间存在唯一的路径 。
存在性。
由 G的连通性及定理 14.5的推论（ 在 n阶图 G中，若从顶点 vi到
vj(vi?vj)存在通路，则 vi到 vj 一定存在长度小于等于 n-1的初级通路 (路径 )）可知，
u,v∈ V,u与 v之间存在路径。
唯一性 （反证法）。
若路径不是唯一的，设 Г1与 Г2都是 u到 v的路径，
易知必存在由 Г1和 Г2上的边构成的回路，
这与 G中无回路矛盾。
(2)?(3)
如果 G中任意两个顶点之间存在唯一的路径,
则 G中无回路且 m＝ n-1。
首先证明 G中无回路。
若 G中存在关联某顶点 v的环，
则 v到 v存在长为 0和 1的两条路经
(注意初级回路是路径的特殊情况 )，
这与已知矛盾。
若 G中存在长度大于或等于 2的圈，
则圈上任何两个顶点之间都存在两条不同的路径，
这也与已知矛盾。
(2)?(3)
如果 G中任意两个顶点之间存在唯一的路径,
则 G中无回路且 m＝ n-1。
其次证明 m＝ n-1。 （归纳法）
n＝ 1时,G为平凡图，结论显然成立。
设 n≤ k(k≥1) 时结论成立，
当 n=k+1时，设 e＝ (u,v)为 G中的一条边，
由于 G中无回路，所以 G-e为两个连通分支 G1,G2。
设 ni,mi分别为 Gi中的顶点数和边数，则 ni≤ k,i＝ 1,2，
由归纳假设可知 mi＝ ni-1,于是
m＝ m1+m2+1＝ n1-1+n2-1+1＝ n1+n2-1＝ n-1。
只需证明 G是连通的。（采用反证法）
假设 G是不连通的，由 s(s≥ 2)个连通分支 G1,G2,…,Gs组成
,并且 Gi中均无回路，因而 Gi全为树 。
由 (1)?(2)?(3)可知,mi＝ ni-1。 于是,
由于 s≥ 2,与 m＝ n-1矛盾 。
1 1 1
( 1 )
s s s
i i i
i i i
m m n n s n s
(3)?(4)
如果 G中无回路且 m＝ n-1,则 G是连通的且 m＝ n -1。
如果 G是连通的且 m＝ n?1,则 G是连通的且 G中任何边均为桥 。
只需证明 G中每条边均为桥 。
e∈ E,均有 |E(G-e)|＝ n-1-1＝ n-2，
由习题十四题 49（ 若 G是 n阶 m条边的无向连通图，则 m≥n-1） 可知,G-e已不是连通图,
所以,e为桥 。
(4)?(5)
如果 G是连通的且 G中任何边均为桥,则 G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈 。
因为 G中每条边均为桥，删掉任何边，将使 G变成不连通图，
所以,G中没有回路，也即 G中无圈。
又由于 G连通，所以 G为树，由 (1)?(2)可知，
u,v∈ V,且 u≠v,则 u与 v之间存在唯一的路径 Г，
则 Г∪ (u,v)（ (u,v)为加的新边 ） 为 G中的圈，
显然圈是唯一的。
(5)?(6)
如果 G中没有回路，但在任何两个不同的顶点之间加一条新边，
在所得图中得到唯一的一个含新边的圈,则 G是树 。
只需证明 G是连通的。
u,v∈ V,且 u≠v,则新边 (u,v)∪ G产生唯一的圈 C，
显然有 C -(u,v)为 G中 u到 v的通路，故 u～ v，
由 u,v的任意性可知,G是连通的。
(6)?(1)
定理 16.2 设 T是 n阶非平凡的无向树,则 T中至少有两片树叶 。
设 T有 x片树叶,由握手定理及定理 16.1可知,证明
2 ( 1 ) ( ) 2 ( )in d v x n x
由上式解出 x≥ 2。
无向树的性质例 16.1
例 16.1 画出 6阶所有非同构的无向树。
解答 设 Ti是 6阶无向树。
由定理 16.1可知,Ti的边数 mi＝ 5，
由握手定理可知,∑ dTi(vj)＝ 10,且 δ( Ti)≥1,△ (Ti)≤5 。
于是 Ti的度数列必为以下情况之一。
(1) 1,1,1,1,1,5
(2) 1,1,1,1,2,4
(3) 1,1,1,1,3,3
(4) 1,1,1,2,2,3
(5) 1,1,2,2,2,2
(4)对应两棵非同构的树，
在一棵树中两个 2度顶点相邻，
在另一棵树中不相邻，
其他情况均能画出一棵非同构的树。
例 16.1
人们常称只有一个分支点，且分支点的度数为 n-1的
n(n≥3) 阶无向树为 星形图,称唯一的分支点为 星心 。
例 16.2
例 16.2 7阶无向图有 3片树叶和 1个 3度顶点，其余 3个顶点的度数均无 1和 3。试画出满足要求的所有非同构的无向树。
解答 设 Ti为满足要求的无向树，则边数 mi＝ 6,于是
∑ d(vj)＝ 12＝ e+3+d(v4)+d(v5)+d(v6)。
由于 d(vj)≠1∧d( vj)≠3,而且 d(vj)≥1 且 d(vj)≤6,j＝ 4,5,6，
可知 d(vj)＝ 2,j＝ 4,5,6。 于是 Ti 的度数列为
1,1,1,2,2,2,3
由度数列可知,Ti中有一个 3度顶点 vi,vi的邻域 N(vi)中有 3个顶点，这 3个顶点的度数列只能为以下三种情况之一：
1,1,2 1,2,2 2,2,2
设它们对应的树分别为 T1,T2,T3。此度数列只能产生这三棵非同构的 7阶无向树。
例 16.2
例题例题 已知无向树 T中,有 1个 3度顶点,2个 2度顶点,其余顶点全是树叶,试求树叶数,并画出满足要求的非同构的无向树 。
解答 设有 x片树叶,于是结点总数为
n＝ 1+2+x＝ 3+x
由握手定理和树的性质 m＝ n?1可知,
2m＝ 2(n?1)＝ 2× (2+x)
＝ 1× 3+2× 2+x
解出 x＝ 3,故 T有 3片树叶。
故 T的度数应为 1,1,1,2,2,3。
例题 已知无向树 T有 5片树叶,2度与 3度顶点各 1个，其余顶点的度数均为 4,求 T的阶数 n,并画出满足要求的所有非同构的无向树。
解答 设 T的阶数为 n,则边数为 n?1,4度顶点的个数为 n?7。
由握手定理得
2m = 2(n?1) = 5?1+2?1+3?1+4(n?7)
解出 n = 8,所以 4度顶点为 1个 。
故 T的度数列为 1,1,1,1,1,2,3,4。
例题小节结束例题
16.2 生成树定义 16.2 设 G为无向图，
（ 1） T为 G的 树 — T是 G的子图并且是树 。
（ 2） T为 G的 生成树 — T是 G的生成子图并且是树 。
（ 3） e为 T的 树枝 — 设 T是 G的生成树,?e∈ E(G),若 e∈ E(T)。
（ 4） e为 T的 弦 — 设 T是 G的生成树,?e∈ E(G),若 e?E(T)。
（ 5） 生成树 T的 余树 — 导出子图 G[E(G)-E(T)] 。 记作 T
注意,不一定连通，也不一定不含回路。T
说明定理 16.3 无向图 G具有生成树当且仅当 G连通 。
证明 必要性,显然 。
充分性 （ 破圈法 ） 。
若 G中无回路,G为自己的生成树 。
若 G中含圈,任取一圈,随意地删除圈上的一条边,
若再有圈再删除圈上的一条边,直到最后无圈为止 。
易知所得图无圈 (当然无回路 ),连通且为 G的生成子图,
所以为 G的生成树 。
生成树的存在条件推论 1 G为 n阶 m条边的无向连通图,则 m≥ n?1。
证明 由定理 16.3可知,G有生成树，设 T为 G的一棵生成树，
则 m＝ |E(G)|≥| E(T)|＝ n-1。
推论 2 设 G是 n阶 m条边的无向连通图,T为 G的生成树，
则 T的余树中含有 m-n+1条边（即 T有 m-n+1条弦） 。
推论 3 设 T是连通图 G的一棵生成树,T为 T的余树,
C为 G中任意一个圈,则 E(T)∩ E(C)≠?。
证明 若 E(T)∩ E(C)＝?,则 E(C)?E(T)，
这说明 C为 T中圈，与 T为 树 矛盾。
所以推论正确。
推论定理 16.4 设 T为无向连通图 G中一棵生成树,e为 T的任意一条弦,则 T∪ e中含 G中只含一条弦其余边均为树枝的圈,而且不同的弦对应的圈也不同 。
证明 T∪ e中含 G中只含一条弦其余边均为树枝的圈。
设 e＝ (u,v),由定理 16.1可知，
在 T中,u,v之间存在惟一的路径?(u,v)，
则?(u,v)∪ e为所要求的圈。
不同的弦对应的圈也不同是显然的。
定理 16.4
定义 16.3 设 T是 n阶 m条边的无向连通图 G的一棵生成树,设 e?1,
e?2,…,e?m?n+1为 T的弦 。 设 Cr为 T添加弦 e?r产生的 G中只含弦 e?r
,其余边均为树枝的圈,称 Cr为 G的对应 T的弦 e?r的基本回路或 基本圈,r＝ 1,2,…,m?n+1。
称 {C1,C2,…,Cm?n+1}为 G对应 T的基本回路系统,称 m?n+1为 G
的圈秩,记作?(G)。
求基本回路的算法设弦 e=(u,v),先求 T中 u到 v的路径?(u,v),再并上弦 e,即得对应 e的基本回路 。
基本回路与基本回路系统的定义对应生成树的弦分别为
e6,e7,e8,e10,e11。
设它们对应的基本回路分别为 C1,C2,C3,C4,C5,从对应的弦开始，按逆时针（也可都按顺时针）的顺序写出它们，分别为此图的圈秩为 5，基本回路系统为 {C1,C2,C3,C4,C5}。
无向连通图 G的圈秩与生成树的选取无关，但不同生成树对应的基本回路系统可能不同。
说明求下图中的 基本回路系统。
举例
C1＝ e6e4e5 C2＝ e7e2e1 C3＝ e8e9e2e1 C4＝ e10e3e5e2 C5＝ e11e3e5e2e9
定理 16.5
定理 16.5 设 T是连通图 G的一棵生成树,e为 T的树枝,则 G中存在只含树枝 e,其余边都是弦的割集,且不同的树枝对应的割集也不同 。
证明 由定理 16.1可知,e是 T的桥,
因而 T?e有两个连通分支 T1和 T2，
令 Se＝ {e|e?E(G)且 e的两个端点分别属于 V(T1)和 V(T2)}，
由构造显然可知,Se为 G的割集,e?Se且 Se中除 e外都是弦。
不同的树枝对应的割集也不同是显然的。
基本割集与基本割集系统的定义定义 16.4 设 T是 n阶连通图 G的一棵生成树,e?1,e?2,…,e?n?1为
T的树枝,Si是 G的 只含树枝 e?i的割集,则称 Si为 G的对应于生成树 T由树枝 e?i生成的基本割集,i＝ 1,2,…,n?1。
称 {S1,S2,…,Sn?1}为 G对应 T的基本割集系统,称 n?1为 G的割集秩,记作?(G)。
求基本割集的算法设 e?为生成树 T的树枝,T?e?为两棵小树 T1与 T2,令
Se? ＝ {e|e?E(G)且 e的两个端点分别属于 T1与 T2}，
则 Se?为 e?对应的基本割集 。
树枝为 e1,e2,e3,e4,e5,e9。
设它们对应的基本割集分别为
S1,S2,S3,S4,S5,S6。
此图的割集秩为 6，基本割集系统为 {S1,S2,S3,S4,S5,S6}。
S1＝ {e1,e7,e8}
无向连通图 G的割集秩与生成树的选取无关，但不同生成树对应的基本割集系统可能不同。
说明求下图中的 基本 割集 系统。
举例
S2＝ {e2,e7,e8,e10,e11} S3＝ {e3,e10,e11}
S4＝ {e4,e6} S5＝ {e5,e6,e10,e11} S6＝ {e9,e8,e11}
最小生成树定义 16.5 设 T是无向连通带权图 G＝ <V,E,W>的一棵生成树,
T的各边权之和称为 T的权,记作 W(T)。
G的所有生成树中权最小的生成树称为 G的 最小生成树 。
求最小生成树的算法 （ 避圈法 (Kruskal)）
(1)设 n阶无向连通带权图 G＝ <V,E,W>有 m条边 。 不妨设 G中没有环 （ 否则,可以将所有的环先删去 ）,将 m条边按权从小到大排序,e1,e2,…,em。
(2)取 e1在 T中 。
(3)依次检查 e2,…,em,若 ej(j≥ 2)与已在 T中的边不构成回路,
取 ej也在 T中,否则弃去 ej。
(4)算法停止时得到的 T为 G的最小生成树为止。
例 16.3
例 16.3 求下图所示两个图中的最小生成树。
W(T1)＝ 6 W(T2)＝ 12
例题例如 求所示图的一棵最小生成树 。 解答最小生成树 W(T)=38
小节结束
16.3 根树及其应用
设 D是有向图，若 D的基图是无向树，则称 D为有向树。
在所有的有向树中，根树最重要，所以我们只讨论根树。
二叉树的应用根树的定义定义 16.6 T是 n(n≥ 2)阶有向树,
(1) T为根树 — T中有一个顶点入度为 0,其余顶点的入度均为 1
(2) 树根 —— 入度为 0的顶点
(3) 树叶 —— 入度为 1,出度为 0的顶点
(4) 内点 —— 入度为 1,出度不为 0的顶点
(5) 分支点 —— 树根与内点的总称
(6) 顶点 v的层数 —— 从树根到 v的通路长度
(7) 树高 —— T中层数最大顶点的层数
(8) 根树 —— 平凡树根树的画法树根放上方,省去所有有向边上的箭头 。
树叶 —— 8片内点 —— 6个分支点 —— 7个高度 —— 5
家族树常将根树看成家族树,家族中成员之间的关系如下定义 。
定义 16.7 设 T为一棵非平凡的根树,
vi,vj∈ V(T),若 vi可达 vj,则称 vi为 vj的 祖先,vj为 vi的 后代 。
若 vi邻接到 vj（ 即 <vi,vj>∈ E(T)）,则称 vi为 vj的 父亲,而 vj为 vi
的 儿子 。
若 vj,vk的父亲相同,则称 vj与 vk是 兄弟 。
定义 16.8 设 v为根树 T中任意一顶点,称 v及其后代的导出子图为以 v为根的 根子树 。
根树的分类
(1)设 T为根树,若将 T中层数相同的顶点都标定次序,
则称 T为 有序树 。
(2)分类,根据根树 T中每个分支点儿子数以及是否有序
r叉树 —— 每个分支点至多有 r个儿子
r叉有序树 —— r叉树是有序的
r叉正则树 —— 每个分支点恰有 r个儿子
r叉正则有序树 —— r叉正则树是有序的
r叉完全正则树 —— 树叶层数均为树高的 r叉正则树
r叉完全正则有序树 —— r叉完全正则树是有序的最优二叉树定义 16.9 设 2叉树 T有 t片树叶 v1,v2,…,vt,权分别为 w1,w2,
…,wt,称 为 T的权,其中 l(vi)是 vi的层数,
在所有有 t片树叶,带权 w1,w2,…,wt的 2叉树中,权最小 的
2叉树称为 最优 2叉树 。
1
( ) ( )t ii
i
W t w l v
举例下图所示的三棵 2叉树 T1,T2,T3都是带权为 2,2,3,3,5的 2叉树
。
W(T1)=2× 2+2× 2+3× 3+5× 3+3× 2=38
W(T2)=3× 4+5× 4+3× 3+2× 2+2× 1=47
W(T3)=3× 3+3× 3+5× 2+2× 2+2× 2=36
求最优树的算法 (Huffman算法 )
给定实数 w1,w2,…,wt,且 w1≤w2≤… ≤ wt。
① 连接权为 w1,w2的两片树叶，得一个分支点，其权为 w1+w2。
② 在 w1+w2,w3,…,wt中选出两个最小的权,连接它们对应的顶点 （ 不一定是树叶 ）,得新分支点及所带的权 。
③ 重复 ②,直到形成 t?1个分支点,t片树叶为止 。
算法举例例如,求带权为 1,1,2,3,4,5的最优树。
解答
W(T)=38
(1)最佳前最码的定义定义 16.10 设?1,?2,…,?n-1,?n是长度为 n的符号串,
称其子串?1,?1?2,…,?1?2…?n?1 分别为该字符串的长度为 1,2,
…,n的 前缀 。
设 A={?1,?2,…,?m}为一个符号串集合,若对于任意的?i,?j?A，
i?j,?i,?j互不为前缀,则称 A为 前缀码 。
若?i(i=1,2,…,m)中只出现 0与 1两个符号,则称 A为 二元前缀码 。
(2)如何产生二元前缀码？
定理 16.6 由一棵给定的 2叉正则树,可以产生唯一的一个二元前缀码 。
最佳前缀码方法：
将每个分支点引出的两条边分别标上 0和 1。
结果：
图所示树产生的前缀码为 {00,10,11,011,0100,0101}。
用 Huffman算法产生最佳前缀码例 16.6 在通信中,八进制数字出现的频率如下：
0,25% 1,20%
2,15% 3,10%
4,10% 5,10%
6,5% 7,5%
求传输它们的最佳前缀码？
求传输 10n（ n≥2） 个按上述比例出现的八进制数字需要多少个二进制数字？
若用等长的 （ 长为 3） 的码字传输需要多少个二进制数字？
解答 以 100乘各频率为权，并按小到大排列，得 w1=5,w2=5,w3=10,
w4=10,w5=10,w6=15,w7=20,w8=25。 产生的最优树如下。
0 —— 01
1 —— 11
2 —— 001
3 —— 100
4 —— 101
5 —— 0001
6 —— 00000
7 —— 00001
传 100个按比例出现的八进制数字所需二进制数字个数 W(T)=285
,所以传 10n(n?2)个所用二进制数字应为 2.85?10n。
用等长码 （ 长为 3） 应该用 3?10n个数字 。
由于在每一步选择两个最小的权的选法不唯一。
因为两个权对应的顶点所放左右位置不同。
画出的最优树可能不同，最佳前缀码并不唯一，但有一点是共同的，就是它们的权应该相等，即它们都应该是最优树。
说明
3,波兰符号法与逆波兰符号法
对一棵根树的每个顶点都访问且仅访问一次称为行遍或周游一棵树 。
对 2叉有序正则树的周游方式：
① 中序行遍法 —— 次序为：左子树,树根,右子树
② 前序行遍法 —— 次序为：树根,左子树,右子树
③ 后序行遍法 —— 次序为：左子树,右子树,树根中序行遍法,b a (f d g) c e
前序行遍法,a b (c (d f g) e)
后序行遍法,b ((f g d) e c) a
例如：
用 2叉有序正则树存放算式：
最高层次的运算符放在树根上 。
依次将运算符放在根子树的根上 。
参加运算的数放在树叶上，
规定：被除数、被减数放在左子树树叶上。
例如,用二叉有序正则树表示算式 ((b+(c+d))?a)?((e?f)?(g+h)?(i?j))
解答
波兰符号法按前序行遍法访问存放算式的 2叉有序正则树,其结果不加括号,规定每个运算符号与其后面紧邻两个数进行运算,运算结果正确 。 称此算法为 波兰符号法或前缀符号法 。
上图前序行遍法的访问结果为
b + c d a e f? + g h? i j
逆波兰符号法按后序行遍法访问,规定每个运算符与前面紧邻两数运算,称为 逆波兰符号法或后缀符号法 。
上图后序行遍法的访问结果为
b c d + + a? e f? g h + i j 小节结束本章主 要内容
无向树的定义及其性质 。
生成树的定义及存在定理 。
基本回路及基本回路系统 。
基本割集及基本割集系统 。
最小生成树 。
根树及其分类 。
最优树,Huffman算法 。
最佳前缀码 。
波兰符号法与逆波兰符号法 。
本章学习要求
深刻理解树的定义和性质 。
熟练地求解无向树 。
准确地求解最小生成树 。
深刻理解基本回路,基本割集,基本回路系统,基本割集系统等概念 。
深刻理解根树,分类,家族树等诸多概念 。
会画阶数 n较小的非同构的根树 。
熟练掌握用 Huffman算法求最优树的方法 。
熟练掌握求最佳前缀码的方法 。
会用二叉树表示算式 。
会求算式的波兰符号法和逆波兰符号法表示的算式 。 小节结束习 题
1、无向树 T有 ni个 i度顶点,i=2,3,…,k,其余顶点全是树叶
，求 T的树叶数。
提示：用树的性质 m=n?1及握手定理 。
解答
2
k
i
i
n n t t
为 树 叶 数（ 1）
2
1k i
i
m n t
（ 2）
2 1 2
2 2 2 2 ( )k n ki i i
i i i
m n t d v i n t
（ 3）
3
( 2) 2k i
i
t i n
从而解出 。
2、设 n阶非平凡的无向树 T中,?(T)? k,k? 1。 证明 T至少有 k片树叶。
证明反证法 。
假设 T至多有 s片树叶,即 s < k，
由于?(T)? k,故存在 v0,d(v0)? k。 于是,
1
2 2 2 ( ) 2 ( 1 )n i
i
m n d v n s k s
由此解出 s? k,这与 s < k矛盾 。
3、画出基图为右图所示无向树的所有非同构的根树。
解答
4、设 T是正则 2叉树,T有 t片树叶，证明 T的阶数 n=2t?1。
证明方法一,利用正则 2叉树的定义及树的性质直接证明 。
（ 1） n = t+i (i为分支点数 )
（ 2） n = m+1 （ m为 T的边数 ）
（ 3） m = 2i （ 正则 2叉树定义 ）
由 （ 2） 和 （ 3） 得,代入 （ 1） 得 n = 2t?1.1
2
ni
方法二,利用握手定理及树的性质证明 。
T的树根为 2度顶点,所有内点为 3度顶点,而树叶为 1度顶点,所以有
（ 1） 2m = 2+3(i?1)+t
（ 2） n = m+1 = i+t
由 （ 1） 和 （ 2） 可解出 n = 2t?1。
小节结束作业习题十六,
1,2,3,20,21,23,35
结束
