计算机数学-(5).pptx
《计算机数学-(5).pptx》由会员分享,可在线阅读,更多相关《计算机数学-(5).pptx(90页珍藏版)》请在咨信网上搜索。
1、第5章 树,引言,树是图论中应用最广泛、最重要的子类之一。1847年,Gustav Kirchhoff(1824-1887)在有关电网的著作中首次使用了树,后来Arthur Cayley(1821-1895)重新发展并命名了树。现在,计算机科学广泛采用了树的概念。比如,在数据库系统中用树来组织信息,在编绎程序中用树表示源程序的语法结构,在最优化问题的求解中树也起着重要作用。本章主要介绍树的基本术语,树的子类(如根数和二叉树),以及树的应用。,例:2011年法网四强结果图,我国选手李娜获得最终法网冠军,5.1 树的概念,树是没有简单回路的连通无向图例:判断下图中的图哪些是树?为什么?,森林是每个
2、连通分支都是树的无向图,5.1 树的概念性质,1、一个无向图是树当且仅当在它的每对顶点之间存在唯一简单路径2、带有n个顶点的树含有n-1条边3、树是边数最多的无回路图,树是边数最少的连通图4、n(n2)阶树T至少有2个叶子。,5.1 树的概念,根树是指定一个顶点作为根并且每条边的方向都离开根的树。,结点v的层数是从根结点到结点v的简单路径的长度。根树的深度是树的最大层数。,5.1 树的概念,例5.1.4如果把e指定为图5.1.5中树T的根结点,我们就得到如图5.1.5所示的根树T1。结点a,d,e,h,j的层数分别为2,1,0,2,3。树T1的深度为3。很显然,选择不同的根会产生不同的根树。,
3、5.1 树的概念树模型,例5.1.5一个虚拟大学的行政结构图。,10.3.5 根树的应用,计算机的文件结构,练习:完成习题5.1的1-3题,5.1 树的概念霍夫曼(Huffman)编码,计算机中信息的表示和传输是通过编码来实现的。在计算机内部进行编码或表示字符的最常用方法是使用由符号0和1组成的定长二进制符号串。例如ASCII(美国标准信息交换码)采用7位二进制串来表示一个字符,,5.1 树的概念-最优树与哈夫曼算法,在计算机及通讯事业中,常用二进制编码来表示符号,称之为码字(codeword)。例如,可用00、01、10、11分别表示字母A、B、C、D。如果字母A、B、C、D出现的频率是一样
4、的,传输100个字母用200个二进制位。但实际上字母出现的频率很不一样,如A出现的频率为50,B出现的频率为25,C出现的频率为20,D出现的频率为5。能否用不等长的二进制序列表示字母A、B、C、D,使传输的信息的二进制位尽可能少呢?事实上,可用000表示字母D,用001表示字母C,01表示B,1表示A。这样表示,传输100个字母所用的二进制位为35+320+225+150 = 175。这种表示比用等长的二进制序列表示法好,节省了二进制位。但当我们用1表示A,用00表示B,用001表示C,用000表示D时,如果接收到的信息为001000,则无法辨别它是CD还是BAD。因而,不能用这种二进制序列
5、表示A、B、C、D,要寻找另外的表示法。,定义,设a1a2an-1an为长度为n的符号串,称其子串a1,a1a2,, a1a2an-1分别为a1a2an-1an的长度为1,2,n-1的前缀(Prefix)。 设A = b1, b2, , bm是一个符号串集合,若对任意bi, bjA,bibj,bi不是bj的前缀,bj也不是bi的前缀,则称A为前缀码(Prefixed Code)。若符号串bi(i = 1, 2, m)中,只出现0和1两个符号,则称A为二元前缀码(Binary Prefixed Code)。,1, 01, 001, 000是前缀码1, 11, 001, 0011不是前缀码。,用二
6、元树产生二元前缀码,给定一棵二元树T,假设它有t片树叶。 设v是T任意一个分支点,则v至少有一个儿子至多有两个儿子。若v有两个儿子,则在由v引出的两条边上,左边的标上0,右边的标上1;若v只有一个儿子,在v引出的边上可标0也可标1。设vi为T的任意一片树叶,从树根到vi的通路上各边的标号组成的符号串放在vi处,t片树叶处的t个符号串组成的集合为一个二元前缀码。,vi中的符号串的前缀均在vi所在的通路上,因而所得集合为二元(0和1组成)前缀码。,若T存在带一个儿子的分支点,则由T产生的前缀码不唯一,但T若为完全二元树,则T产生的前缀码就是唯一的了。,例,图中所示的二元树产生的前缀码为:1,00,
7、010,011。因此用1表示A,用00表示B,用010表示 C,用011表示 即可满足要求。,当知道了传输的符号出现的频率时,如何选择前缀码,使传输的二进制位尽可能地少呢?先产生最优二元树T,然后用T产生二元前缀码。,最优树,定义 设有一棵二元树,若对其所有的t片叶赋以权值w1、w2、wt,则称之为赋权二元树(Power Binary Tree);若权为wi的叶的层数为L(wi),则称 为该赋权二元树的权;而在所有赋权w1、w2、wt的二元树中,W(T)最小的二元树称为最优树(Optimal Tree)。 1952年哈夫曼(Huffman)给出了求最优树的方法。该方法的关键是:从带权为W1+W
8、2、W3、Wt(这里假设W1W2Wt)的最优树T中得到带权为W1、W2、Wt的最优树。,算法5.1.8 哈夫曼算法:,初始:令S = W1, W2, , Wt;从S中取出两个最小的权Wi和Wj,画结点vi,带权Wi,画结点vj,带权Wj。画vi和vj的父亲v,连接vi和v,vj和v,令v带权Wi+Wj;令S = (S -Wi, Wj)Wi+Wj;判断S是否只含一个元素?若是,则停止,否则转2。,例10.3.9,求带权7、8、9、12、16的最优树。,15,7,8,9,16,12,21,31,52,例,用机器分辨一些币值为1分、2分、5分的硬币,假设各种硬币出现的概率分别为0.5、0.4、0.1
9、。问如何设计一个分辨硬币的算法,使所需的时间最少(假设每作一次判别所用的时间相同,以此为一个时间单位)?,所需时间:20.1+20.4+10.5 = 1.5(时间单位)。,例,已知字母A、B、C、D、E、F出现的频率如下:A30,B25,C20D10,E10,F 5构造一个表示A、B、C、D、E、F前缀码,使得传输的二进制位最少。解(1)求带权30,25,20,10,10,5的最优二元树T。(2)在T上求一个前缀码。,(3)设树叶vi带权为w100 = w,则vi处的符号串表示出现频率为w的字母。01,10,11,001,0001,0000为一前缀码,其中0000表示F,0001表示E,001
10、表示D,01表示C,10表示B,11表示A。传输100个这样的字母所用的二进制位为:4(5+10)+310+2(20+25+30) = 240。,例:我们利用上面的霍夫曼码树对二进制位串01010111进行解码。,练习:完成课本习题5.1的4-9题,5.2 树的特征,我们可以把一个家谱树看成一个根树。如古希腊神话中诸神的家谱树的一部分,5.2 树的特征术语,阅读课本定义5.2.1理解父亲,祖先,孩子,子孙,兄弟,外部结点(叶子),内部结点,子树的概念,例5.2.6设T是一个树,且有3个3度结点,1个2度结点,其余均为1度结点。那么该无向树共有多少个结点?对此,画出两棵不同的树。,练习:完成课本
11、习题5.2,5.3 最小生成树生成树的概念,定义5.3.1如果树T是包含图G的所有结点的一个子图,那么就称树T是图G的一个生成树。,5.3 最小生成树生成树,判断下图中的图(b)、(c)、(d)、(e)是否是图(a)的生成树。,定理5.3.3图G有一个生成树T当且仅当G是连通的。,破圈法与避圈法,算法5.3.1 求连通图G = 的生成树的破圈法:每次删除回路中的一条边,其删除的边的总数为m-n+1。算法5.3.2 求连通图G = 的生成树的避圈法:每次选取G中一条与已选取的边不构成回路的边,选取的边的总数为n-1。由于删除回路上的边和选择不构成任何回路的边有多种选法,所以产生的生成树不是惟一的
12、。,例1,分别用破圈法和避圈法求下图的生成树。,1,2,3,4,5,6,分析 分别用破圈法和避圈法依次进行即可。用破圈法时,由于n = 6,m = 9,所以m-n+1 = 4,故要删除的边数为4,因此只需4步即可。用避圈法时,由于n = 6,所以n-1 = 5,故要选取5条边,因此需5步即可。,破圈法,避圈法,由于生成树的形式不惟一,故上述两棵生成树都是所求的。 破圈法和避圈法的计算量较大,主要是需要找出回路或验证不存在回路。,1,2,3,4,5,6,最小生成树,定义5.3.4 设G = 是连通的赋权图,T是G的一棵生成树,T的每个树枝所赋权值之和称为T的权(Weight),记为w(T)。G中
13、具有最小权的生成树称为G的最小生成树(Minimal Spanning Tree)。,一个无向图的生成树不是惟一的,同样地,一个赋权图的最小生成树也不一定是惟一的。,算法5.3.5 Kruskal算法,(1)在G中选取最小权边e1,置i = 1。(2)当i = n-1时,结束,否则转(3)。(3)设已选取的边为e1, e2, , ei,在G中选取不同于e1, e2, , ei的边ei+1,使e1, e2, , ei, ei+1中无回路且ei+1是满足此条件的最小权边。(4)置i = i+1,转(2)。,要点:在与已选取的边不构成回路的边中选取最小者。,在Kruskal算法的步骤1和3中,若满足
14、条件的最小权边不止一条,则可从中任选一条,这样就会产生不同的最小生成树。,例2,用Kruskal算法求图中赋权图的最小生成树。,解 n=12,按算法要执行n-1=11次,,w(T) = 36。,算法5.3.5 Prim算法,(1)在G中任意选取一个结点v1,置VT = v1, ET = ,k = 1;(2)在V-VT中选取与某个viVT邻接的结点vj,使得边(vi, vj)的权最小,置VT = VTvj, ET = ET(vi, vj),k = k+1;(3)重复步骤2,直到k = |V|。,要点:从任意结点开始,每次增加一条最小权边构成一棵新树。,在Prim算法的步骤2中,若满足条件的最小权
15、边不止一条,则可从中任选一条,这样就会产生不同的最小生成树。,例3,用Prim算法求图中赋权图的最小生成树。,解 n = 7,按算法要执行n-1 = 6次,,w(T) = 25。,由Prim算法可以看出,每一步得到的图一定是树,故不需要验证是否有回路,因此它的计算工作量较Kruskal算法要小。,5.3 小结,树是不含回路的连通图。注意把握树的性质,特别是树中叶结点的数目及边数与结点数的关系:m = n-1;生成树是无向连通图是树的生成子图。注意把握所有连通图都有生成树,会使用避圈法、破圈法算法求生成树;最小生成树是赋权连通图的权值之和最小的生成树。会使用Kruskal算法和Prim算法求最小
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 数学
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。