离散数学树(1)

1、第16章 树离离 散散 数数 学学精选精选ppt2本章说明本章说明q树是图论中重要内容之一。树是图论中重要内容之一。q本章所谈本章所谈回路均指初级回路（圈）或简单回路回路均指初级回路（圈）或简单回路，不含复杂回路（有重复边出现的回路）。不含复杂回路（有重复边出现的回路）。精选精选ppt316.1 无向树及其性质无向树及其性质定义定义16.116.1无向树无向树连通无回路的无向图，简称树，用连通无回路的无向图，简称树，用T表示。表示。平凡树平凡树平凡图。平凡图。森林森林若无向图若无向图G至少有两个连通分支（每个都是树）。至少有两个连通分支（每个都是树）。树叶树叶无向图中悬挂顶点。无向图中悬挂顶点

2、。分支点分支点度数度数大于或等于大于或等于2 2的顶点。的顶点。举例举例如图为九个顶点的树。如图为九个顶点的树。精选精选ppt4定理定理16.116.1 设设G 是是n阶阶m条边的无向图，则下面各命题是等条边的无向图，则下面各命题是等价的：价的：（1 1）G是树。是树。（2 2）G中任意两个顶点之间存在唯一的路径。中任意两个顶点之间存在唯一的路径。（3 3）G中无回路且中无回路且mn 1 1。（4 4）G是连通的且是连通的且mn 1 1。（5 5）G是连通的且是连通的且G G中任何边均为桥。中任何边均为桥。（6 6）G中没有回路，但在任何两个不同的顶点之间加一条新边，中没有回路，但在任何两个不

3、同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。在所得图中得到唯一的一个含新边的圈。无向树的等价定义无向树的等价定义精选精选ppt5(1)(1)(2)(2)如果如果G是树是树，则，则G中任意两个顶点之间存在唯一的路径中任意两个顶点之间存在唯一的路径。存在性。存在性。 由由G的连通性及定理的连通性及定理14.514.5的推论（的推论（在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj( (vi vj) )存在通路，则存在通路，则vi到到vj 一定存在长度小于等于一定存在长度小于等于n-1-1的初级的初级通路通路( (路径路径) )）可知，）可知， u, ,vV，u与与v之间存在路径

4、。之间存在路径。唯一性唯一性（反证法）。（反证法）。 若路径不是唯一的，设若路径不是唯一的，设1 1与与2 2都是都是u到到v的路径，的路径，易知必存在由易知必存在由1 1和和2 2上的边构成的回路，上的边构成的回路，这与这与G中无回路矛盾。中无回路矛盾。精选精选ppt6(2)(2)(3)(3)如果如果G中任意两个顶点之间存在唯一的路径中任意两个顶点之间存在唯一的路径，则则G中无回路且中无回路且mn- -1 1。首先证明首先证明 G中无回路。中无回路。若若G中存在关联某顶点中存在关联某顶点v的环，的环，则则v到到v存在长为存在长为0 0和和1 1的两条路经的两条路经( (注意初级回路是路径的特

5、殊情况注意初级回路是路径的特殊情况) )，这与已知矛盾。这与已知矛盾。若若G中存在长度大于或等于中存在长度大于或等于2 2的圈，的圈，则圈上任何两个顶点之间都存在两条不同的路径，则圈上任何两个顶点之间都存在两条不同的路径，这也与已知矛盾。这也与已知矛盾。精选精选ppt7(2)(2)(3)(3)如果如果G中任意两个顶点之间存在唯一的路径中任意两个顶点之间存在唯一的路径，则则G中无回路且中无回路且mn- -1 1。其次证明其次证明 mn-1-1。（归纳法）（归纳法）n1 1时，时，G为平凡图，结论显然成立。为平凡图，结论显然成立。设设nk( (k1)1)时结论成立，时结论成立，当当n= =k+1+

