第 9章 树第 9章 树
9.1 无向树
9.2 根树及其应用
9.3 例题选解习 题 九第 9章 树
9.1 无 向 树定义 9.1.1 连通无回路的无向图称为无向树,简称树,记作 T。 树中的悬挂点称为树叶,其余顶点称为分支点 。 每个连通分支均为树的无向图称为森林 。 平凡图称为平凡树 。
例 9.1.1 图 9.1.1中 （ a）,（ b） 均是树,图 （ c） 是森林 。
由于树无环且无重边 （ 否则有回路 ）,所以树必是简单图 。 下面我们来讨论树的性质 。
第 9章 树图 9.1.1
( b )( a ) ( c )
第 9章 树定理 9.1.1 无向图 T是树,当且仅当以下五条之一成立 。
（ 1） T中无回路且 m=n-1,其中 m为边数,n为顶点数 。
（ 2） T是连通图且 m=n-1。
（ 3） T中无回路,但增一条边,则得到一条且仅一条初级回路 。
（ 4） T连通且每条边均是桥 。
（ 5） 每对顶点间有唯一的一条初级通路 。
第 9章 树证明 ① 由树的定义可得 （ 1） 。
施归纳于顶点数 n。 当 n=1时,m=0,则 m=n-1成立 。
假设当 n=k时,m=n-1成立 。 则当 n=k+1时,因为树是连通的且无回路,所以至少有一个度数为 1的顶点 v，
从树中删去 v和与它关联的边,则得到 k个顶点的树 T′。
根据假设它有 k-1条边,现将 v和与它关联的边加到 T′上还原成树 T,则 T有 k+1个顶点,k条边,边数比顶点数少 1,故 m=n-1成立 。
第 9章 树
② 由 （ 1） 可得 （ 2） 。
再证反证法,若图 T不连通,设 T有 k个连通分支 T1，
T2,…,Tk（ k≥2）,其顶点数分别为 n1,n2,…,nk，
则有
1
k
i
i
nn
边数分别为 m1,m2,…,mk，则有
1
k
i
i
mm
第 9章 树因此,有
11
( 1 ) 1
kk
ii
ii
m m n n k n
即 m＜ n-1，这与 m=n-1矛盾，故 T是连通的 m=n-1图。
第 9章 树
③ 由 （ 2） 可得 （ 3） 。
若 T是连通图并有 n-1条边 。 施归纳于顶点数 n。
当 n=2时,m=n-1=1,所以没有回路,如果增加一条边,只能得到唯一的一个回路 。
假设 n=k时,命题成立 。 则当 n=k+1时,因为 T是连通的并有 n-1条边,所以每个顶点都有 d（ v） ≥1,并且至少有一个顶点 v0,满足 d（ v0） =1。 否则,如果每个顶点 v都有 d（ v） ≥2,那么必然会有总度数 2m≥2n,即
m≥n,这与条件 m=n-1矛盾 。 因此至少有一个顶点 v0，
满足 d（ v0） =1。
第 9章 树删去 v0及其关联的边,得到图 T′,由假设知 T′无回路,现将 v0及其关联的边再加到 T′,则还原成 T,所以 T
没有回路 。
如果在连通图 T中增加一条新边 （ vi,vj）,则 （ vi，
vj） 与 T中从 vi到 vj的一条初级路径构成一个初级回路,
且该回路必定是唯一的,否则当删去新边 （ vi,vj） 时,
T中必有回路,产生矛盾 。
第 9章 树
④ 由 （ 3） 可得 （ 4） 。
若图 T不连通,则存在两个顶点 vi和 vj,在 vi,vj之间没有路径,如果增加边 （ vi,vj） 不产生回路,这与
（ 3） 矛盾,因此 T连通 。 因为 T中无回路,所以删去任意一条边,图必不连通 。 故图中每一条边均是桥 。
⑤由（ 4）可得（ 5）。
由图的连通性可知,任意两个顶点之间都有一条通路,是初级通路 。 如果这条初级通路不唯一,则 T中必有回路,删去回路上的任意一条边,图仍连通,与
（ 4） 矛盾 。 故任意两个顶点之间有唯一一条初级回路 。
第 9章 树
⑥ 由 （ 5） 可得树的定义 。
每对顶点之间有唯一一条初级通路,那么 T必连通,
若有回路,则回路上任意两个顶点之间有两条初级通路,与 （ 5） 矛盾 。 故图连通且无回路,是树 。
第 9章 树定理 9.1.2 任何一棵非平凡树 T至少有两片树叶 。
证明 设 T是 （ n,m） 图,n≥2,有 k片树叶,其余顶点度数均大于或等于 2。 则
1
1
( ) 2 ( ) 2
( ) 2 2 ( ) 2 2
n
i
i
n
i
i
d n k k n k
d m n k n
而所以 2n-2≥2n-k，即 k≥2。
第 9章 树
【 例 9.1.2】 T是一棵树,有两个顶点度数为 2,一个顶点度数为 3,三个顶点度数为 4,T有几片树叶？
解 设树 T有 x片树叶,则 T的顶点数
n=2+1+3+x
T的边数
m=n-1=5+x
又由握手定理
1
2 ( )
n
i
i
md?
第 9章 树得
2 · （ 5+x） =2·2+3·1+4·3+x
所以 x=9,即树 T有 9片树叶 。
请读者自己画出两棵具有上述度数列的非同构的树 。
第 9章 树
【 例 9.1.3】 画出所有非同构的七阶无向树 。
解 设 Ti是七阶无向树。因为 n=7，所以 m=6，又因为,所以七个顶点分配 12度，且由树是连通简单图知 1≤d（ v） ≤6。则 Ti的度数列必是下列情况之一。
1
2 ( )n i
i
md?
第 9章 树
（ 1） 1,1,2,2,2,2,2
（ 2） 1,1,1,2,2,2,3
（ 3） 1,1,1,1,2.2,4
（ 4） 1,1,1,1,2,3,3
（ 5） 1,1,1,1,1,2,5
（ 6） 1,1,1,1,1,3,4
（ 7） 1,1,1,1,1,1,6
第 9章 树生成树有一些图,本身不是树,但它的某些子图却是树,
其中很重要的一类是生成树 。
定义 9.1.2 若无向图 G的一个生成子图 T是树，则称 T
是 G的一棵生成树。
例如图 9.1.3中,T1和 T2是图 G的两棵生成树 。
由图 9.1.3可见,G与 T1,T2的区别是 G中有回路,而它的生成树无回路,因此要在一个连通图 G中找到一棵生成树,只要不断地从 G的回路上删去一条边,最后所得无回路的子图就是 G的一棵生成树 。 于是有以下定理 。
第 9章 树图 9.1.2
T
1
T
2
T
7
T
8
T
9
T
10
T
11
T
3
T
4
T
5
T
6
第 9章 树图 9.1.3
e
2
e
3
e
4
e
1
e
5
e
6
e
7 e
8
e
9
e
10
e
2
e
3
e
1
e
6
e
7
e
8
e
2
e
4
e
1
e
6
e
7 e
9
T
2
T
1
G
1
2
3
4
5
6 7
1 2
3
4
5
6 7
1 2
3
4
5
6 7
第 9章 树定理 9.1.3 无向图 G有生成树的充分必要条件是 G为连通图 。
证明 先采用反证法来证明必要性 。
若 G不连通,则它的任何生成子图也不连通,因此不可能有生成树,与 G有生成树矛盾,故 G是连通图 。
再证充分性 。
设 G连通,则 G必有连通的生成子图,令 T是 G的含有边数最少的生成子图,于是 T中必无回路 （ 否则删去回路上的一条边不影响连通性,与 T含边数最少矛盾 ）,
故 T是一棵树,即生成树 。
第 9章 树如果 T是 G的一棵生成树,则称 G在 T中的边为 T的树枝,G不在 T中的边为 T的弦,T的所有的弦的集合的导出子图称 T的余树 。 易知,余树不一定是树,更不一定是生成树 。
一般情况,图 G的生成树不是唯一的,这里的不唯一有两个含义,一种是标定图的生成树所含的树枝不同,另一种是不考虑标定的生成树是不同构的 。 但无论怎样,一个连通的 （ n,m） 图,其任意一棵生成树的树枝数一定是 n-1,从而弦数也是固定不变的 m-n+1。
由树的性质可知,对于图 G的一棵生成树 T,每增加一条弦,便得到一条初级回路 。
第 9章 树例如,在图 9.1.3所示的 T1中：
加弦 e5,得初级回路 e2e3e5；
加弦 e4,得初级回路 e1e3e4；
加弦 e9,得初级回路 e6e8e9；
加弦 e10,得初级回路 e7e8e10。
同样,在图 9.1.3所示的 T2中,分别加弦 e3,e5,e8，
e10,则分别产生初级回路 e1e3e4,e1e4e5e2,e6e8e9，
e7e6e9e10。
第 9章 树这些初级回路有一个共同特点：它们中均只含一条弦,其余的边均是树枝,我们称这样的回路为基本回路 。 对于 G的每棵生成树 T,m-n+1条弦对应着 m-n+1
个基本回路,这些基本回路构成的集合称为对应 T的基本回路系统 。 显然不同的生成树对应不同的基本回路系统 。 如图 9.1.3中,G对应 T1的基本回路系统为 {e2e3e5，
e1e3e4,e6e8e9,e7e8e10},G对应 T2的基本回路系统为
{e1e3e4,e1e4e5e2,e6e8e9,e7e6e9e10}。 但是它们所含的元素个数均是 m-n+1=4。 在电路网络分析中,基本回路具有重要意义 。
第 9章 树另一方面,从树 T中删去一边,便将 T分成两棵树,
即两个连通分支,图 G中连接这两个连通分支的边的集合,称为对应于这条边的基本 （ 边 ） 割集 。
例如在图 9.1.3中的 G和 T1：
对应树枝 e1,有基本割集 {e1,e4}；
对应树枝 e2,有基本割集 {e2,e5}；
对应树枝 e3,有基本割集 {e3,e4,e5}；
对应树枝 e6,有基本割集 {e6,e9}；
对应树枝 e7,有基本割集 {e7,e10}；
对应树枝 e8,有基本割集 {e8,e9,e10}；
第 9章 树同样对于图 9.1.3中的 G和 T2，对应树枝 e1,e2,e4，
e6,e7,e9，分别有基本割集,{e1,e3,e5},{e2,e5}，
{e4,e3,e5},{e6,e8,e 10 },{e7,e 10 },{e9，
e 10}。
第 9章 树这些割集所具有的共同特点是：每个割集中均只含生成树的一个树枝,其余的均是弦 。 对于图 G的任何一棵生成树 T,对应每个树枝的基本割集所构成的集合,
称为对应 T的基本割集系统 。 如图 9.1.3中,G对应 T2的基本割集系统为 {{e1,e3,e5},{e2,e5},{e4,e3,e5}，
{e6,e8,e 10 },{e7,e 10 },{e9,e 10 }},显然不同的生成树有不同的基本割集系统,但其元素个数均为 n-1。
第 9章 树最小生成树带权图的生成树是实际应用较多的树,所谓权就是附加在图上的信息,通常是实数,权加在边上的称边权图,加在点上的称点权图,这里我们只涉及边权图 。
定义 9.1.3 对图 G的每条边附加上一个实数 ω（ e）,
称 ω（ e） 为边 e上的权,G连同附加在各边上的权称为带权图,常记作 G=〈 V,E,ω〉 。 设 G1是 G的任意子图,
G1的权,记作 ω（ G1） 。
1()
()
e E G
e?
第 9章 树一个很实际的问题是：假设你是一个设计师,欲架设连接 n个村镇的电话线,每个村镇设一个交换站 。
已知由 i村到 j村的线路 e=（ vi,vj） 造价为 ω（ e） =w ij
,要保证任意两个村镇之间均可通话,请设计一个方案,使总造价最低 。 这个问题的数学模型为：在已知的带权图上求权最小的生成树 。
第 9章 树定义 9.1.4 设无向连通带权图 G=〈 V,E,ω〉,G中带权最小的生成树称为 G的最小生成树 （ 最优树 ） 。
定理 9.1.4 设连通图 G的各边的权均不相同,则回路中权最大的边必不在 G的最小生成树中 。
证明略。
第 9章 树定理的结论是显然的,由此寻找带权图 G的最小生成树,可以采用破圈法,即在图 G中不断去掉回路中权最大的边 。
求最小生成树的另一个更有效率的算法是克鲁斯卡尔 （ Kruskal ） 的避圈法：
（ 1） 选 e1∈ E（ G）,使得 ω(e1） = min 。
（ 2） 若 e1,e2,…,ei已选好,则从 E（ G） -{e1，
e2,…,ei}中选取 e i+1,使得 G［ {e1,e2,…,ei}］ 中无圈,且 ω（ e i+1 ） =min。
（ 3） 继续进行到选得 e n-1 为止 。
第 9章 树
【 例 9.1.4】 求图 9.1.4（ a）所示带权图的最小生成树。（它的实际背景是北京与巴黎、纽约、东京、伦敦、墨西哥城这六大城市间的航空路线距离图，单位是百公里。）
解 图 9.1.4（ b） 中实线是用破圈法得到的最小生成树 （ 虚线是去掉的回路上的边 ）,图 9.1.4（ c） 中粗实线是用避圈法得到的最小生成树 。 其权均为 122。
事实上因为边（ L,B）与（ P,B）的权相等，所以最小生成树并不唯一（如图 9.1.4的（ b）与（ c）），
但是它们的权是相等的。
第 9章 树图 9.1.4
L
60
51
56
70
2
2135
68
68
78
6113
51 36
57
T
B
P
NY
MG
L
60
51
56
70
2
2135
68
68
78
6113
51 36
57
T
B
P
NY
MG
L
60
51
56
70
2
2135
68
68
78
6113
51 36
57
T
B
P
NY
MG
( b )( a ) ( c )
第 9章 树
9.2 根树及其应用定义 9.2.1 T是一棵有向树,若 T中恰有一个顶点入度为 0,其余顶点的入度均为 1,则称 T为根树 。 入度为
0的顶点称树根,出度为 0的顶点称树叶,入度为 1,出度不为 0的顶点称内点,内点和树根统称为分支点 。
例如图 9.2.1中的 （ a）,（ b）,（ c） 均是有向树,
但只有图 （ c） 是根树 。
第 9章 树图 9.2.1
( b )( a ) ( c )
1
0
2
3
4
5
6
7
8
第 9章 树由定义和例题易知,对于 （ n,m） 根树,同样有
m=n-1,且根树一定是有向树,但反之未必 。
在根树中,从树根 v0到每个顶点 vi有唯一一条初级通路,该通路的长度称为点 vi的层数,记作 l（ vi）,其中最大的层数称为树高,记作 h（ T） 。
第 9章 树习惯上将根树画成树根在上,各边箭头均朝下的形状 （ 如图 9.2.1（ c） 所示 ）,并为方便起见,略去各边上的箭头,可以看出,根树上的各个顶点有了层次关系 。
一棵根树常常被形象的比作一棵家族树,如果顶点 u邻接到顶点 v,则称 u为 v的父亲,v为 u的儿子；共有同一个父亲的顶点称为兄弟；如果顶点 u可达顶点 v，
则称 u是 v的祖先,v是 u的后代 。 在根树 T中,所有的内点,树叶均是树根的后代,由某个顶点 vi及其所有的后代构成的导出子图称为 T的以 vi为根的子根树 。
第 9章 树例如图 9.2.1（ c） 中,v3是 v1的儿子,v1是 v3的父亲；
v4与 v5是兄弟,
T′=G［ {v2,v4,v5,v6,v7,v8}］ 是以 v2为根的 T的子根树 。
定义 9.2.2 在根树 T中,如果每一层的顶点都按一定的次序排列,则称 T为有序树 。 在画有序树时,常假定每一层的顶点是按从左到右排序的 。
例如图 9.2.2中的 （ a） 和 （ b） 表示的是不同的有序树 。 而如果不考虑同层顶点的次序,则图 9.2.2（ a）
和 （ b） 表示的是同一棵根树 。
第 9章 树图 9.2.2
( b )( a )
第 9章 树
【 例 9.2.1】 英语句子,The big elephant ate the
peanut” 可以图解为图 9.2.3，称之为这个英语句子的语法树。可见，句子的语法树是一棵有序树。
第 9章 树图 9.2.3
T h e b i g e l e p h a n t a t e
冠词 形容词 名词 动词冠词 名词直接宾语主语 谓语句子
t h e p e a n u t
第 9章 树定义 9.2.3 设 T是一棵根树 。
（ 1） 若 T的每个顶点至多有 m个儿子,则称 T为 m元树 。
（ 2） 若 T的每个顶点都有 m个或 0个儿子,则称 T为 m元正则树 。
（ 3） 若 T是 m元树,并且是有序的,则称 T为 m元有序树 。
（ 4） 若 T是 m元正则树,并且是有序的,则称 T为 m元有序正则树 。
第 9章 树
（ 5） 若 T是 m元正则树,且所有树叶的层数都等于树高,则称 T为 m元完全正则树 。
（ 6） 若 T是 m元完全正则树,且是有序的,则称 T
为 m元有序完全正则树 。
（ 7） 设 T是 m元树,如果为 T中每个顶点的儿子规定了确定的位置,则称 T为 m元位置树 。
例如,图 9.2.4中的 （ a） 和 （ b） 可看成相等的二元有序树,但是不是相同的二元位置树,图 （ c） 是二元正则树,图 （ d） 是二元完全正则树 。
第 9章 树图 9.2.4
( b )( a ) ( c ) ( d )
0 0
1
2
3 4 5
1 2
4 53
第 9章 树在所有的 m元树中,二元树居重要地位,其中二元有序正则树应用最为广泛 。 在二元有序正则树中,以分支点的两个儿子分别作为树根的两棵子树通常称为该分支点的左子树和右子树 。
第 9章 树图 9.2.5
a b
c d
e
×
＋
÷
－
第 9章 树
【 例 9.2.2】 用二元树 （ 见图 9.2.5） 表示算术表达式,（ a-b） ÷ (c× d+e） 。
对计算机来说,二元位置树最容易处理,因此常将有序树转化为二元位置树,步骤如下：
（ 1） 对于每个顶点只保留左儿子 。
（ 2） 兄弟间从左到右连接 。
（ 3） 对于每个分支点,保留的左儿子仍做左儿子,
右边邻接的顶点做右儿子 。
第 9章 树例如,图 9.2.6（ a） 是棵有序树,图 （ b） 是表示图 （ a） 的一棵二元树,图 （ c） 是相应的二元位置树 。
此方法可以推广到有序森林上去,只是将森林中每棵树的根看作兄弟 。 例如,图 9.2.7（ a） 是有序森林,
图 （ b） 是表示图 （ a） 的一棵二元树,图 （ c） 是相应的二元位置树 。
显然这种方法是可逆的,即任何一棵二元位置树,
也可以转化为有序树或有序森林 。
第 9章 树图 9.2.6
5 6 7 8 9 10
1 2 3 4
0
5 6 7 8 9 10
1
2 3 4
0
10
9
8
6
5
1
0
2
3
4
7
( a )
( b ) ( c )
第 9章 树图 9.2.7
13121110543
1 2 7 8 9
60
0
6
1 2 7
8
9
3 4 5 10 11 12 13
13
12
11
9
8
7
2
1054
3
1
0
6
( a )
( b ) ( c )
第 9章 树定义 9.2.4 设根树 T有 t片树叶 v1,v2,…,vt,它们分别带权 w1,w2,…,wt,则称 T为 （ 叶 ） 带权树,称
1
()
t
ii
i
W T l?
为 T的权,其中 li是 vi的层数 。
第 9章 树
【 例 9.2.3】 求 4片树叶分别带权 5,6,7,12的二元树的权 。
解 根据题意,我们构造出了四棵树叶具有不同权的带权二元树,如图 9.2.8所示,其中图 (a),(b),(c)、
(d)对应的二元树的权分别为
W（ T1） =61,W（ T2） =74，
W（ T3） =59,W（ T4） =60。
第 9章 树图 9.2.8
6 7
5
12
12 7
6
5
5 6
7
12
5 6 7 12
( a ) ( b ) ( c ) ( d )
第 9章 树由于树叶的层数不同,叶权也大小各异,因此树权是不同的,但其中必存在一棵权最小的二元树 。
定义 9.2.5 在所有叶带权 w1,w2,…,wt的二元树中,权最小的二元树称最优二元树,简称最优树 （ 又
Huffman 树 ） 。 如何寻求最优二元树？ 1952年哈夫曼 （ Huffman） 给出了求最优二元树的算法 。
Huffman 算法：
第 9章 树令 S={w1,w2,…,wt},w1≤w2≤…≤wt,wi是树叶 vi
所带的权（ i=1,2,…,t）。
（ 1） 在 S中选取两个最小的权 wi,wj,使它们对应的顶点 vi,vj做兄弟,得一分支点 vr,令其带权 wr=wi+wj。
（ 2） 从 S中去掉 wi,wj,再加入 wr。
（ 3）若 S中只有一个元素，则停止，否则转到（ 1）。
第 9章 树图 9.2.9
3
3 4
9
10
6
10
20
1
4
7
16
3
3 4
9 10
6
10
20
1
4
7
16
36
3
3 4
9
10
6
1
4
7
16
3
3 4
10
6
1
4
7
9 10
10
31
4
7
3 4 6 9 10
( a )
1 3 3 4 6 9 10
( b )
31
4
3 4 6 9 10
( c ) ( d )
( e ) ( f)
( g )
第 9章 树
【 例 9.2.4】 构造一棵带权 1,3,3,4,6,9,10的最优二元树,并求其权 W（ T） 。
解 构造过程如图 9.2.9中的 (a)～ (g)。 可得 W(T)=93。
一般来说,带权 w1,w2,…,wt的最优二元树并不唯一 。
Huffman 算法的正确性,先证下面的引理 。
引理 设 T是一棵带权 w1≤w2≤…wt的最优二元树,则带最小权 w1,w2的树叶 v1和 v2是兄弟,且以它们为儿子的分支点层数最大 。
第 9章 树证明 设 v是 T中离根最远的分支点,它的两个儿子 va
和 vb都是树叶,分别带权 wa和 wb,而不是 w1和 w2。 并且从根到 va和 vb的通路长度分别是 la和 lb,la=lb。 故有
la≥l1,lb≥l2
现在将 wa和 wb分别与 w1和 w2交换,得一棵新的二元树,记为 T′,则
W（ T） =w1l1+w2l2+…+wala+wblb+…
W（ T′） =wal1+wbl2+…+w1la+w2lb+…
第 9章 树于是
W（ T） -W（ T′） =(w1-wa)(w1-wa)+(w2-wb)(w2-wb)≥0
即 W（ T） ≥W（ T′），又 T是带权 w1,w2,…,wt的最优树，应有 W（ T） ≤W（ T′），因此 W（ T） =W（ T′）。
从而可知是将权 w1,w2与 wa,wb对调得到的最优树，故而 la=l1,lb=l2，即带权 w1和 w2的树叶是兄弟，且以它们为儿子的分支点层数最大。
第 9章 树定理 9.2.1（ Huffman定理 ) 设 T是带权 w1≤w2≤…≤wt
的最优二元树，如果将 T中带权为 w1和 w2的树叶去掉，
并以它们的父亲作树叶，且带权 w1+w2，记所得新树为,则 是带权为 w1+w2,w3,…,wt的最优树。
证明 由题意可知
^T^T
^
12( ) ( )W T W T
第 9章 树若 不是最优树,则必有另一棵带权 w1+w2，
w3…,wt的最优树 。 令 中带权 w1+w2的树叶生出两个儿子,分别带权 w1和 w2,得到新树,则
^T
~T ~T
~
12( ) ( )W T W T
因为 是带权为 w1+w2,w3,…,wt的最优树,所以
~T
~^( ) ( )W T W T?
第 9章 树如果,则必有 W（ T′） ＜ W（ T）,
与 T是带权 w1≤w2≤…≤wt的最优二元树矛盾,故 是带权为 w1+w2,w3,…,wt的最优树 。
由 Huffman定理易知 Huffman 算法的正确性 。
最优树的一个直接用处是前缀码的设计 。
~^( ) ( )W T W T?
^T
第 9章 树在远程通讯中,通常的电报是用 0和 1组成的序列来表示英文字母和标点符号的,英文有 26个字母,所以只要用长度为 5的等长字符串就可表达不同的字母了 。
发送端只要发送一条 0和 1组成的字符串,它正好是信息中字母对应的字符序列 。 在接收端,将这一长串字符分成长度为 5的序列就得到了相应的信息 。
第 9章 树但是字母在信息中出现的频繁程度是不一样的，
e和 t在单词中出现的频率要远远大于字母 q
和 z在单词中出现的频率。因此人们希望能用较短的字符串表示出现较频繁的字母，这样就可缩短信息字符串的总长度，显然如能实现这一想法是很有价值的。
对于发送端来说，发送长度不同的字符串并无困难，
但在接收端，怎样才能准确无误地将收到的一长串字符分割成长度不一的序列，即接收端如何译码呢？例如若用 00表示 t，用 01表示 e，用 0001表示 y，那么当接收到字符串 0001时，如何判断信息是 te还是 y 呢？为了解决这个问题，先引入前缀码的概念。
第 9章 树定义 9.2.6 设 a1a2…an是长度为 n的符号串,称其子串 a1,a1a2,…,a1a2…a n-1 分别为该符号串的长度为
1,2,…,n-1的前缀 。
设 A={β1,β2,…,βn}为一个符号串集合,若 A中任意两个不同的符号串 βi和 βj互不为前缀,则称 A为一组前缀码,若符号串中只出现两个符号,则称 A为二元前缀码 。
如 {0,10,110,1110,1111}是前缀码,{00，
001,011}不是前缀码 。 二元前缀码与正则二元树有一一对应关系 。
第 9章 树在一棵正则二元树中,将每个顶点和它的左儿子之间的边标记为 0；和它的右儿子之间的边标记为 1，
如图 9.2.10（ a） 所示,把从根到每个树叶所经过的边的标记序列作为树叶的标记,由于每片树叶的标记的前缀是它的祖先的标记,而不可能是任何其他树叶的标记,所以这些树叶的标记就是前缀码 。 由图 9.2.10
（ a） 可看出前缀码是 {000,001,01,10,11}。
相反，如果给定前缀码，也可找出对应的二元树。
例如，前缀码 {000,001,01,1}对应的二元树如图
9.2.10（ b）所示。
第 9章 树图 9.2.10
0 0 0 0 0 1
01 10 110 1
0
1
0 1
0 1
( a )
0 0 0 0 0 1
01
1
0 1
0
1
0 1
( b )
第 9章 树
【 例 9.2.5】 假设在通讯中,十进制数字出现的频率是
0,20%； 1,15%； 2,10%； 3,10%；
4,10% 5,5%； 6,10%； 7,5%； 8,10%；
9,5%
（ 1） 求传输它们的最佳前缀码 。
（ 2） 用最佳前缀码传输 10000个按上述频率出现的数字需要多少个二进制码？
（ 3） 它比用等长的二进制码传输 10000个数字节省多少个二进制码？
第 9章 树解 （ 1） 令 i对应叶权
wi,wi=100i,则 w0=20； w1=15；
w2=10； w3=10； w4=10； w5=5；
w6=10； w7=5； w8=10； w9=5。
构造一棵带权 5,5,5,10,10,10,10,10,15,20的最优二元树 （ 见图 9.2.11）,数字与前缀码的对应关系见图右侧 。
第 9章 树图 9.2.11
0 0 0 0 0 0 0 0 0 1
5 5
10
0 0 0 1
5
15
0 0 1
25
0 1 0
10 15
0 1 1 0 0 1 1 1
10 10
20
35
60
10
20
1 1 0 1 1 1
10 10
20
40
1 0 0
0 —1 0
1 —0 1 0
2 —1 1 1
3 —1 1 0
4 —0 1 1 1
5 —0 0 0 1
6 —0 1 1 0
7 —0 0 0 0 1
8 —0 0 1
9 —0 0 0 0 0
第 9章 树即最佳前缀码为,{10,010,111,110,001,0111，
0001,0110,00000,00001}。
（ 2 ） （ 2(20%+3 × （ 10%+15%+10%+10% ）
+4× （ 5%+10%+10% ） +5 × （ 5%+5% ））
× 10000=32500
即传输 10000个数字需 32500个二进制码 。
（ 3） 因为用等长码传输 10个数字码长为 4,即用等长的码传 10000个数字需 40000个二进制码,故用最佳前缀码传节省了 7500个二进制码 。
第 9章 树
9.3 例 题 选 解
【 例 9.3.1】 判断下列命题是否为真 。
（ 1） 若 n阶无向简单图 G的边数 m=n-1,则 G一定是树 。
（ 2） 若有向图 G仅有一个顶点的入度为 0,其余顶点的入度都是 1,则 G一定是有向树 。
（ 3） 任何树 T都至少有两片树叶 。
（ 4） 任何无向图 G都至少有一棵生成树 。
（ 5） 根树中最长初级通路的端点都是树叶 。
第 9章 树
（ 6） 无向连通图 G中的任何一条边都可以成为 G的某棵生成树的树枝 。
（ 7） （ n,m） 图的每棵生成树都有 n-1条树枝 。
（ 8） 以 1,1,1,1,2,2,4为度数列的非同构的树有 2棵 。
（ 9） 任何无向树的边均是桥 。
（ 10） G是 （ n,m） 无向图,若 m≥n,则 G中必有圈 。
（ 11） G是 （ n,m） 无向连通图,若要求 G的一棵生成树,必删去 G中的 m-n+1条边 。
第 9章 树图 9.3.1
第 9章 树解答与分析
（ 1） 假命题 。 当 G是非连通无向图时,顶点数和边数可能满足 m=n-1,但 G不是树 （ 如图 9.3.1所示 ） 。
（ 2） 假命题 。 当 G是非连通的有向图时,各点入度可能满足命题条件,但 G不是有向树 （ 如图 9.3.2所示 ） 。
第 9章 树图 9.3.2
第 9章 树
（ 3） 假命题 。 在平凡树中没有两片树叶 。
（ 4） 假命题 。 当且仅当 G是连通图时,G中才有生成树 。 例如图 9.3.1所示非连通图没有生成树 。
（ 5） 假命题 。 根树中最长初级通路的两个端点,一个是树叶,而另一个是树根 。
（ 6） 假命题 。 无向连通图 G中若有环,则环永远无法成为生成树的树枝,因为树中无圈 。
（ 7） 真命题 。 因为 （ n,m） 图的每棵生成树都是其生成子图,必有 n个顶点 。
（ 8） 真命题 。 如图 9.3.3所示,在一棵中两个 2度顶点邻接,在另一棵中两个 2度顶点不邻接 。
第 9章 树图 9.3.3
第 9章 树
（ 9） 真命题 。 由树的等价定义可知 。
（ 10） 真命题 。 若 G是非简单图,则 G中必有环或平行边,故 G中有圈 。
若 G是简单连通图,则 G中必有圈,否则 G是树,m=n-
1,这与 m≥n矛盾 。
若 G是简单非连通图，设其有 k个连通分支，若每个连通分支均无圈，则 G是森林，必有 m=n-k，与 m≥n矛盾，故至少有一个连通分支不是树，在此分支中有圈。
（ 11） 真命题。因每棵生成树必有 n-1条边。
第 9章 树
【 例 9.3.2】 （ 1） 若 T是高度为 k的二元树,则 T的树叶数最多为 2 k。
（ 2） 若 T是高度为 k的二元完全正则树,则 T的顶点数为 2 k+1 -1。
分析 （ 1） 在同样高度的二元树中,二元完全正则树的树叶最多,只需证明二元完全正则树的树叶数是
2 k片 。 （ 2） 利用 （ 1） 的结果即可 。
第 9章 树证明 （ 1） 对 k做归纳：
当 k=1时,树叶数 t=2=2 1,结论成立 。
假设 k=n时结论成立,t=2 n。
当 k=n+1时,因为在原来 2 n片树叶中,每片叶均增加了 2个儿子变成分支点,所以有树叶 t=2× 2 n=2 n+1,
结论成立 。
（ 2） 利用 （ 1） 知,在二元完全正则树中,高度为
k的顶点有 2 k个,故树高为 k的顶点总数为
1+2+2 2+… +2 k= 1
11 ( 2 1 ) 21
21
k
k
第 9章 树
【 例 9.3.3】 若图 G=〈 V,E〉 连通且 e∈ E,证明：
（ 1） e属于每一个生成树的充要条件是 e为 G的割边 。
（ 2） e不属于 G的任一个生成树的充要条件是 e为 G
中的环 。
分析 本题 （ 1）,（ 2） 均需从充分和必要两部分予以论证 。 在 （ 1） 中如 e属于每个生成树,需证 G中删去 e后必不连通,否则 e必不属于某个生成树,与题设矛盾 。 在 （ 2） 中要证明 e是环,可证 e是仅含其本身的一个回路,否则 e必属于某棵生成树 。
第 9章 树证明 （ 1） 先证充分性 。 设 e属于 G中每个生成树 T，
若 e不是割边,则 G-e连通,因此在 G-e中必存在生成树
T,因为 V（ G-e） =V（ G）,所以 T也是 G中的生成树 。
但 T中不包含 e,与题设矛盾 。
再证必要性 。 设 e是 G的割边,若有 G的某个生成树
T不包含 e,则 T+e必包含回路 C,且 e(C。 在 C中删去 e
后仍连通,故与 e是割边的假设矛盾 。
第 9章 树
（ 2）先证充分性。因为 G连通，必有生成树 T，设
e T，则 T+e包含回路 C，如果 C中除 e外另有边 e1∈ G，
构造 T′=T+e-e1，必仍连通，因为 |E（Ｔ ′） |=|E（ T）
|=m-1，故 T′也是 G的一棵生成树，但 T′包含 e，与题设矛盾。故 C中没有异于 e的边，即 e是 G中的环。再证必要性。若 e是 G中的环，则 e不能属于 G的任一棵生成树，
因为树是连通无回路的。
第 9章 树
【 例 9.3.4】 设 T是二元正则树,i为 T中的分支点数,
t为 T中的树叶数 。 证明,i=t-1。
证明 由正则树定义可知,二元正则树的每个分支点都有 2个儿子,所以 T中有 2i条边 。 由于树中的顶点数比树叶数多 1,故 T中有 2i+1个顶点 。 已知 T中有 i个分支点和 t片树叶,因此 2i+1=i+t,即 i=t-1。
第 9章 树习 题 九
1.画出所有非同构的 6阶无向树 。
2.无向树 T中有 7片树叶,3个 3度顶点,其余都是 4
度顶点,T中有多少个 4度顶点？
3.无向树 T中有 n2个 2度顶点,n3个 3度顶点,…,nk
个 k度顶点,T中有多少个 1度顶点？
第 9章 树图 9.1
第 9章 树
4.设有无向图 G如图 9.1所示 。
（ 1） 画出 G的关于完全图的补图 G。
（ 2） 画出 [AKG-]的所有不同构的生成树 。
5.如图 9.2所示两个无向图,其中实线边所示生成子图为
G的一棵生成树 T。
（ 1） 指出 T的所有弦,及 T所对应的基本回路系统 。
（ 2） 指出 T的所有树枝,及 T所对应的基本割集系统 。
第 9章 树图 9.2
e
c
d
f
b
a
G
1
e
c
d
b
a
f
g
h
( a ) ( b )
i
G
2
第 9章 树
6.求图 9.3所示的 2个带权图的最小生成树,计算它们的权,并写出关于这棵生成树的基本割集系统和基本回路系统 。
7.证明：对于 n个顶点的数,其顶点度数之和为 2n-2。
8.对于 n≥2，设 d1,d2,…,dn是 n个正整数，且
,证明：存在顶点度数为 d1,d2,…，
dn的一棵树。 1
22n i
i
dn
第 9章 树
1
3
5 5
7
3
4
6
2 1
1
8
9
2
7 6
5 4
10
3
( a ) ( b )
图 9.3
第 9章 树
9.证明,n＞ 2的连通图 G至少有两个顶点,将它们删去后得到的图仍是连通图 。
10.设 T是 k+1阶无向树,k≥1。 G是无向简单图,已知 δ（ G） ≥k,证明 G中存在与 T同构的子图 。
11.在连通图中,对给定的一棵生成树,设 D={e1，
e2,…,ek}是一个基本割集,其中 e1是树枝,e2,e3,…，
ek是生成树的弦,则 e1包含在对应于 ei（ i=2,3,…,k）
的基本回路中,且 e1不包含在任何其它的基本回路中 。
第 9章 树
12.在连通图中,对给定的一棵生成树,设 C={e1，
e2,…,ek}是一条基本回路,其中 e1是弦,e2,e3,…,ek
是树枝,则 e1包含在对应于 ei（ i=2,3,…,k） 的基本割集中,且 e1不包含在任何其它的基本割集中 。
13.证明：在二元正则树中,边的总数等于 2（ t-1）,
其中 t是树叶的数目 。
14.证明：二元正则树有奇数个顶点 。
15.求出对应于图 9.4所给树 （ a） 和森林 （ b） 的二元位置树 。
第 9章 树图 9.4
( a ) ( b )
第 9章 树
16.画出公式 （ p∨ （ ﹁ p∧ q）） ∧
（（ ﹁ p→ q） ∧ ﹁ r） 的根树表示 。
17.给定权 1,4,9,16,25,36,49,64,81,100。
（ 1） 构造一棵最优二元树 。
（ 2） 构造一棵最优三元树 。
（ 3） 说明如何构造一棵最优 t元树 。
第 9章 树
18.通讯中 a,b,c,d,e,f,g,N出现的频率分别为
a,25 % b,20 % c,15 % d,15 %
e,10 % f,5 % g,5 %
N,5 %
通过画出相应的最优二元树,求传输它们的最佳前缀码,并计算传输 10000个按上述比例出现的字母需要多少个二进制数码 。
9.1 无向树
9.2 根树及其应用
9.3 例题选解习 题 九第 9章 树
9.1 无 向 树定义 9.1.1 连通无回路的无向图称为无向树,简称树,记作 T。 树中的悬挂点称为树叶,其余顶点称为分支点 。 每个连通分支均为树的无向图称为森林 。 平凡图称为平凡树 。
例 9.1.1 图 9.1.1中 （ a）,（ b） 均是树,图 （ c） 是森林 。
由于树无环且无重边 （ 否则有回路 ）,所以树必是简单图 。 下面我们来讨论树的性质 。
第 9章 树图 9.1.1
( b )( a ) ( c )
第 9章 树定理 9.1.1 无向图 T是树,当且仅当以下五条之一成立 。
（ 1） T中无回路且 m=n-1,其中 m为边数,n为顶点数 。
（ 2） T是连通图且 m=n-1。
（ 3） T中无回路,但增一条边,则得到一条且仅一条初级回路 。
（ 4） T连通且每条边均是桥 。
（ 5） 每对顶点间有唯一的一条初级通路 。
第 9章 树证明 ① 由树的定义可得 （ 1） 。
施归纳于顶点数 n。 当 n=1时,m=0,则 m=n-1成立 。
假设当 n=k时,m=n-1成立 。 则当 n=k+1时,因为树是连通的且无回路,所以至少有一个度数为 1的顶点 v，
从树中删去 v和与它关联的边,则得到 k个顶点的树 T′。
根据假设它有 k-1条边,现将 v和与它关联的边加到 T′上还原成树 T,则 T有 k+1个顶点,k条边,边数比顶点数少 1,故 m=n-1成立 。
第 9章 树
② 由 （ 1） 可得 （ 2） 。
再证反证法,若图 T不连通,设 T有 k个连通分支 T1，
T2,…,Tk（ k≥2）,其顶点数分别为 n1,n2,…,nk，
则有
1
k
i
i
nn
边数分别为 m1,m2,…,mk，则有
1
k
i
i
mm
第 9章 树因此,有
11
( 1 ) 1
kk
ii
ii
m m n n k n
即 m＜ n-1，这与 m=n-1矛盾，故 T是连通的 m=n-1图。
第 9章 树
③ 由 （ 2） 可得 （ 3） 。
若 T是连通图并有 n-1条边 。 施归纳于顶点数 n。
当 n=2时,m=n-1=1,所以没有回路,如果增加一条边,只能得到唯一的一个回路 。
假设 n=k时,命题成立 。 则当 n=k+1时,因为 T是连通的并有 n-1条边,所以每个顶点都有 d（ v） ≥1,并且至少有一个顶点 v0,满足 d（ v0） =1。 否则,如果每个顶点 v都有 d（ v） ≥2,那么必然会有总度数 2m≥2n,即
m≥n,这与条件 m=n-1矛盾 。 因此至少有一个顶点 v0，
满足 d（ v0） =1。
第 9章 树删去 v0及其关联的边,得到图 T′,由假设知 T′无回路,现将 v0及其关联的边再加到 T′,则还原成 T,所以 T
没有回路 。
如果在连通图 T中增加一条新边 （ vi,vj）,则 （ vi，
vj） 与 T中从 vi到 vj的一条初级路径构成一个初级回路,
且该回路必定是唯一的,否则当删去新边 （ vi,vj） 时,
T中必有回路,产生矛盾 。
第 9章 树
④ 由 （ 3） 可得 （ 4） 。
若图 T不连通,则存在两个顶点 vi和 vj,在 vi,vj之间没有路径,如果增加边 （ vi,vj） 不产生回路,这与
（ 3） 矛盾,因此 T连通 。 因为 T中无回路,所以删去任意一条边,图必不连通 。 故图中每一条边均是桥 。
⑤由（ 4）可得（ 5）。
由图的连通性可知,任意两个顶点之间都有一条通路,是初级通路 。 如果这条初级通路不唯一,则 T中必有回路,删去回路上的任意一条边,图仍连通,与
（ 4） 矛盾 。 故任意两个顶点之间有唯一一条初级回路 。
第 9章 树
⑥ 由 （ 5） 可得树的定义 。
每对顶点之间有唯一一条初级通路,那么 T必连通,
若有回路,则回路上任意两个顶点之间有两条初级通路,与 （ 5） 矛盾 。 故图连通且无回路,是树 。
第 9章 树定理 9.1.2 任何一棵非平凡树 T至少有两片树叶 。
证明 设 T是 （ n,m） 图,n≥2,有 k片树叶,其余顶点度数均大于或等于 2。 则
1
1
( ) 2 ( ) 2
( ) 2 2 ( ) 2 2
n
i
i
n
i
i
d n k k n k
d m n k n
而所以 2n-2≥2n-k，即 k≥2。
第 9章 树
【 例 9.1.2】 T是一棵树,有两个顶点度数为 2,一个顶点度数为 3,三个顶点度数为 4,T有几片树叶？
解 设树 T有 x片树叶,则 T的顶点数
n=2+1+3+x
T的边数
m=n-1=5+x
又由握手定理
1
2 ( )
n
i
i
md?
第 9章 树得
2 · （ 5+x） =2·2+3·1+4·3+x
所以 x=9,即树 T有 9片树叶 。
请读者自己画出两棵具有上述度数列的非同构的树 。
第 9章 树
【 例 9.1.3】 画出所有非同构的七阶无向树 。
解 设 Ti是七阶无向树。因为 n=7，所以 m=6，又因为,所以七个顶点分配 12度，且由树是连通简单图知 1≤d（ v） ≤6。则 Ti的度数列必是下列情况之一。
1
2 ( )n i
i
md?
第 9章 树
（ 1） 1,1,2,2,2,2,2
（ 2） 1,1,1,2,2,2,3
（ 3） 1,1,1,1,2.2,4
（ 4） 1,1,1,1,2,3,3
（ 5） 1,1,1,1,1,2,5
（ 6） 1,1,1,1,1,3,4
（ 7） 1,1,1,1,1,1,6
第 9章 树生成树有一些图,本身不是树,但它的某些子图却是树,
其中很重要的一类是生成树 。
定义 9.1.2 若无向图 G的一个生成子图 T是树，则称 T
是 G的一棵生成树。
例如图 9.1.3中,T1和 T2是图 G的两棵生成树 。
由图 9.1.3可见,G与 T1,T2的区别是 G中有回路,而它的生成树无回路,因此要在一个连通图 G中找到一棵生成树,只要不断地从 G的回路上删去一条边,最后所得无回路的子图就是 G的一棵生成树 。 于是有以下定理 。
第 9章 树图 9.1.2
T
1
T
2
T
7
T
8
T
9
T
10
T
11
T
3
T
4
T
5
T
6
第 9章 树图 9.1.3
e
2
e
3
e
4
e
1
e
5
e
6
e
7 e
8
e
9
e
10
e
2
e
3
e
1
e
6
e
7
e
8
e
2
e
4
e
1
e
6
e
7 e
9
T
2
T
1
G
1
2
3
4
5
6 7
1 2
3
4
5
6 7
1 2
3
4
5
6 7
第 9章 树定理 9.1.3 无向图 G有生成树的充分必要条件是 G为连通图 。
证明 先采用反证法来证明必要性 。
若 G不连通,则它的任何生成子图也不连通,因此不可能有生成树,与 G有生成树矛盾,故 G是连通图 。
再证充分性 。
设 G连通,则 G必有连通的生成子图,令 T是 G的含有边数最少的生成子图,于是 T中必无回路 （ 否则删去回路上的一条边不影响连通性,与 T含边数最少矛盾 ）,
故 T是一棵树,即生成树 。
第 9章 树如果 T是 G的一棵生成树,则称 G在 T中的边为 T的树枝,G不在 T中的边为 T的弦,T的所有的弦的集合的导出子图称 T的余树 。 易知,余树不一定是树,更不一定是生成树 。
一般情况,图 G的生成树不是唯一的,这里的不唯一有两个含义,一种是标定图的生成树所含的树枝不同,另一种是不考虑标定的生成树是不同构的 。 但无论怎样,一个连通的 （ n,m） 图,其任意一棵生成树的树枝数一定是 n-1,从而弦数也是固定不变的 m-n+1。
由树的性质可知,对于图 G的一棵生成树 T,每增加一条弦,便得到一条初级回路 。
第 9章 树例如,在图 9.1.3所示的 T1中：
加弦 e5,得初级回路 e2e3e5；
加弦 e4,得初级回路 e1e3e4；
加弦 e9,得初级回路 e6e8e9；
加弦 e10,得初级回路 e7e8e10。
同样,在图 9.1.3所示的 T2中,分别加弦 e3,e5,e8，
e10,则分别产生初级回路 e1e3e4,e1e4e5e2,e6e8e9，
e7e6e9e10。
第 9章 树这些初级回路有一个共同特点：它们中均只含一条弦,其余的边均是树枝,我们称这样的回路为基本回路 。 对于 G的每棵生成树 T,m-n+1条弦对应着 m-n+1
个基本回路,这些基本回路构成的集合称为对应 T的基本回路系统 。 显然不同的生成树对应不同的基本回路系统 。 如图 9.1.3中,G对应 T1的基本回路系统为 {e2e3e5，
e1e3e4,e6e8e9,e7e8e10},G对应 T2的基本回路系统为
{e1e3e4,e1e4e5e2,e6e8e9,e7e6e9e10}。 但是它们所含的元素个数均是 m-n+1=4。 在电路网络分析中,基本回路具有重要意义 。
第 9章 树另一方面,从树 T中删去一边,便将 T分成两棵树,
即两个连通分支,图 G中连接这两个连通分支的边的集合,称为对应于这条边的基本 （ 边 ） 割集 。
例如在图 9.1.3中的 G和 T1：
对应树枝 e1,有基本割集 {e1,e4}；
对应树枝 e2,有基本割集 {e2,e5}；
对应树枝 e3,有基本割集 {e3,e4,e5}；
对应树枝 e6,有基本割集 {e6,e9}；
对应树枝 e7,有基本割集 {e7,e10}；
对应树枝 e8,有基本割集 {e8,e9,e10}；
第 9章 树同样对于图 9.1.3中的 G和 T2，对应树枝 e1,e2,e4，
e6,e7,e9，分别有基本割集,{e1,e3,e5},{e2,e5}，
{e4,e3,e5},{e6,e8,e 10 },{e7,e 10 },{e9，
e 10}。
第 9章 树这些割集所具有的共同特点是：每个割集中均只含生成树的一个树枝,其余的均是弦 。 对于图 G的任何一棵生成树 T,对应每个树枝的基本割集所构成的集合,
称为对应 T的基本割集系统 。 如图 9.1.3中,G对应 T2的基本割集系统为 {{e1,e3,e5},{e2,e5},{e4,e3,e5}，
{e6,e8,e 10 },{e7,e 10 },{e9,e 10 }},显然不同的生成树有不同的基本割集系统,但其元素个数均为 n-1。
第 9章 树最小生成树带权图的生成树是实际应用较多的树,所谓权就是附加在图上的信息,通常是实数,权加在边上的称边权图,加在点上的称点权图,这里我们只涉及边权图 。
定义 9.1.3 对图 G的每条边附加上一个实数 ω（ e）,
称 ω（ e） 为边 e上的权,G连同附加在各边上的权称为带权图,常记作 G=〈 V,E,ω〉 。 设 G1是 G的任意子图,
G1的权,记作 ω（ G1） 。
1()
()
e E G
e?
第 9章 树一个很实际的问题是：假设你是一个设计师,欲架设连接 n个村镇的电话线,每个村镇设一个交换站 。
已知由 i村到 j村的线路 e=（ vi,vj） 造价为 ω（ e） =w ij
,要保证任意两个村镇之间均可通话,请设计一个方案,使总造价最低 。 这个问题的数学模型为：在已知的带权图上求权最小的生成树 。
第 9章 树定义 9.1.4 设无向连通带权图 G=〈 V,E,ω〉,G中带权最小的生成树称为 G的最小生成树 （ 最优树 ） 。
定理 9.1.4 设连通图 G的各边的权均不相同,则回路中权最大的边必不在 G的最小生成树中 。
证明略。
第 9章 树定理的结论是显然的,由此寻找带权图 G的最小生成树,可以采用破圈法,即在图 G中不断去掉回路中权最大的边 。
求最小生成树的另一个更有效率的算法是克鲁斯卡尔 （ Kruskal ） 的避圈法：
（ 1） 选 e1∈ E（ G）,使得 ω(e1） = min 。
（ 2） 若 e1,e2,…,ei已选好,则从 E（ G） -{e1，
e2,…,ei}中选取 e i+1,使得 G［ {e1,e2,…,ei}］ 中无圈,且 ω（ e i+1 ） =min。
（ 3） 继续进行到选得 e n-1 为止 。
第 9章 树
【 例 9.1.4】 求图 9.1.4（ a）所示带权图的最小生成树。（它的实际背景是北京与巴黎、纽约、东京、伦敦、墨西哥城这六大城市间的航空路线距离图，单位是百公里。）
解 图 9.1.4（ b） 中实线是用破圈法得到的最小生成树 （ 虚线是去掉的回路上的边 ）,图 9.1.4（ c） 中粗实线是用避圈法得到的最小生成树 。 其权均为 122。
事实上因为边（ L,B）与（ P,B）的权相等，所以最小生成树并不唯一（如图 9.1.4的（ b）与（ c）），
但是它们的权是相等的。
第 9章 树图 9.1.4
L
60
51
56
70
2
2135
68
68
78
6113
51 36
57
T
B
P
NY
MG
L
60
51
56
70
2
2135
68
68
78
6113
51 36
57
T
B
P
NY
MG
L
60
51
56
70
2
2135
68
68
78
6113
51 36
57
T
B
P
NY
MG
( b )( a ) ( c )
第 9章 树
9.2 根树及其应用定义 9.2.1 T是一棵有向树,若 T中恰有一个顶点入度为 0,其余顶点的入度均为 1,则称 T为根树 。 入度为
0的顶点称树根,出度为 0的顶点称树叶,入度为 1,出度不为 0的顶点称内点,内点和树根统称为分支点 。
例如图 9.2.1中的 （ a）,（ b）,（ c） 均是有向树,
但只有图 （ c） 是根树 。
第 9章 树图 9.2.1
( b )( a ) ( c )
1
0
2
3
4
5
6
7
8
第 9章 树由定义和例题易知,对于 （ n,m） 根树,同样有
m=n-1,且根树一定是有向树,但反之未必 。
在根树中,从树根 v0到每个顶点 vi有唯一一条初级通路,该通路的长度称为点 vi的层数,记作 l（ vi）,其中最大的层数称为树高,记作 h（ T） 。
第 9章 树习惯上将根树画成树根在上,各边箭头均朝下的形状 （ 如图 9.2.1（ c） 所示 ）,并为方便起见,略去各边上的箭头,可以看出,根树上的各个顶点有了层次关系 。
一棵根树常常被形象的比作一棵家族树,如果顶点 u邻接到顶点 v,则称 u为 v的父亲,v为 u的儿子；共有同一个父亲的顶点称为兄弟；如果顶点 u可达顶点 v，
则称 u是 v的祖先,v是 u的后代 。 在根树 T中,所有的内点,树叶均是树根的后代,由某个顶点 vi及其所有的后代构成的导出子图称为 T的以 vi为根的子根树 。
第 9章 树例如图 9.2.1（ c） 中,v3是 v1的儿子,v1是 v3的父亲；
v4与 v5是兄弟,
T′=G［ {v2,v4,v5,v6,v7,v8}］ 是以 v2为根的 T的子根树 。
定义 9.2.2 在根树 T中,如果每一层的顶点都按一定的次序排列,则称 T为有序树 。 在画有序树时,常假定每一层的顶点是按从左到右排序的 。
例如图 9.2.2中的 （ a） 和 （ b） 表示的是不同的有序树 。 而如果不考虑同层顶点的次序,则图 9.2.2（ a）
和 （ b） 表示的是同一棵根树 。
第 9章 树图 9.2.2
( b )( a )
第 9章 树
【 例 9.2.1】 英语句子,The big elephant ate the
peanut” 可以图解为图 9.2.3，称之为这个英语句子的语法树。可见，句子的语法树是一棵有序树。
第 9章 树图 9.2.3
T h e b i g e l e p h a n t a t e
冠词 形容词 名词 动词冠词 名词直接宾语主语 谓语句子
t h e p e a n u t
第 9章 树定义 9.2.3 设 T是一棵根树 。
（ 1） 若 T的每个顶点至多有 m个儿子,则称 T为 m元树 。
（ 2） 若 T的每个顶点都有 m个或 0个儿子,则称 T为 m元正则树 。
（ 3） 若 T是 m元树,并且是有序的,则称 T为 m元有序树 。
（ 4） 若 T是 m元正则树,并且是有序的,则称 T为 m元有序正则树 。
第 9章 树
（ 5） 若 T是 m元正则树,且所有树叶的层数都等于树高,则称 T为 m元完全正则树 。
（ 6） 若 T是 m元完全正则树,且是有序的,则称 T
为 m元有序完全正则树 。
（ 7） 设 T是 m元树,如果为 T中每个顶点的儿子规定了确定的位置,则称 T为 m元位置树 。
例如,图 9.2.4中的 （ a） 和 （ b） 可看成相等的二元有序树,但是不是相同的二元位置树,图 （ c） 是二元正则树,图 （ d） 是二元完全正则树 。
第 9章 树图 9.2.4
( b )( a ) ( c ) ( d )
0 0
1
2
3 4 5
1 2
4 53
第 9章 树在所有的 m元树中,二元树居重要地位,其中二元有序正则树应用最为广泛 。 在二元有序正则树中,以分支点的两个儿子分别作为树根的两棵子树通常称为该分支点的左子树和右子树 。
第 9章 树图 9.2.5
a b
c d
e
×
＋
÷
－
第 9章 树
【 例 9.2.2】 用二元树 （ 见图 9.2.5） 表示算术表达式,（ a-b） ÷ (c× d+e） 。
对计算机来说,二元位置树最容易处理,因此常将有序树转化为二元位置树,步骤如下：
（ 1） 对于每个顶点只保留左儿子 。
（ 2） 兄弟间从左到右连接 。
（ 3） 对于每个分支点,保留的左儿子仍做左儿子,
右边邻接的顶点做右儿子 。
第 9章 树例如,图 9.2.6（ a） 是棵有序树,图 （ b） 是表示图 （ a） 的一棵二元树,图 （ c） 是相应的二元位置树 。
此方法可以推广到有序森林上去,只是将森林中每棵树的根看作兄弟 。 例如,图 9.2.7（ a） 是有序森林,
图 （ b） 是表示图 （ a） 的一棵二元树,图 （ c） 是相应的二元位置树 。
显然这种方法是可逆的,即任何一棵二元位置树,
也可以转化为有序树或有序森林 。
第 9章 树图 9.2.6
5 6 7 8 9 10
1 2 3 4
0
5 6 7 8 9 10
1
2 3 4
0
10
9
8
6
5
1
0
2
3
4
7
( a )
( b ) ( c )
第 9章 树图 9.2.7
13121110543
1 2 7 8 9
60
0
6
1 2 7
8
9
3 4 5 10 11 12 13
13
12
11
9
8
7
2
1054
3
1
0
6
( a )
( b ) ( c )
第 9章 树定义 9.2.4 设根树 T有 t片树叶 v1,v2,…,vt,它们分别带权 w1,w2,…,wt,则称 T为 （ 叶 ） 带权树,称
1
()
t
ii
i
W T l?
为 T的权,其中 li是 vi的层数 。
第 9章 树
【 例 9.2.3】 求 4片树叶分别带权 5,6,7,12的二元树的权 。
解 根据题意,我们构造出了四棵树叶具有不同权的带权二元树,如图 9.2.8所示,其中图 (a),(b),(c)、
(d)对应的二元树的权分别为
W（ T1） =61,W（ T2） =74，
W（ T3） =59,W（ T4） =60。
第 9章 树图 9.2.8
6 7
5
12
12 7
6
5
5 6
7
12
5 6 7 12
( a ) ( b ) ( c ) ( d )
第 9章 树由于树叶的层数不同,叶权也大小各异,因此树权是不同的,但其中必存在一棵权最小的二元树 。
定义 9.2.5 在所有叶带权 w1,w2,…,wt的二元树中,权最小的二元树称最优二元树,简称最优树 （ 又
Huffman 树 ） 。 如何寻求最优二元树？ 1952年哈夫曼 （ Huffman） 给出了求最优二元树的算法 。
Huffman 算法：
第 9章 树令 S={w1,w2,…,wt},w1≤w2≤…≤wt,wi是树叶 vi
所带的权（ i=1,2,…,t）。
（ 1） 在 S中选取两个最小的权 wi,wj,使它们对应的顶点 vi,vj做兄弟,得一分支点 vr,令其带权 wr=wi+wj。
（ 2） 从 S中去掉 wi,wj,再加入 wr。
（ 3）若 S中只有一个元素，则停止，否则转到（ 1）。
第 9章 树图 9.2.9
3
3 4
9
10
6
10
20
1
4
7
16
3
3 4
9 10
6
10
20
1
4
7
16
36
3
3 4
9
10
6
1
4
7
16
3
3 4
10
6
1
4
7
9 10
10
31
4
7
3 4 6 9 10
( a )
1 3 3 4 6 9 10
( b )
31
4
3 4 6 9 10
( c ) ( d )
( e ) ( f)
( g )
第 9章 树
【 例 9.2.4】 构造一棵带权 1,3,3,4,6,9,10的最优二元树,并求其权 W（ T） 。
解 构造过程如图 9.2.9中的 (a)～ (g)。 可得 W(T)=93。
一般来说,带权 w1,w2,…,wt的最优二元树并不唯一 。
Huffman 算法的正确性,先证下面的引理 。
引理 设 T是一棵带权 w1≤w2≤…wt的最优二元树,则带最小权 w1,w2的树叶 v1和 v2是兄弟,且以它们为儿子的分支点层数最大 。
第 9章 树证明 设 v是 T中离根最远的分支点,它的两个儿子 va
和 vb都是树叶,分别带权 wa和 wb,而不是 w1和 w2。 并且从根到 va和 vb的通路长度分别是 la和 lb,la=lb。 故有
la≥l1,lb≥l2
现在将 wa和 wb分别与 w1和 w2交换,得一棵新的二元树,记为 T′,则
W（ T） =w1l1+w2l2+…+wala+wblb+…
W（ T′） =wal1+wbl2+…+w1la+w2lb+…
第 9章 树于是
W（ T） -W（ T′） =(w1-wa)(w1-wa)+(w2-wb)(w2-wb)≥0
即 W（ T） ≥W（ T′），又 T是带权 w1,w2,…,wt的最优树，应有 W（ T） ≤W（ T′），因此 W（ T） =W（ T′）。
从而可知是将权 w1,w2与 wa,wb对调得到的最优树，故而 la=l1,lb=l2，即带权 w1和 w2的树叶是兄弟，且以它们为儿子的分支点层数最大。
第 9章 树定理 9.2.1（ Huffman定理 ) 设 T是带权 w1≤w2≤…≤wt
的最优二元树，如果将 T中带权为 w1和 w2的树叶去掉，
并以它们的父亲作树叶，且带权 w1+w2，记所得新树为,则 是带权为 w1+w2,w3,…,wt的最优树。
证明 由题意可知
^T^T
^
12( ) ( )W T W T
第 9章 树若 不是最优树,则必有另一棵带权 w1+w2，
w3…,wt的最优树 。 令 中带权 w1+w2的树叶生出两个儿子,分别带权 w1和 w2,得到新树,则
^T
~T ~T
~
12( ) ( )W T W T
因为 是带权为 w1+w2,w3,…,wt的最优树,所以
~T
~^( ) ( )W T W T?
第 9章 树如果,则必有 W（ T′） ＜ W（ T）,
与 T是带权 w1≤w2≤…≤wt的最优二元树矛盾,故 是带权为 w1+w2,w3,…,wt的最优树 。
由 Huffman定理易知 Huffman 算法的正确性 。
最优树的一个直接用处是前缀码的设计 。
~^( ) ( )W T W T?
^T
第 9章 树在远程通讯中,通常的电报是用 0和 1组成的序列来表示英文字母和标点符号的,英文有 26个字母,所以只要用长度为 5的等长字符串就可表达不同的字母了 。
发送端只要发送一条 0和 1组成的字符串,它正好是信息中字母对应的字符序列 。 在接收端,将这一长串字符分成长度为 5的序列就得到了相应的信息 。
第 9章 树但是字母在信息中出现的频繁程度是不一样的，
e和 t在单词中出现的频率要远远大于字母 q
和 z在单词中出现的频率。因此人们希望能用较短的字符串表示出现较频繁的字母，这样就可缩短信息字符串的总长度，显然如能实现这一想法是很有价值的。
对于发送端来说，发送长度不同的字符串并无困难，
但在接收端，怎样才能准确无误地将收到的一长串字符分割成长度不一的序列，即接收端如何译码呢？例如若用 00表示 t，用 01表示 e，用 0001表示 y，那么当接收到字符串 0001时，如何判断信息是 te还是 y 呢？为了解决这个问题，先引入前缀码的概念。
第 9章 树定义 9.2.6 设 a1a2…an是长度为 n的符号串,称其子串 a1,a1a2,…,a1a2…a n-1 分别为该符号串的长度为
1,2,…,n-1的前缀 。
设 A={β1,β2,…,βn}为一个符号串集合,若 A中任意两个不同的符号串 βi和 βj互不为前缀,则称 A为一组前缀码,若符号串中只出现两个符号,则称 A为二元前缀码 。
如 {0,10,110,1110,1111}是前缀码,{00，
001,011}不是前缀码 。 二元前缀码与正则二元树有一一对应关系 。
第 9章 树在一棵正则二元树中,将每个顶点和它的左儿子之间的边标记为 0；和它的右儿子之间的边标记为 1，
如图 9.2.10（ a） 所示,把从根到每个树叶所经过的边的标记序列作为树叶的标记,由于每片树叶的标记的前缀是它的祖先的标记,而不可能是任何其他树叶的标记,所以这些树叶的标记就是前缀码 。 由图 9.2.10
（ a） 可看出前缀码是 {000,001,01,10,11}。
相反，如果给定前缀码，也可找出对应的二元树。
例如，前缀码 {000,001,01,1}对应的二元树如图
9.2.10（ b）所示。
第 9章 树图 9.2.10
0 0 0 0 0 1
01 10 110 1
0
1
0 1
0 1
( a )
0 0 0 0 0 1
01
1
0 1
0
1
0 1
( b )
第 9章 树
【 例 9.2.5】 假设在通讯中,十进制数字出现的频率是
0,20%； 1,15%； 2,10%； 3,10%；
4,10% 5,5%； 6,10%； 7,5%； 8,10%；
9,5%
（ 1） 求传输它们的最佳前缀码 。
（ 2） 用最佳前缀码传输 10000个按上述频率出现的数字需要多少个二进制码？
（ 3） 它比用等长的二进制码传输 10000个数字节省多少个二进制码？
第 9章 树解 （ 1） 令 i对应叶权
wi,wi=100i,则 w0=20； w1=15；
w2=10； w3=10； w4=10； w5=5；
w6=10； w7=5； w8=10； w9=5。
构造一棵带权 5,5,5,10,10,10,10,10,15,20的最优二元树 （ 见图 9.2.11）,数字与前缀码的对应关系见图右侧 。
第 9章 树图 9.2.11
0 0 0 0 0 0 0 0 0 1
5 5
10
0 0 0 1
5
15
0 0 1
25
0 1 0
10 15
0 1 1 0 0 1 1 1
10 10
20
35
60
10
20
1 1 0 1 1 1
10 10
20
40
1 0 0
0 —1 0
1 —0 1 0
2 —1 1 1
3 —1 1 0
4 —0 1 1 1
5 —0 0 0 1
6 —0 1 1 0
7 —0 0 0 0 1
8 —0 0 1
9 —0 0 0 0 0
第 9章 树即最佳前缀码为,{10,010,111,110,001,0111，
0001,0110,00000,00001}。
（ 2 ） （ 2(20%+3 × （ 10%+15%+10%+10% ）
+4× （ 5%+10%+10% ） +5 × （ 5%+5% ））
× 10000=32500
即传输 10000个数字需 32500个二进制码 。
（ 3） 因为用等长码传输 10个数字码长为 4,即用等长的码传 10000个数字需 40000个二进制码,故用最佳前缀码传节省了 7500个二进制码 。
第 9章 树
9.3 例 题 选 解
【 例 9.3.1】 判断下列命题是否为真 。
（ 1） 若 n阶无向简单图 G的边数 m=n-1,则 G一定是树 。
（ 2） 若有向图 G仅有一个顶点的入度为 0,其余顶点的入度都是 1,则 G一定是有向树 。
（ 3） 任何树 T都至少有两片树叶 。
（ 4） 任何无向图 G都至少有一棵生成树 。
（ 5） 根树中最长初级通路的端点都是树叶 。
第 9章 树
（ 6） 无向连通图 G中的任何一条边都可以成为 G的某棵生成树的树枝 。
（ 7） （ n,m） 图的每棵生成树都有 n-1条树枝 。
（ 8） 以 1,1,1,1,2,2,4为度数列的非同构的树有 2棵 。
（ 9） 任何无向树的边均是桥 。
（ 10） G是 （ n,m） 无向图,若 m≥n,则 G中必有圈 。
（ 11） G是 （ n,m） 无向连通图,若要求 G的一棵生成树,必删去 G中的 m-n+1条边 。
第 9章 树图 9.3.1
第 9章 树解答与分析
（ 1） 假命题 。 当 G是非连通无向图时,顶点数和边数可能满足 m=n-1,但 G不是树 （ 如图 9.3.1所示 ） 。
（ 2） 假命题 。 当 G是非连通的有向图时,各点入度可能满足命题条件,但 G不是有向树 （ 如图 9.3.2所示 ） 。
第 9章 树图 9.3.2
第 9章 树
（ 3） 假命题 。 在平凡树中没有两片树叶 。
（ 4） 假命题 。 当且仅当 G是连通图时,G中才有生成树 。 例如图 9.3.1所示非连通图没有生成树 。
（ 5） 假命题 。 根树中最长初级通路的两个端点,一个是树叶,而另一个是树根 。
（ 6） 假命题 。 无向连通图 G中若有环,则环永远无法成为生成树的树枝,因为树中无圈 。
（ 7） 真命题 。 因为 （ n,m） 图的每棵生成树都是其生成子图,必有 n个顶点 。
（ 8） 真命题 。 如图 9.3.3所示,在一棵中两个 2度顶点邻接,在另一棵中两个 2度顶点不邻接 。
第 9章 树图 9.3.3
第 9章 树
（ 9） 真命题 。 由树的等价定义可知 。
（ 10） 真命题 。 若 G是非简单图,则 G中必有环或平行边,故 G中有圈 。
若 G是简单连通图,则 G中必有圈,否则 G是树,m=n-
1,这与 m≥n矛盾 。
若 G是简单非连通图，设其有 k个连通分支，若每个连通分支均无圈，则 G是森林，必有 m=n-k，与 m≥n矛盾，故至少有一个连通分支不是树，在此分支中有圈。
（ 11） 真命题。因每棵生成树必有 n-1条边。
第 9章 树
【 例 9.3.2】 （ 1） 若 T是高度为 k的二元树,则 T的树叶数最多为 2 k。
（ 2） 若 T是高度为 k的二元完全正则树,则 T的顶点数为 2 k+1 -1。
分析 （ 1） 在同样高度的二元树中,二元完全正则树的树叶最多,只需证明二元完全正则树的树叶数是
2 k片 。 （ 2） 利用 （ 1） 的结果即可 。
第 9章 树证明 （ 1） 对 k做归纳：
当 k=1时,树叶数 t=2=2 1,结论成立 。
假设 k=n时结论成立,t=2 n。
当 k=n+1时,因为在原来 2 n片树叶中,每片叶均增加了 2个儿子变成分支点,所以有树叶 t=2× 2 n=2 n+1,
结论成立 。
（ 2） 利用 （ 1） 知,在二元完全正则树中,高度为
k的顶点有 2 k个,故树高为 k的顶点总数为
1+2+2 2+… +2 k= 1
11 ( 2 1 ) 21
21
k
k
第 9章 树
【 例 9.3.3】 若图 G=〈 V,E〉 连通且 e∈ E,证明：
（ 1） e属于每一个生成树的充要条件是 e为 G的割边 。
（ 2） e不属于 G的任一个生成树的充要条件是 e为 G
中的环 。
分析 本题 （ 1）,（ 2） 均需从充分和必要两部分予以论证 。 在 （ 1） 中如 e属于每个生成树,需证 G中删去 e后必不连通,否则 e必不属于某个生成树,与题设矛盾 。 在 （ 2） 中要证明 e是环,可证 e是仅含其本身的一个回路,否则 e必属于某棵生成树 。
第 9章 树证明 （ 1） 先证充分性 。 设 e属于 G中每个生成树 T，
若 e不是割边,则 G-e连通,因此在 G-e中必存在生成树
T,因为 V（ G-e） =V（ G）,所以 T也是 G中的生成树 。
但 T中不包含 e,与题设矛盾 。
再证必要性 。 设 e是 G的割边,若有 G的某个生成树
T不包含 e,则 T+e必包含回路 C,且 e(C。 在 C中删去 e
后仍连通,故与 e是割边的假设矛盾 。
第 9章 树
（ 2）先证充分性。因为 G连通，必有生成树 T，设
e T，则 T+e包含回路 C，如果 C中除 e外另有边 e1∈ G，
构造 T′=T+e-e1，必仍连通，因为 |E（Ｔ ′） |=|E（ T）
|=m-1，故 T′也是 G的一棵生成树，但 T′包含 e，与题设矛盾。故 C中没有异于 e的边，即 e是 G中的环。再证必要性。若 e是 G中的环，则 e不能属于 G的任一棵生成树，
因为树是连通无回路的。
第 9章 树
【 例 9.3.4】 设 T是二元正则树,i为 T中的分支点数,
t为 T中的树叶数 。 证明,i=t-1。
证明 由正则树定义可知,二元正则树的每个分支点都有 2个儿子,所以 T中有 2i条边 。 由于树中的顶点数比树叶数多 1,故 T中有 2i+1个顶点 。 已知 T中有 i个分支点和 t片树叶,因此 2i+1=i+t,即 i=t-1。
第 9章 树习 题 九
1.画出所有非同构的 6阶无向树 。
2.无向树 T中有 7片树叶,3个 3度顶点,其余都是 4
度顶点,T中有多少个 4度顶点？
3.无向树 T中有 n2个 2度顶点,n3个 3度顶点,…,nk
个 k度顶点,T中有多少个 1度顶点？
第 9章 树图 9.1
第 9章 树
4.设有无向图 G如图 9.1所示 。
（ 1） 画出 G的关于完全图的补图 G。
（ 2） 画出 [AKG-]的所有不同构的生成树 。
5.如图 9.2所示两个无向图,其中实线边所示生成子图为
G的一棵生成树 T。
（ 1） 指出 T的所有弦,及 T所对应的基本回路系统 。
（ 2） 指出 T的所有树枝,及 T所对应的基本割集系统 。
第 9章 树图 9.2
e
c
d
f
b
a
G
1
e
c
d
b
a
f
g
h
( a ) ( b )
i
G
2
第 9章 树
6.求图 9.3所示的 2个带权图的最小生成树,计算它们的权,并写出关于这棵生成树的基本割集系统和基本回路系统 。
7.证明：对于 n个顶点的数,其顶点度数之和为 2n-2。
8.对于 n≥2，设 d1,d2,…,dn是 n个正整数，且
,证明：存在顶点度数为 d1,d2,…，
dn的一棵树。 1
22n i
i
dn
第 9章 树
1
3
5 5
7
3
4
6
2 1
1
8
9
2
7 6
5 4
10
3
( a ) ( b )
图 9.3
第 9章 树
9.证明,n＞ 2的连通图 G至少有两个顶点,将它们删去后得到的图仍是连通图 。
10.设 T是 k+1阶无向树,k≥1。 G是无向简单图,已知 δ（ G） ≥k,证明 G中存在与 T同构的子图 。
11.在连通图中,对给定的一棵生成树,设 D={e1，
e2,…,ek}是一个基本割集,其中 e1是树枝,e2,e3,…，
ek是生成树的弦,则 e1包含在对应于 ei（ i=2,3,…,k）
的基本回路中,且 e1不包含在任何其它的基本回路中 。
第 9章 树
12.在连通图中,对给定的一棵生成树,设 C={e1，
e2,…,ek}是一条基本回路,其中 e1是弦,e2,e3,…,ek
是树枝,则 e1包含在对应于 ei（ i=2,3,…,k） 的基本割集中,且 e1不包含在任何其它的基本割集中 。
13.证明：在二元正则树中,边的总数等于 2（ t-1）,
其中 t是树叶的数目 。
14.证明：二元正则树有奇数个顶点 。
15.求出对应于图 9.4所给树 （ a） 和森林 （ b） 的二元位置树 。
第 9章 树图 9.4
( a ) ( b )
第 9章 树
16.画出公式 （ p∨ （ ﹁ p∧ q）） ∧
（（ ﹁ p→ q） ∧ ﹁ r） 的根树表示 。
17.给定权 1,4,9,16,25,36,49,64,81,100。
（ 1） 构造一棵最优二元树 。
（ 2） 构造一棵最优三元树 。
（ 3） 说明如何构造一棵最优 t元树 。
第 9章 树
18.通讯中 a,b,c,d,e,f,g,N出现的频率分别为
a,25 % b,20 % c,15 % d,15 %
e,10 % f,5 % g,5 %
N,5 %
通过画出相应的最优二元树,求传输它们的最佳前缀码,并计算传输 10000个按上述比例出现的字母需要多少个二进制数码 。
