离散数学课件资料

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第九章,树,9.1,无向树及生成树,9.2,根树及其应用,树：,连通而,不含回路,的无向图称为,无向树,，,简称树,。,常记做,T,。,树叶：,树中度数为,1,的结点。,分支点：,树中度数大于,1,的结点。,森林：,连通分支数大于等于2,且每个连通分支都是树的无向图。,9.1 无向树及生成图,平凡树：,平凡图。,本章所指回路为简单回路或初级回路,一、无向树,(1),G,连通且不含回路；,(2),G,中无回路，且,m,=,n,-1,，其中,m,为边，,n,为结点数；,(3),G,是连通的，且,m,=,n,-1,;,(4),G,中无回路，但在,G,中任意不相邻两结点之间增加一条边，就得到唯一的一条初级回路；,(5),G,是连通的且,G,中每条边都是桥；,(6),G,中每一对结点之间有唯一的一条基本通路。,树的等价,定义,任意非平凡树T (,n,m,)至少有两片树叶。,定理,设,T,有,k,片树叶，于是2,m,k+,2 (,n,-,k,)，,则2 (,n,-1),2,n,-,k,，则,k,2,例：,画出6阶所有非同构的无向树。,(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,解：,设,T,是,6,阶无向树，,T,的边数,m,5，,由握手定理可知，,d,(,v,)10，且,(T),1，,(T),5。故T的度数列必为以下情况之一：,一、无向树,二、生成树,生成树：,若连通图,G,的某个生成子图是一棵树，,则称该树为,G,的生成树，记做,T,G,。,树枝：,生成树,T,G,的边。,弦：,G,中不在,T,G,中的边。,生成树的余树,(补),：,T,G,的所有弦的集合的导出子图。余树不一定是树,也不一定连通。,二、生成树,d,b,a,e,c,d,b,a,e,c,b,a,e,c,图,G,生成树,T,G,生成树,T,G,的补,无向连通图如果本身不是树，它的生成树是不唯一的，但所有连通图都具有生成树。,推论1:,G,为,n,阶,m,条边的无向连通图，则,m,n,1。,(要把,n,个顶点联系起来至少需要,n,-1条边),推论2,:,设,G,是,n,阶,m,条边的无向连通图，,T,为,G,的生成树，则,T,的余树中含有,m,-,n,+1条边（即,T,有,m,-,n,+1条弦）。,定理,任何连通图,G,至少存在一棵生成树。,二、生成树,基本回路,:,设,T,是,n,阶,m,条边的无向连通图,G,的一棵生成树，设,e,1,e,2, ,e,m,n,+,1,为,T,的弦。设,C,r,为,T,添加弦,e,r,产生的,G,的回路, 该回路只含生成树,T,的一条,弦,e,r,，其余边均为树枝，称,C,r,为对应,T,的弦,e,r,的,基本回路,，,r,1, 2, ,m,n,+1。,a,e,d,b,f,c,二、生成树,基本回路系统：,C,1,C,2, ,C,m,n,+1,为,G,对应,T,的,基本回路系统。,一个连通图对应不同的生成树的基本回路及,基本回路,系统可能不同，但是基本回路的个数相等，等于,m,n,+1。,三、最小生成树,最小生成树：,设,G =,是无向,连通带权图，,T,是,G,的一棵生成树，,T,各边带权之和称为,T,的权，记为,W,(,T,),。,G,的所有生成树中带权最小的生成树称为,G,的最小生成树。,Kruskal,算法(避圈法),：设,n,阶,无向,连通带权图,G,有,m,条边 ，它们带的权分别为 ，设 。,（1）取,e,1,在T中（,e,i,非环，若是环，则放弃,）,（2）若,e,2,不与,e,1,构成回路，取,e,2,在T中，否则放弃,e,2,，考查,e,3,，继续这一过程，直到形成生成树T为止。,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,Kruskal,算法,:,7,12,18,19,9.2 根树及其应用,其中：入度为0的顶点称为树根，,有向树,：,一个有向图，若略去所有有向边的方向后得到的无向图是一棵树，则称该有向图为有向树。,根树：,非平凡的有向树，若恰有一个结点的入度为0，,其余所有顶点的入度均为1，则称此有向树为根树。,入度为1，出度为0的顶点称为树叶，,入度为1出度大于0的顶点称为内点，,内点和树根统称为分支点。,一、有向树,层数,:,从树根到任意顶点,v,的通路长度，称为,v,的层数，记为,l,(,v,).,树高,:,层数最大的顶点的层数，记为,h,(T)。,（本书树根为第0层。）,v,0,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,v,10,v,11,v,12,根树,可看成是,家族树,：,(1) 若从,a,到,b,可达，则称,a,是,b,的祖先，,b,是,a,的后代；,(2) 若是根树中的有向边，则称,a,是,b,的父亲，,b,是,a,的儿子；,(3) 若,b,、,c,同为,a,的儿子，则称,b,、,c,为兄弟。,一、有向树,根子树,：,根树,T,中，任一不为树根的顶点,v,及其所有后代导出的子图, 称为,T,的以,v,为根的子树。,二、有序树,r,元树,：每个分支点至多有,r,个儿子；,r,元有序树,：,r,元树是有序的；,r,元正则树,：每个分支点恰有,r,个儿子；,r,元正则有序树,：,r,元正则树是有序的；,r,元完全正则树,：树叶层数均为树高的,r,元正则树；,r,元完全正则有序树,：,r,元完全正则树是有序的。,有序树,：,每层上的顶点都,规定了,次序的根树。,分类,：,根据根树,T,中每个分支点儿子数以及是否有序：,二、有序树,将有序,树转换为二元树：,(1) 从树根开始，保留每个父亲顶点和最左边儿子,的连线，撤消与其他儿子的连线；,(2) 兄弟间用从左至右的水平有向边连接。,(3) 以位于给定顶点下面的顶点作为,左儿子,，以给定,顶点的水平右邻顶点（,兄弟）,作为,右儿子,。,将森林,转换为二元树：,将每棵树表示为二元树，除第一棵二元树外，将余下每棵二元树作为前一棵二元树的根的右子树。,三、最优树,带权二元树：,设有一棵二元树有,t,片树叶，分别带权为,w,1,、,w,2,、 、,w,t,，则称之为带权二元树；,权：,称 为该,带权二元树的权,，其中，,权为,w,i,的树叶的层数为,L,(,w,i,)。,最优二元树：,所有带权,w,1,、,w,2,、 、,w,t,的二元树中，,带权,W,(,T,),最小的二元树。,例：下图所示的三棵二叉树,T,1,T,2,T,3,都是带权为,2、2、3、3、5,的,二,叉树。,W,(,T,1,)=22+22+33+53+32=38,W,(,T,2,)=34+54+33+22+21=47,W,(,T,3,)=33+33+52+22+22=36,三、最优树,求最优树的算法(,Huffman,算法),给定实数,w,1,w,2,w,t,，设,w,1,w,2,w,t,。, 连接权为,w,1,w,2,的两片树叶，得一个分支点，其权为,w,1,+,w,2,。,三、最优树, 重复，直到形成,t,-,1个分支点、,t,片树叶为止。, 在,w,1,+,w,2,w,3, ,w,t,中选出两个最小的权，连接它们对应的顶点（不一定是树叶），得新分支点及所带的权。,9,例如: 已知权值,W= 5, 6, 2, 9, 7 ,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,6,7,13,9,5,2,7,9,5,2,7,16,6,7,13,29,0,0,0,0,1,1,1,1,00,01,10,110,111,例：求带权为,1、1、2、3、4、5,的最优树。,三、最优树,W,(,T,),=38,最优树不是唯一的，但是由,Huffman,算法得到的树一定是最优树。,前缀,:设,=,1,2,n,-1,n,是长度为,n,的符号串，称,其子串,1,1,2,1,2,n,-1,分别为,的长,度为,1,2, ,n,-1,的,前缀,。,四、最佳前缀码,二元前缀码:,若,i,(i=1,2,m,),中只出现0与1两个符号，,则称,B,为,二元前缀码,。,前缀码:,设,B,=,1,2, ,m,为一个符号串集合，若对,于任意的,i,j,B,，,i,j,，,i,j,互不为前缀，则,称,B,为,前缀码,。,四、最佳前缀码,(2)如何产生二元前缀码？,定理:,任何一棵二元正则树对应一个二元前缀码。,定理:,任何一个二元前缀码对应一颗二元正则树。,0，10，110，1111,1，11，101，0010,1，01，001，000,00，11，011，0100，0101,例：判断下列符号串集合是否是前缀码。,方法：,用Huffman算法产生最佳前缀码。,例、,在通信中，八进制数字出现的频率如下：,0：25%；1：20%；2：15%；3：10%,4：10%；5：10%；6：5%； 7：5%,求传输它们的最佳前缀码？,求传输10,n,（,n,2）个按上述比例出现的八进制数字需要多少个二进制数字？,若用等长码(长为,3,)传输需要多少个二进制数字？,四、最佳前缀码,最佳前缀码：,当要传输按着一定比例出现的符号串 时，需要寻找传输它们最省二进制数字 的前缀码，即最佳前缀码。,例：以100乘各频率为权，并按小到大排列，得,w,1,=5,w,2,=5,w,3,=10,w,4,=10,w,5,=10,w,6,=15,w,7,=20,w,8,=25,。产生的最优树如下。,0 01 (25%),1 11,(20%),2 001,(15%),3 100,(10%),4 101,(10%),50001,(10%),6 00000,(5%),7 00001,(5%),传100个按比例出现的八进制数字所需二进制数字个数,W,(,T,)=285，所以传,10,n,(,n,2),个所用二进制数字应为,2.85,10,n,。,用等长码（长为3）应该用,3,10,n,个数字,因此用最佳前缀码可节省传递数字。,（1）,由于在每一步选择两个最小的权的选法不唯一。,（2）,因为两个权对应的顶点所放左右位置不同。,（3）,画出的最优树可能不同，最佳前缀码并不唯一，但有一点是共同的，就是它们的权相等，即它们都应该是最优树。,四、最佳前缀码,遍历,：,对一棵根树的每个顶点访问且仅访问一次称为,遍历,一棵树,。,中序遍历法：,b,a,(,f,d,g,),c,e,五、树的遍历,前序遍历法：,a,b,(,c,(,d,f,g,),e,),后序遍历法：,b,(,f,g,d,),e,c,),a,对2元有序正则树的遍历方式：, 先序遍历法：访问次序为：树根、左子树、右子树, 后序遍历法：访问次序为：左子树、右子树、树根, 中序遍历法：访问次序为：左子树、树根、右子树,用,2,元有序正则树存放算式：,最高层次的运算符放在树根上。,依次将运算符放在根子树的根上。,参加运算的数放在树叶上，规定：被除数、被减数放在左子树树叶上。,五、树的遍历,例：,用二叉有序正则树表示算式：,(,b,+(,c,+,d,),a,),(,e,f,),(,g,+,h,),(,i,j,),五、树的遍历,波兰符号法:,按前序遍历法访问存放算式的二元有序,正则树，其结果不加括号，规定每个运算符号与其,后面紧邻两个数进行运算。,前序遍历法的访问结果为:,b,+,c,d,a,e,f,+,g,h,i,j,逆波兰符号法:,按后序行遍法访问，规定每个运算符与,前面紧邻两数运算。,后序行遍法的访问结果为:,b,c,d,+ +,a,e,f,g,h,+,i,j,小节结束,