《离散数学第九章ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学第九章ppt课件.ppt（71页珍藏版）》请在三一办公上搜索。
1、第九章 树,第一节 无向树及生成树,内容：无向树，生成树。,重点：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
2、),故这棵树有1个4度顶点。,二、生成树。,树枝,弦,余树,例4、,上图中，(2)是(1)的生成树，,(3)是(2)的余树。,注意：,(1)生成树不唯一，,(2)余树不一定是树。,2、连通图的性质。,3、最小生成树。,最小生成树,各边权和最小的生成树。,求最小生成树的方法,解：,解：,解：,解：,注意：,第二节 根树及其应用,内容：有向树，根树，最优二元树。,重点：1、有向树及根树的定义，,一、根树。,1、有向树：,2、根树：,根树的顶点,例1、,例1、,3、树高。,树高,如例1(2)中，,4、家族树。,一棵根树可以看成一棵家族树。,5、根子树。,例2、,1、有序树,每一层上都规定次序的根树。
3、,元正则树,元有序树,元有序正则树,元有序完全正则树,例3、,2元有序树,2元有序正则树,例3、,2元有序完全正则树,1、前序遍历,根，左，右。,2、,中序遍历,左，根，右。,3、,后序遍历,左，右，根。,3、最优2元树。,最优2元树,权最小的2元树。,解：,解：,解：,(2)求最优2元树的算法。,算法：,解：,解：,解：,(2),解：,(3),解：,解：,4、求最佳前缀码。(了解),最优2元树的用途之一是求最佳前缀码。,在通讯中，我们常用0和1的符号串作为英文字母的传送信息，26个英文字母被使用的频率往往是不同的。为了使整个信息的长度尽可能短，自然希望用较短的符号串去表示使用频率高的英文字母
4、，用较长的符号串表示使用频率低的英文字母。,4、求最佳前缀码。(了解),最优元树的用途之一是求最佳前缀码。,第九章 小结与例题,一、无向树及生成树。,1、基本概念。,2、运用。,(1)无向树的六个等价定义。,一、无向树及生成树。,1、基本概念。,2、运用。,(4)求生成树，最小生成树。,二、根树及其应用。,1、基本概念。,二、根树及其应用。,2、运用。,例1、画出满足下列要求的所有非同构的无向树。,(1)2个顶点,(2)3个顶点,(3)4个顶点,例1、画出满足下列要求的所有非同构的无向树。,(4)5个顶点,解：命题不正确。,反例：,得,解得：,解：不一定，,反例：,由二元正则树的定义，知,证法二：,证法二：由握手定理知，,解：,结 束 语,课 程 结 束，谢 谢 大 家！,
