离散数学——树.ppt

《离散数学——树.ppt》由会员分享，可在线阅读，更多相关《离散数学——树.ppt（41页珍藏版）》请在课桌文档上搜索。

1、第16章 树,离 散 数 学,本章说明,树是图论中重要内容之一。本章所谈回路均指初级回路（圈）或简单回路，不含复杂回路（有重复边出现的回路）。,16.1 无向树及其性质,定义16.1无向树连通无回路的无向图，简称树，用T表示。平凡树平凡图。森林若无向图G至少有两个连通分支（每个都是树）。树叶无向图中悬挂顶点。分支点度数大于或等于2的顶点。举例如图为九个顶点的树。,定理16.1 设G是n阶m条边的无向图，则下面各命题是等价的：（1）G是树。（2）G中任意两个顶点之间存在唯一的路径。（3）G中无回路且mn1。（4）G是连通的且mn1。（5）G是连通的且G中任何边均为桥。（6）G中没有回路，但在任何

2、两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。,无向树的等价定义,(1)(2),如果G是树，则G中任意两个顶点之间存在唯一的路径。,存在性。由G的连通性及定理14.5的推论（在n阶图G中，若从顶点vi到vj(vivj)存在通路，则vi到vj 一定存在长度小于等于n-1的初级通路(路径)）可知，u,vV，u与v之间存在路径。唯一性（反证法）。若路径不是唯一的，设1与2都是u到v的路径，易知必存在由1和2上的边构成的回路，这与G中无回路矛盾。,(2)(3),如果G中任意两个顶点之间存在唯一的路径，则G中无回路且mn-1。,首先证明 G中无回路。若G中存在关联某顶点v的环，则v到

3、v存在长为0和1的两条路经(注意初级回路是路径的特殊情况)，这与已知矛盾。若G中存在长度大于或等于2的圈，则圈上任何两个顶点之间都存在两条不同的路径，这也与已知矛盾。,(2)(3),如果G中任意两个顶点之间存在唯一的路径，则G中无回路且mn-1。,其次证明 mn-1。（归纳法）n1时，G为平凡图，结论显然成立。设nk(k1)时结论成立，当n=k+1时，设e(u,v)为G中的一条边，由于G中无回路，所以G-e为两个连通分支G1、G2。设ni、mi分别为Gi中的顶点数和边数，则nik，i1,2，由归纳假设可知mini-1，于是mm1+m2+1n1-1+n2-1+1n1+n2-1n-1。,只需证明G

4、是连通的。（采用反证法）假设G是不连通的，由s(s2)个连通分支G1,G2,Gs组成，并且Gi中均无回路，因而Gi全为树。由(1)(2)(3)可知，mini-1。于是，,由于s2，与mn-1矛盾。,(3)(4),如果G中无回路且mn-1，则G是连通的且mn-1。,如果G是连通的且mn1，则G是连通的且G中任何边均为桥。,只需证明G中每条边均为桥。eE，均有|E(G-e)|n-1-1n-2，由习题十四题49（若G是n阶m条边的无向连通图，则mn-1）可知，G-e已不是连通图，所以，e为桥。,(4)(5),如果G是连通的且G中任何边均为桥，则G中没有回路，但在任何两个不同的顶点之间加一条新边，在所

5、得图中得到唯一的一个含新边的圈。,因为G中每条边均为桥，删掉任何边，将使G变成不连通图，所以，G中没有回路，也即G中无圈。又由于G连通，所以G为树，由(1)(2)可知，u,vV，且uv，则u与v之间存在唯一的路径，则(u,v)（(u,v)为加的新边）为G中的圈，显然圈是唯一的。,(5)(6),如果G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈，则G是树。,只需证明G是连通的。u,vV，且uv，则新边(u,v)G产生唯一的圈C，显然有C-(u,v)为G中u到v的通路，故uv，由u,v的任意性可知，G是连通的。,(6)(1),定理16.2 设T是n阶非平凡的

6、无向树，则T中至少有两片树叶。,设T有x片树叶，由握手定理及定理16.1可知，,证明,由上式解出x2。,无向树的性质,例16.1,例16.1 画出6阶所有非同构的无向树。解答 设Ti是6阶无向树。由定理16.1可知，Ti的边数mi5，由握手定理可知，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,人们常

7、称只有一个分支点，且分支点的度数为n-1的n(n3)阶无向树为星形图，称唯一的分支点为星心。,例16.2,例16.2 7阶无向图有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3。试画出满足要求的所有非同构的无向树。解答 设Ti为满足要求的无向树，则边数mi6，于是d(vj)12e+3+d(v4)+d(v5)+d(v6)。由于d(vj)1d(vj)3，而且d(vj)1且d(vj)6，j4,5,6，可知d(vj)2，j4,5,6。于是Ti 的度数列为1，1，1，2，2，2，3由度数列可知，Ti中有一个3度顶点vi，vi的邻域N(vi)中有3个顶点，这3个顶点的度数列只能为以下三种情况之一：1