6、1时，设时，设e( (u, ,v) )为为G中的一条边，中的一条边，由于由于G中无回路，所以中无回路，所以G- -e e为两个连通分支为两个连通分支G1 1、G2 2。设设ni、mi分别为分别为Gi中的顶点数和边数，则中的顶点数和边数，则nik ，i1,21,2，由归纳假设可知由归纳假设可知mini-1-1，于是于是mm1 1+ +m2 2+1+1n1 1-1+-1+n2 2-1+1-1+1n1 1+ +n2 2-1-1n-1-1。精选精选ppt8只需证明只需证明G是连通的。（采用反证法）是连通的。（采用反证法）假设假设G是不连通的，由是不连通的，由s( (s2) )个连通分支个连通分支G1,

7、G2,Gs组成组成，并且并且Gi中均无回路，因而中均无回路，因而Gi全为树全为树。由由(1)(1)( (2)2)( (3)3)可知可知，mini- -1。于是于是，由于由于s2，与与mn- -1矛盾矛盾。111(1)sssiiiiiimmnnsns(3)(3)(4)(4)如果如果G中无回路且中无回路且mn-1-1，则则G是连通的且是连通的且mn -1-1。精选精选ppt9如果如果G是连通的且是连通的且mn 1，则则G是连通的且是连通的且G中任何边均为桥中任何边均为桥。只需证明只需证明G中每条边均为桥。中每条边均为桥。 eE，均有均有| |E( (G- -e)|)|n- -1- -1n- -2，

8、由习题十四题由习题十四题49（若若G是是n阶阶m条边的无向连通图，则条边的无向连通图，则mn- -1）可可知，知，G- -e已不是连通图，已不是连通图，所以，所以，e为桥。为桥。 (4)(4)(5)(5)精选精选ppt10如果如果G是连通的且是连通的且G中任何边均为桥中任何边均为桥，则，则G中没有回路，但在任中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈一个含新边的圈。因为因为G中每条边均为桥，删掉任何边，将使中每条边均为桥，删掉任何边，将使G变成不连通图，变成不连通图，所以，所以，G中没有回路，也即中没

9、有回路，也即G中无圈。中无圈。又由于又由于G连通，所以连通，所以G为树，由为树，由(1) (2)可知，可知， u,vV，且且uv，则则u与与v之间存在唯一的路径之间存在唯一的路径，则则( (u,v) )（( (u,v) )为加的新边为加的新边）为为G中的圈，中的圈，显然圈是唯一的。显然圈是唯一的。(5)(5)(6)(6)精选精选ppt11如果如果G中没有回路，但在任何两个不同的顶点之间加一条新边，中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈在所得图中得到唯一的一个含新边的圈，则，则G是树是树。只需证明只需证明G是连通的。是连通的。 u,vV，且且uv，则

10、新边则新边( (u,v) )G产生唯一的圈产生唯一的圈C，显然有显然有C -(-(u,v) )为为G中中u到到v的通路，故的通路，故uv，由由u,v的任意性可知，的任意性可知，G是连通的。是连通的。(6)(6)(1)(1)精选精选ppt12定理定理16.216.2 设设T是是n阶非平凡的无向树，则阶非平凡的无向树，则T中至少有两片树叶。中至少有两片树叶。设设T有有x片树叶，由握手定理及定理片树叶，由握手定理及定理16.116.1可知，可知，证明证明2(1)( )2()ind vxnx由上式解出由上式解出x2 2。无向树的性质无向树的性质精选精选ppt13例例16.116.1例例16.116.1

11、 画出画出6 6阶所有非同构的无向树。阶所有非同构的无向树。 解答解答 设设Ti是是6 6阶无向树。阶无向树。由定理由定理16.116.1可知，可知，Ti的边数的边数mi5 5，由握手定理可知，由握手定理可知，dTi( (vj) )1010，且且(Ti)1)1，( (Ti)5)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)(4)对应两棵非同构的树，对应两棵非同构的树，在一棵树中两个在一棵树中两个2 2度顶点相邻，度顶点

