离散数学屈婉玲第十章.ppt

1,第十章 树,主要内容无向树及其性质生成树根树及其应用,10.1 无向树及其性质,定义10.1 连通无回路的无向图称为无向树,简称树.每个连通分支都是树的无向图称为森林.平凡图称为平凡树.在无向树中,悬挂顶点称为树叶,度数大于或等于2的顶点称为分支点例,f,f,f,星形树,3,无向树的性质,定理10.1 设G=是n阶m条边的无向图，则下面各命题是等价的：(1)G 是树(2)G 中任意两个顶点之间存在惟一的路径.(3)G 中无回路且 m=n1.(4)G 是连通的且 m=n1.(5)G 是连通的且 G 中任何边均为桥.(6)G 中没有回路，但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.,4,(3)(4).只需证明G连通.用反证法.否则G有s(s2)个连通分支,它们都是树.于是,有mi=ni1,这与m=n1矛盾.,证明,(2)(3).若G中有回路，则回路上任意两点之间的路径不惟一.对n用归纳法证明m=n1.当n=1时成立.设nk时成立，证n=k+1时也成立：任取一条边e，Ge有且仅有两个连通分支G1,G2.nik，由归纳假设得mi=ni1,i=1,2.于是，m=m1+m2+1=n1+n22+1=n1.,证(1)(2).若路径不惟一,必有回路.,5,(4)(5).只需证明G 中每条边都是桥.下述命题显然成立:G 是 n 阶 m 条边的无向连通图，则 mn1.eE,Ge只有n2条边，由命题可知Ge不连通，故e为桥.,证明,(5)(6).由(5)易知G为树.由(1)(2)知，u,vV（uv）,u到v有惟一路径，加新边(u,v)得惟一的一个圈.,(6)(1).只需证明G连通，这是显然的.,解得 x 2.,定理10.2 设T是n阶非平凡的无向树，则T 中至少有两片树叶.,无向树的性质,证 设 T 有 x 片树叶，由握手定理及定理10.1可知，,例1 已知无向树T中有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树.,解 设有x片树叶，n=3+x.2m=2(n1)=2(2+x)=13+22+x解出x=3，故T有3片树叶.,7,例2 已知无向树T有5片树叶，2度与3度顶点各1个，其余顶点的度数均为4，求T的阶数n，并画出满足要求的所有非同构的无向树.,例题,解 设T的阶数为n,则边数为n1，4度顶点的个数为n7.由握手定理,2m=2(n1)=51+21+31+4(n7),解出n=8，4度顶点为1个.,8,10.2 生成树,定义10.2 如果无向图G的生成子图T是树，则称T是G的生成树.设T是G的生成树，G的在T中的边称为T的树枝，不在T中的边为T的弦.称T的所有弦的导出子图为T的余树，记作.例,9,定理10.3 无向图G有生成树当且仅当G连通.,生成树存在条件,推论 G为n阶m条边的无向连通图，则mn1.,证 必要性显然.证充分性若G中无回路，则G为自己的生成树若G中含圈，任取一圈，随意地删除圈上的一条边;若仍有圈,再任取一个圈并删去这个圈上的一条边，重复进行,直到最后无圈为止.最后得到的图无圈（当然无回路）、连通且是G的生成子图，因而是G的生成树这个产生生成树的方法称为破圈法,10,最小生成树,定义10.3 设无向连通带权图G=，T是G的一棵生成树，T的各边权之和称为T的权，记作W(T)G的所有生成树中权最小的生成树称为G的最小生成树.,避圈法（Kruskal）输入:连通图G=输出:G的最小生成树T 1.将G中非环边按权从小到大排列:W(e1)W(e2)W(em).2.令Te1,i2.3.若ei与T中的边不构成回路,则令TTei.4.若|T|n-1,则令ii+1,转3.,11,例4 求图的一棵最小生成树.,W(T)=38,实例,12,16.3 根树及其应用,定义10.4 若有向图的基图是无向树,则称这个有向图为有向树.一个顶点的入度为0、其余顶点的入度为1的有向树称为根树入度为0的顶点称为树根，入度为1出度为0的顶点称为树叶，入度为1出度不为0的顶点称为内点，内点和树根统称为分支点从树根到顶点v的路径的长度(即,路径中的边数)称为v的层数.所有顶点的最大层数称为树高,根树的画法树根放上方，省去所有有向边上的箭头例,13,家族树与根树的分类,定义10.5 设T为一棵非平凡的根树,vi,vjV(T),若vi可达vj，则称vi为vj的祖先,vj为vi的后代;若vi邻接到vj,则称vi为vj的父亲,vj为vi的儿子.若vj,vk的父亲相同,则称vj与vk是兄弟 将根树T中层数相同的顶点都标定次序,称T为有序树根树的分类：(1)若T的每个分支点至多有r个儿子，则称T为r叉树.(2)若T的每个分支点都恰好有r个儿子,则称T为r叉正则树.(3)若T是r叉正则树,且所有树叶的层数相同,则称T为r叉完全正则树.有序的r叉树,r叉正则树,r叉完全正则树分别称作 r叉有序树,r叉正则有序树,r叉完全正则有序树,14,根子树与最优二叉树,定义10.6 设T为一棵根树,vV(T),称v及其后代的导出子图Tv为以v为根的根子树 2叉正则有序树的每个分支点的两个儿子导出的根子树分别称为该分支点的左子树和右子树定义10.7 设2叉树T 有t片树叶v1,v2,vt,权分别为w1,w2,wt,称 为T 的权,其中li是vi 的层数.在所有有t片树叶,带权w1,w2,wt 的2叉树中,权最小的2叉树称为最优2叉树.,15,Huffman算法,Huffman算法输入:实数w1,w2,wt输出:最优二叉树1.作t片树叶,分别以w1,w2,wt为权.2.在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点,添加一个新分支点,它以这2个顶点为儿子,其权等于这2个儿子的权之和.3.重复2,直到只有1个入度为0的顶点为止.W(T)等于所有分支点的权之和.,16,例 5 求权为2,2,3,3,5的最优树.解,实例,W(T)=34,17,前缀码,定义10.8 设12n1n是长为n的符号串,称其子串1,12,12n为该符号串的前缀.设A=1,2,m是一个符号串集合,若A的任意两个符号串都互不为前缀,则称A为前缀码.由0-1符号串构成的前缀码称作二元前缀码 例 1,00,011,0101,01001,01000为前缀码 1,00,011,0101,0100,01001,01000不是前缀码,18,用2叉树产生二元前缀码例,一棵正则2叉树产生惟一的前缀码（按左枝标0，右枝标1）,前缀码的产生,19,最佳前缀码,设符号Ai在传输中出现的频率为pi,二元前缀码的长为li,1it,传输m个符号需要m 个二进制位.最小的二元前缀码称作最佳前缀码.最佳前缀码可用Huffman算法计算以频率为权的最优二叉树产生.例6 设在通信中,八进制数字出现的频率如下：0：25%1：20%2：15%3：10%4：10%5：10%6：5%7：5%求传输它们的最佳前缀码,并求传输10n(n2)个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的(长为3)的码字传输需要多少个二进制数字？,20,解 传输100个八进制数字中各数字出现的个数,即以100乘各频率为:25,20,15,10,10,10,5,5,以它们为权构造最优二叉树.,实例,最佳前缀码 01-0 11-1 001-2 100-3 101-4 0001-500000-6 00001-7,W(T)=285，传输10n(n2)个八进制数字,用最佳前缀码需2.8510n位，用等长码需310n位.,21,有序树的行遍方式,行遍(周游)有序树对每个顶点访问且仅访问一次.对2叉有序正则树的周游方式：中序行遍法.访问次序为：左子树、根、右子树 前序行遍法.访问次序为：根、左子树、右子树 后序行遍法.访问次序为：左子树、右子树、根,例 用中序,前序,后序行遍法访问的结果分别为：b a(f d g)c e，a b(c(d f g)e)，b(f g d)e c)a,22,用2叉有序树存放算式,用2叉有序树表示含有2元运算和1元运算的算式:每个分支点放一个运算符,其运算对象是以它的儿子为树根的子树所表示的子算式.规定运算对象的排列顺序,如被除数、被减数放在左边所有的变量和常量都放在树叶上.,例(b+(c+d)a)(ef)(g+h)(ij)用中序行遍法访问还原算式,23,波兰符号法,波兰符号法(前缀符号法):按前序行遍法访问存放算式的2叉有序树,且不加括号.运算规则:从右到左每个运算符号对其后面紧邻的两个或一个对象进行运算.如对上页的算式 b+c d a e f+g h i j 逆波兰符号法(后缀符号法):按后序行遍法访问,且不加括号.运算规则:从左到右每个运算符对其前面紧邻的两个或一个对象进行运算.如对上页的算式 b c d+a e f g h+i j,24,第十章 习题课,主要内容无向树及其性质生成树、最小生成树根树及其分类、最优二叉树、最佳前缀码、波兰符号法、逆波兰符号法基本要求深刻理解无向树的定义及性质熟练地求解无向树准确地求出给定带权连通图的最小生成树理解根树及其分类等概念熟练掌握求最优二叉树及最佳前缀码的方法掌握波兰符号法与逆波兰符号法,25,练习1,1.无向树 T 有ni个i 度顶点，i=2,3,k，其余顶点全是树叶，求T 的树叶数.,26,2设n阶非平凡的无向树T中，(T)k，k 1.证明T至少 有k片树叶.,练习2,27,3设G为n 阶无向简单图，n5，证明G 或 中必含圈.,练习3,28,证二.在G与 中有一个(不妨设为G)边数若G是森林,则mn-1,矛盾.,练习3,29,4画出基图为图所示无向树的所有非同构的根树,练习4,解 以a,b,c,d为根的根树同构,选a为根,如(1);以 e,g 为根的根树同构，取 g为根，如(2)；以 f 为根，如(3).,(1)(2)(3),30,5设T 是正则2叉树，T 有t 片树叶，证明T的阶数 n=2t1.,证一.利用正则2叉树的定义及树的性质直接证明.(1)n=t+i(i为分支点数)(2)n=m+1（m为T的边数）(3)m=2i（正则2叉树定义）由(2)、(3)得，代入（1）得n=2t1.,练习5,证二.利用握手定理及树的性质证.T的树根为2度顶点，所有内点为3度顶点，叶为1度顶点，有(1)2m=2+3(i1)+t(2)m+1=n=i+t由(1)和(2)可解得 n=2t1.,