8、,1,21,2,22,2,2设它们对应的树分别为T1，T2，T3。此度数列只能产生这三棵非同构的7阶无向树。,例16.2,例题,例题 已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树。解答 设有x片树叶，于是结点总数为n1+2+x3+x 由握手定理和树的性质mn1可知，2m2(n1)2(2+x)13+22+x解出x3，故T有3片树叶。故T的度数应为1、1、1、2、2、3。,例题 已知无向树T有5片树叶，2度与3度顶点各1个，其余顶点的度数均为4，求T的阶数n，并画出满足要求的所有非同构的无向树。解答设T的阶数为n,则边数为n1，4度顶点

9、的个数为n7。由握手定理得 2m=2(n1)=51+21+31+4(n7)解出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的生成树，eE(G)，若eE(T)。（4）e为T的弦设T是G的生成树，eE(G)，若eE(T)。（5）生成树T的余树导出子图GE(G)-E(T)。记作,注意：不一定连通，也不一定不含回路。,说明,定理16.3 无向图G具有生成树当且仅当G连通。证明必要性，显然。充分性

10、（破圈法）。若G中无回路，G为自己的生成树。若G中含圈，任取一圈，随意地删除圈上的一条边，若再有圈再删除圈上的一条边，直到最后无圈为止。易知所得图无圈(当然无回路)、连通且为G的生成子图，所以为G的生成树。,生成树的存在条件,最小生成树,定义16.5 设T是无向连通带权图G的一棵生成树，T的各边权之和称为T的权，记作W(T)。G的所有生成树中权最小的生成树称为G的最小生成树。求最小生成树的算法（避圈法(Kruskal)）(1)设n阶无向连通带权图G有m条边。不妨设G中没有环（否则，可以将所有的环先删去），将m条边按权从小到大排序：e1,e2,em。(2)取e1在T中。(3)依次检查e2,em，

11、若ej(j2)与已在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(n2)阶有向树，(1)T为根树 T中有一个顶点入度为0，其余顶点的入度均为1(2)树根入度为0的顶点(3)树叶入度为1，出度为0的顶点(4

12、)内点入度为1，出度不为0的顶点(5)分支点树根与内点的总称(6)顶点v的层数从树根到v的通路长度(7)树高T中层数最大顶点的层数(8)根树平凡树,根树的画法,树根放上方，省去所有有向边上的箭头。,树叶8片内点 6个分支点 7个高度 5,家族树,常将根树看成家族树，家族中成员之间的关系如下定义。定义16.7 设T为一棵非平凡的根树，vi、vjV(T)，若vi可达vj，则称vi为vj的祖先，vj为vi的后代。若vi邻接到vj（即E(T)），则称vi为vj的父亲，而vj为vi的儿子。若vj、vk的父亲相同，则称vj与vk是兄弟。定义16.8 设v为根树T中任意一顶点，称v及其后代的导出子图为以v为

13、根的根子树。,根树的分类,(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叉树。,举例,下图所示的三棵2叉树T1,T2,

14、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,求最优树的算法(Huffman算法),给定实数w1,w2,wt，且w1w2 wt。连接权为w1,w2的两片树叶，得一个分支点，其权为w1+w2。在w1+w2,w3,wt中选出两个最小的权，连接它们对应的顶点（不一定是树叶），得新分支点及所带的权。重复，直到形成t1个分支点、t片树叶为止。,算法举例,例如：求带权为1、1、2、3、4、5的最优树。,解答,W(T)=38,(1)最佳前最码的定义定义16.10 设1,2

15、,n-1,n是长度为n的符号串，称其子串1,12,12n1 分别为该字符串的长度为1,2,n的前缀。设A=1,2,m为一个符号串集合，若对于任意的i,jA，ij，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：

16、15%3：10%4：10%5：10%6：5%7：5%求传输它们的最佳前缀码？求传输10n（n2）个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的（长为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 1004 1015 00016 000007 00001,传100个按比例出现的八进制数字所需二进制数字个数W(T)=285，所以传10n(n2)个所用二进制数字应为2.8510n。用等长码（长为3）应该用

17、310n个数字。,由于在每一步选择两个最小的权的选法不唯一。因为两个权对应的顶点所放左右位置不同。画出的最优树可能不同，最佳前缀码并不唯一，但有一点是共同的，就是它们的权应该相等，即它们都应该是最优树。,说明,3、波兰符号法与逆波兰符号法对一棵根树的每个顶点都访问且仅访问一次称为行遍或周游一棵树。对2叉有序正则树的周游方式：中序行遍法次序为：左子树、树根、右子树 前序行遍法次序为：树根、左子树、右子树 后序行遍法次序为：左子树、右子树、树根,中序行遍法：b a(f d g)c e前序行遍法：a b(c(d f g)e)后序行遍法：b(f g d)e c)a,例如：,用2叉有序正则树存放算式：最高层次的运算符放在树根上。依次将运算符放在根子树的根上。参加运算的数放在树叶上，规定：被除数、被减数放在左子树树叶上。,