12、相邻，在另一棵树中不相邻，在另一棵树中不相邻，其他情况均能画出一棵非同构其他情况均能画出一棵非同构的树。的树。精选精选ppt14例例16.116.1q 人们常称只有一个分支点，且分支点的度数为人们常称只有一个分支点，且分支点的度数为n-1-1的的n( (n3)3)阶无向树为阶无向树为星形图星形图，称唯一的分支点为，称唯一的分支点为星心星心。 精选精选ppt15例例16.216.2例例16.216.2 7 7阶无向图有阶无向图有3 3片树叶和片树叶和1 1个个3 3度顶点，其余度顶点，其余3 3个顶点的度数个顶点的度数均无均无1 1和和3 3。试画出满足要求的所有非同构的无向树。试画出满足要求的

13、所有非同构的无向树。解答解答 设设Ti为满足要求的无向树，则边数为满足要求的无向树，则边数mi6 6，于是于是d( (vj) )1212e+3+3+d( (v4 4)+)+d( (v5 5)+)+d( (v6 6) )。由于由于d( (vj)1d()1d(vj)3)3，而且而且d( (vj)1)1且且d( (vj)6)6，j4,5,64,5,6，可知可知d(d(vj) )2 2，j4,5,64,5,6。于是于是Ti 的度数列为的度数列为1 1，1 1，1 1，2 2，2 2，2 2，3 3由度数列可知，由度数列可知，Ti中有一个中有一个3 3度顶点度顶点vi，vi的邻域的邻域N( (vi) )

14、中有中有3 3个顶个顶点，这点，这3 3个顶点的度数列只能为以下三种情况之一：个顶点的度数列只能为以下三种情况之一：1,1,21,1,21,2,21,2,22,2,22,2,2设它们对应的树分别为设它们对应的树分别为T1 1，T2 2，T3 3。此度数列只能产生这三棵。此度数列只能产生这三棵非同构的非同构的7 7阶无向树。阶无向树。精选精选ppt16例例16.216.2精选精选ppt17例题例题例题例题 已知无向树已知无向树T中，有中，有1 1个个3 3度顶点，度顶点，2 2个个2 2度顶点，其余度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构顶点全是树叶，试求树叶数，并画出满足要

15、求的非同构的无向树。的无向树。 解答解答 设有设有x片树叶，于是结点总数为片树叶，于是结点总数为n1+2+1+2+x3+3+x 由握手定理和树的性质由握手定理和树的性质mn 1 1可知，可知，2 2m2(2(n 1)1)2 2(2+(2+x) ) 1 13+23+22+2+x解出解出x3 3，故故T有有3 3片树叶。片树叶。故故T的度数应为的度数应为1 1、1 1、1 1、2 2、2 2、3 3。精选精选ppt18例题例题 已知无向树已知无向树T有有5片树叶，片树叶，2度与度与3度顶点各度顶点各1个，其余顶个，其余顶点的度数均为点的度数均为4，求求T的阶数的阶数n，并画出满足要求的所有非同并画

16、出满足要求的所有非同构的无向树。构的无向树。解答解答设设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。例题例题精选精选ppt19例题例题精选精选ppt2016.2 16.2 生成树生成树 定义定义16.216.2 设设G为无向图，为无向图，（1 1）T为为G的的树树T是是G的子图并且是树。的子图并且是树。（2 2）T为为G的的生成树生成树T是是G的生成子图

17、并且是树。的生成子图并且是树。（3 3）e为为T的的树枝树枝设设T是是G的生成树，的生成树， eE( (G) )，若若eE( (T) )。（4 4）e为为T的的弦弦设设T是是G的生成树，的生成树， eE( (G) )，若若e e E( (T) )。（5 5）生成树）生成树T的的余树余树导出子图导出子图G E( (G)-)-E( (T) ) 。记作。记作T精选精选ppt21注意：注意： 不一定连通，也不一定不含回路。不一定连通，也不一定不含回路。T说明说明 精选精选ppt22定理定理16.316.3 无向图无向图G具有生成树当且仅当具有生成树当且仅当G连通。连通。证明证明必要性必要性，显然。，显

