离散数学 第九章：树.ppt

9.1 9.1 无向树及生成树无向树及生成树树：连通连通而不含回路不含回路的无向无向图称为无向树，简称树，记作 T。森林：连通分支数大于等于2，且每个连通分支均是树的非连通无向图。平凡树：平凡图为平凡树。一、树的概念森林树叶树叶:树中度数为1的顶点分支点分支点:树中度数2的顶点树的性质：树的性质：(1)G连通而不含回路；(2)每对顶点之间具有唯一一条初级通路唯一一条初级通路(3)n=m+1(4)若在G中任意两个不相邻的顶点之间增加一条边，就形成唯一一条初级回路唯一一条初级回路。(5)连通且每条边都是桥每条边都是桥(6)连通但删除任何一条边后就不连通设设G=是是n阶阶m条边的无向树，条边的无向树，则下面各命题是等价的：则下面各命题是等价的：性质(7):任一棵非平凡树 T=，至少有两至少有两片叶。片叶。证明证明：设设T有有x片树叶，由握手定理及定理片树叶，由握手定理及定理9.1知，知，由上式解出由上式解出x 2.生成树生成树：若图G为无向连通图.T为G的生成子图，且T为树，称T为G的生成树生成树。三、生成树及其构造方法三、生成树及其构造方法树枝与弦：树枝与弦：G在T中的边称为T的树枝树枝，G不 在T中的边称为T的弦弦。余树：余树：T的弦的集合的导出子图称为T的余树余树。生成树生成树余树余树生生成成树树余树余树例子无向连通图的生成树不一定唯一生成树的余树不一定是树带权图的最小生成树：带权图的最小生成树：设G=是带权的连通简单图，具有权最小权最小的生成树称为最小生成树。T是是G的一棵生成树的一棵生成树，T中所有枝的权之和所有枝的权之和称为T的权权，记作：W(T)。四、最小生成树四、最小生成树方法：避圈法方法：避圈法在不产生回路的基础上依次画出权值最小的边，直至画出n-1条边为止v15656541v2v4v5v323例9.1.1：5v1541v2v4v5v323W(T)=1+2+3+4+5=15651v2v4v5v323例9.1.2：v1551v2v4v5v323v1565551v2v4v5v32355oror551v2v4v5v323W(T)=1+2+3+5+5=16！最小生成树不一定唯一！最小生成树不一定唯一定义：定义：设设T是是n阶阶m条边的无向连通图条边的无向连通图G的一棵的一棵生成树，设生成树，设e1,e2,e m n+1为为T的的弦弦.设设Cr为为T添加弦添加弦er 产生的产生的G中惟一中惟一的圈的圈(由由er 和和树枝组成树枝组成),称称Cr为对应弦为对应弦er 的的基本回路基本回路r=1,2,m n+1.称称C1,C2,Cm n+1为对为对应应T的的基本回路系统基本回路系统.五：基本回路与基本回路系统五：基本回路与基本回路系统例9.1.3：Ca=aefCb=bdeCc=cdf基本回路系统为：基本回路系统为：Ca,Cb,Cc定义：定义：设设T是是n阶连通图阶连通图G的一棵生成树的一棵生成树,e1,e2,e n 1为为T的树枝，的树枝，Si是是G的的只含树只含树枝枝ei,其他边都是弦其他边都是弦的割集的割集,称称Si为对为对应生成树应生成树T由树枝由树枝ei 生成的生成的基本割集基本割集。i=1,2,n 1.称称S1,S2,Sn 1为对应为对应T的的基本割集系统基本割集系统.六：基本割集与基本割集系统六：基本割集与基本割集系统例9.1.4：Sa=a,f,gSb=b,g,hSd=d,h,iSc=c,f,hSe=e,f,i基本割集系统为：基本割集系统为：Sa,Sb,Sc,Sd,Se课后例题：课后例题：9.5，9.6，9.7，9.8课后作业：课后作业：9.1，9.3，9.4，9.5，9.6，9.7，9.89.2 9.2 根树及其应用根树及其应用一、树的概念有向树有向树:基图为无向树的有向图基图为无向树的有向图根树根树:有一个顶点入度为有一个顶点入度为0,其余的入度均为其余的入度均为1的的 非平凡的有向树非平凡的有向树树根树根:有向树中入度为有向树中入度为0的顶点的顶点树叶树叶:有向树中入度为有向树中入度为1,出度为出度为0的顶点的顶点内点内点:有向树中入度为有向树中入度为1,出度大于出度大于0的顶点的顶点分支点分支点:树根与内点的总称树根与内点的总称(出度大于等于出度大于等于1）顶点顶点v的层数的层数:从树根到从树根到v的通路长度，记作的通路长度，记作l(v)树高树高:有向树中顶点的最大层数，记作有向树中顶点的最大层数，记作h(T)根树的画法根树的画法:树根放上方树根放上方,省去所有有向边上的箭头省去所有有向边上的箭头如右图所示如右图所示 a是树根是树根 b,e,f,h,i是树叶是树叶 c,d,g是内点是内点 a,c,d,g是分支点是分支点 a为为0层层;1层有层有b,c;2层有层有d,e,f;3层有层有g,h;4层有层有i.树高为树高为4定义定义 把根树看作一棵把根树看作一棵家族树家族树:(1)若若顶顶点点 a 邻邻接接到到顶顶点点 b,则则称称 b 是是 a 的的儿儿子子,a 是是 b 的的父亲父亲;(2)若若b和和c为为同同一一个个顶顶点点的的儿儿子子,则则称称b和和c是是兄兄弟弟;(3)若若a b且且a可可达达b,则则称称a是是b的的祖祖先先,b是是a的的后代后代.(4)设设v为根树的一个顶点且不是树根为根树的一个顶点且不是树根,称称v及其及其所有后代的导出子图为以所有后代的导出子图为以v为根的为根的根子树根子树.有序树有序树:每一层的结点均有序每一层的结点均有序r元树元树:根树的每个分支点根树的每个分支点至多至多有有r个儿子个儿子r元正则树元正则树:根树的每个分支点根树的每个分支点恰有恰有r个儿子个儿子r元完全正则树元完全正则树:所有树叶层数相同都等于树高的所有树叶层数相同都等于树高的r元元 正则树正则树r元有序树元有序树:有序的有序的r元树元树r元正则有序树元正则有序树:有序的有序的r元正则树元正则树r元完全正则有序树元完全正则有序树:有序的有序的r元完全正则树元完全正则树定义定义 设设2元树元树T有有t片树叶片树叶v1,v2,vt,树叶的权分别树叶的权分别 为为w1,w2,wt,称称 为为T的权的权,记作记作 W(T),其中其中l(vi)是是vi的层数的层数.在所有有在所有有t片树叶片树叶,带权带权 w1,w2,wt 的的 2元树中元树中,权最小的权最小的2元树称为元树称为最优最优 2元树元树.给定实数给定实数w1,w2,wt,作作t片树叶片树叶,分别以分别以w1,w2,wt为权为权.在在所所有有入入度度为为0的的顶顶点点(不不一一定定是是树树叶叶)中中选选出出两两个个权权最最小小的的顶顶点点,添添加加一一个个新新分分支支点点,以以这这2个个顶顶点点为为儿子儿子,其权等于这其权等于这2个儿子的权之和个儿子的权之和.重复重复,直到只有直到只有1个入度为个入度为0 的顶点为止的顶点为止.W(T)等于所有分支点的权之和等于所有分支点的权之和Huffman算法算法例例 求带权为求带权为1,1,2,3,4,5的最优树的最优树.解题过程由下图给出，解题过程由下图给出，W(T)=38 例9.2.1：设设 =1 2 n-1 n是长度为是长度为n的符号串的符号串 的的前缀前缀:1 2 k,k=1,2,n-1 前前缀缀码码:1,2,m,其其中中 1,2,m为为非非空空字字符符串串,且任何两个互不为前缀且任何两个互不为前缀2元前缀码元前缀码:只出现两个符号只出现两个符号(如如0与与1)的前缀码的前缀码如如 0,10,110,1111,10,01,001,110是是2元前缀码元前缀码 0,10,010,1010 不是不是2元前缀码元前缀码一棵一棵2元树产生一个二元前缀码元树产生一个二元前缀码:对每个分支点对每个分支点,若关联若关联2条边条边,则给左边标则给左边标0,右边标右边标1;若只关联若只关联1条边条边,则可以给它标则可以给它标0(看作左边看作左边),也可以也可以标标1(看作右边看作右边).将从树根到每一片树叶的通路上标将从树根到每一片树叶的通路上标的数字组成的字符串的数字组成的字符串记在树叶处记在树叶处,所得的字符所得的字符串构成一个前缀码串构成一个前缀码.如右图所示：如右图所示：最优最优2进制编码：使信息传进制编码：使信息传递的递的2进制数最短进制数最短例例 在通信中，设八进制数字出现的频率如下：在通信中，设八进制数字出现的频率如下：0：25%1：20%2：15%3：10%4：10%5：10%6：5%7：5%采用采用2元前缀码元前缀码,求传输数字最少的求传输数字最少的2元前缀码元前缀码(称作称作最佳前最佳前缀码缀码),并求传输并求传输10n(n 2)个按上述比例出现的八进制数字需个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的要多少个二进制数字？若用等长的(长为长为3)的码字传输需要的码字传输需要多少个二进制数字多少个二进制数字?解解 用用Huffman算法求以频率算法求以频率(乘以乘以100)为权的最优为权的最优2元树元树.这这里里 w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.最优最优2元树如图所示元树如图所示.例9.2.2：编码编码:0-01 1-11 2-001 3-100 4-101 5-0001 6-00000 7-00001传传100个按比例出现的八进制数字所需二进制数字的个数个按比例出现的八进制数字所需二进制数字的个数为为 W(T)=285.传传10n(n 2)个所用二进制数字的个数为个所用二进制数字的个数为2.85 10n,而用等而用等长长码码(长为长为3)需要用需要用 3 10n个数字个数字.课后习题：课后习题：9.9，9.13行遍行遍(周游周游)根树根树T:对对T 的每个顶点访问且仅访问一次的每个顶点访问且仅访问一次.行遍行遍2元有序正则树的方式：元有序正则树的方式：中序行遍法中序行遍法:左子树、左子树、根根、右子树、右子树 前序行遍法前序行遍法:根根、左子树、右子树、左子树、右子树 后序行遍法后序行遍法:左子树、右子树、左子树、右子树、根根 例如例如,对图所示根树按中序、前序、对图所示根树按中序、前序、后序行遍法访问结果分别为：后序行遍法访问结果分别为：b a(f d g)c e a b(c(d f g)e)b(f g d)e c)a带下划线的是带下划线的是(子子)树根树根,一对括号内是一棵子树一对括号内是一棵子树 用用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 课后作业：课后作业：9.11，9.141.掌握树的概念及其各种等价定义；掌握树的概念及其各种等价定义；2.熟熟悉悉生生成成树树与与回回路路和和割割集集的的关关系系，掌掌握握最最小生成树的构造方法；小生成树的构造方法；3.熟熟练练掌掌握握根根树树的的性性质质和和最最优优二二元元树树的的生生成成方法和应用方法和应用;4.了解平面图的概念及其性质。了解平面图的概念及其性质。作业六作业六课后习题：课后习题：课后习题：课后习题：9.1-9.9，9.11，9.13