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