18、然。充分性充分性（破圈法）。（破圈法）。 若若G中无回路，中无回路，G为自己的生成树。为自己的生成树。 若若G中含圈，任取一圈，随意地删除圈上的一条边，中含圈，任取一圈，随意地删除圈上的一条边，若再有圈再删除圈上的一条边，直到最后无圈为止。若再有圈再删除圈上的一条边，直到最后无圈为止。易知所得图无圈易知所得图无圈( (当然无回路当然无回路) )、连通且为、连通且为G G的生成子图，的生成子图，所以为所以为G的生成树。的生成树。生成树的存在条件生成树的存在条件 精选精选ppt23最小生成树最小生成树定义定义16.516.5 设设T是无向连通带权图是无向连通带权图G 的一棵生成树，的一棵生成树，T

19、的各边权之和称为的各边权之和称为T的权的权，记作，记作W( (T) )。G的所有生成树中权最小的生成树称为的所有生成树中权最小的生成树称为G的的最小生成树最小生成树。求最小生成树的算法（避圈法求最小生成树的算法（避圈法( (Kruskal) )）(1)(1)设设n阶无向连通带权图阶无向连通带权图G 有有m条边。不妨设条边。不妨设G中没有中没有环（否则，可以将所有的环先删去），将环（否则，可以将所有的环先删去），将m条边条边按权从小到大按权从小到大排序：排序：e1 1, ,e2 2,em。(2)(2)取取e1 1在在T中。中。(3)(3)依次检查依次检查e2 2,em ，若若ej( (j2)2)

20、与已在与已在T中的边不构成回路，取中的边不构成回路，取ej也在也在T中，否则弃去中，否则弃去ej。(4)(4)算法停止时得到的算法停止时得到的T为为G的最小生成树为止。的最小生成树为止。精选精选ppt24例例16.316.3例例16.316.3 求下图所示两个图中的最小生成树。求下图所示两个图中的最小生成树。 W( (T1 1) )6 6 W( (T2 2) )1212 精选精选ppt25例题例题例如例如 求所示图的一棵最小生成树。求所示图的一棵最小生成树。解答解答最小生成树最小生成树 W(T)=38精选精选ppt2616.3 16.3 根树及其应用根树及其应用q 设设D是有向图，若是有向图，

21、若D的基图是无向树，则称的基图是无向树，则称D为有向树。为有向树。q 在所有的有向树中，根树最重要，所以我们只讨论根树。在所有的有向树中，根树最重要，所以我们只讨论根树。q 二叉树的应用二叉树的应用 精选精选ppt27根树的定义根树的定义定义定义16.616.6 T是是n( (n2) )阶有向树，阶有向树，(1) T为根树为根树 T中有一个顶点入度为中有一个顶点入度为0，其余顶点的入度均为，其余顶点的入度均为1(2) 树根树根入度为入度为0的顶点的顶点(3) 树叶树叶入度为入度为1，出度为，出度为0的顶点的顶点(4) 内点内点入度为入度为1，出度不为，出度不为0的顶点的顶点(5) 分支点分支点

22、树根与内点的总称树根与内点的总称(6) 顶点顶点v的层数的层数从树根到从树根到v的通路长度的通路长度(7) 树高树高T中层数最大顶点的层数中层数最大顶点的层数(8) 根树根树平凡树平凡树精选精选ppt28根树的画法根树的画法树根放上方，省去所有有向边上的箭头。树根放上方，省去所有有向边上的箭头。树叶树叶88片片内点内点 6 6个个分支点分支点 7 7个个高度高度 5 5精选精选ppt29家族树家族树常将根树看成家族树，家族中成员之间的关系如下定义。常将根树看成家族树，家族中成员之间的关系如下定义。 定义定义16.7 16.7 设设T为一棵非平凡的根树，为一棵非平凡的根树， vi、vjV(T)，

23、若若vi可达可达vj，则称则称vi为为vj的的祖先祖先，vj为为vi的的后代后代。若若vi邻接到邻接到vj（即即E(T)），），则称则称vi为为vj的的父亲父亲，而，而vj为为vi的的儿子儿子。若若vj、vk的父亲相同，则称的父亲相同，则称vj与与vk是是兄弟兄弟。定义定义16.8 设设v为根树为根树T中任意一顶点，称中任意一顶点，称v及其后代的导出子图为及其后代的导出子图为以以v为根的为根的根子树根子树。精选精选ppt30根树的分类根树的分类(1)(1)设设T为根树，若将为根树，若将T中层数相同的顶点都标定次序，中层数相同的顶点都标定次序，则称则称T为为有序树有序树。 (2)(2)分类：分类

