北大离散数学chap_第1页
北大离散数学chap_第2页
北大离散数学chap_第3页
北大离散数学chap_第4页
北大离散数学chap_第5页
已阅读5页，还剩65页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第九章树,第一节无向树及生成树,内容：无向树，生成树。,重点：1、无向树的定义(包括等价定义)，,2、无向树的性质，,本章中所谈回路均指简单回路或初级回路。,一、无向树。,1、无向树,连通且不含回路的无向图。,平凡树,平凡图。,森林,例1、,例1、,2、树的六个等价定义。,2、树的六个等价定义。,3、性质。,(2)定理：非平凡树至少2片树叶。,由握手定理，,例2、画出所有的6个顶点的非同构的树。,(1),例2、画出所有的6个顶点的非同构的树。,(2),例2、画出所有的6个顶点的非同构的树。,(3),例2、画出所有的6个顶点的非同构的树。,(4),例2、画出所有的6个顶点的非同构的树。,(5),故这棵树有1个4度顶点。,二、生成树。,树枝,弦,余树,例4、,上图中，(2)是(1)的生成树，,(3)是(2)的余树。,注意：,(1)生成树不唯一，,(2)余树不一定是树。,2、连通图的性质。,3、最小生成树。,最小生成树,各边权和最小的生成树。,求最小生成树的方法,解：,解：,解：,解：,注意：,第二节根树及其应用,内容：有向树，根树，最优二元树。,重点：1、有向树及根树的定义，,一、根树。,1、有向树：,2、根树：,根树的顶点,例1、,例1、,3、树高。,树高,如例1(2)中，,4、家族树。,一棵根树可以看成一棵家族树。,5、根子树。,例2、,1、有序树,每一层上都规定次序的根树。,元正则树,元有序树,元有序正则树,元有序完全正则树,例3、,2元有序树,2元有序正则树,例3、,2元有序完全正则树,3、最优2元树。,最优2元树,权最小的2元树。,解：,解：,解：,(2)求最优2元树的算法。,算法：,解：,解：,解：,(2),解：,(3),解：,解：,4、求最佳前缀码。(了解),最优2元树的用途之一是求最佳前缀码。,在通讯中，我们常用0和1的符号串作为英文字母的传送信息，26个英文字母被使用的频率往往是不同的。为了使整个信息的长度尽可能短，自然希望用较短的符号串去表示使用频率高的英文字母，用较长的符号串表示使用频率低的英文字母。,4、求最佳前缀码。(了解),最优元树的用途之一是求最佳前缀码。,第九章小结与例题,一、无向树及生成树。,1、基本概念。,2、运用。,(1)无向树的六个等价定义。,一、无向树及生成树。,1、基本概念。,2、运用。,(4)求生成树，最小生成树。,二、根树及其应用。,1、基本概念。,二、根树及其应用。,2、运用。,例1、画出满足下列要求的所有非同构的无向树。,(1)2个顶点,(2)3个顶点,(3)4个顶点,例1、画出满足下列要求的所有非同构的无向树。,(4)5个顶点,解：命题不正确。,反例：,得,解得：
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论