24、：根据根树根据根树T中每个分支点儿子数以及是否有序中每个分支点儿子数以及是否有序q r叉树叉树每个分支点至多有每个分支点至多有r个儿子个儿子r叉有序树叉有序树r叉树是有序的叉树是有序的q r叉正则树叉正则树每个分支点恰有每个分支点恰有r个儿子个儿子r叉正则有序树叉正则有序树r叉正则树是有序的叉正则树是有序的q r叉完全正则树叉完全正则树树叶层数均为树高的树叶层数均为树高的r叉正则树叉正则树r叉完全正则有序树叉完全正则有序树r叉完全正则树是有序的叉完全正则树是有序的精选精选ppt31最优二叉树最优二叉树定义定义16.916.9 设设2叉树叉树T有有t片树叶片树叶v1, v2, , vt，权分别为

25、权分别为w1, w2, , wt，称称 为为T的权，其中的权，其中l(vi)是是vi的层数，的层数，在所有有在所有有t片树叶、带权片树叶、带权w1, w2, , wt的的2叉树中，叉树中，权最小权最小的的2叉树称为叉树称为最优最优2叉树叉树。1( )( )tiiiW twl v精选精选ppt32举例举例下图所示的三棵下图所示的三棵2叉树叉树T1,T2,T3都是带权为都是带权为2、2、3、3、5的的2叉树叉树。 W(T1)=22+22+33+53+32=38W(T2)=34+54+33+22+21=47W(T3)=33+33+52+22+22=36 精选精选ppt33求最优树的算法求最优树的算法

26、( (Huffman算法算法) )给定实数给定实数w1, w2, , wt，且且w1w2 wt。连接权为连接权为w1, w2的两片树叶，得一个分支点，其权为的两片树叶，得一个分支点，其权为w1+w2。 在在w1+w2, w3, , wt中选出两个最小的权，连接它们对应的顶中选出两个最小的权，连接它们对应的顶点（不一定是树叶），得新分支点及所带的权。点（不一定是树叶），得新分支点及所带的权。 重复重复 ，直到形成，直到形成t 1个分支点、个分支点、t片树叶为止。片树叶为止。精选精选ppt34算法举例算法举例例如：例如：求带权为求带权为1 1、1 1、2 2、3 3、4 4、5 5的最优树。的最优

27、树。解答解答W(T)=38 精选精选ppt35(1)(1)最佳前最码的定义最佳前最码的定义定义定义16.1016.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为为二元前缀码二元前缀码。

28、(2)(2)如何产生二元前缀码？如何产生二元前缀码？定理定理16.6 由一棵给定的由一棵给定的2叉正则树，可以产生唯一的一个二元前缀叉正则树，可以产生唯一的一个二元前缀码。码。 最佳前缀码最佳前缀码精选精选ppt36方法：方法：将每个分支点引出的两条边分别标上将每个分支点引出的两条边分别标上0和和1。结果：结果： 图所示树产生的前缀码为图所示树产生的前缀码为00, 10, 11, 011, 0100, 0101。 精选精选ppt37用用Huffman算法产生最佳前缀码算法产生最佳前缀码例例16.616.6 在通信中，八进制数字出现的频率如下：在通信中，八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6： 5% 7： 5%求传输它们的最佳前缀码？求传输它们的最佳前缀码？求传输求传输10n（n2）个按上述比例出现的八进制数字需要多个按上述比例出现的八进制数字需要多少个二进制数字？少个二进制数字？若用等长的（长为若用等长的（长为3）的码字传输需要多少个二进制数字？）的码字传输需要多少个二进制数字？精选精选ppt38解答解答 以以100乘各频率为权，并按小到大排列，得乘各频率为权，并按小到大排列，得w1=5, w2=5, w3=10, w4=10, w