北大离散数学chap.ppt

第九章 树 第一节 无向树及生成树 第二节 根树及其应用 第九章 小结与例题 3、树高。 的层数 ——从树根到顶点 的通路 长度，记 。 树高 ——树中顶点的最大层数，记 。 如例1(2)中， 4、家族树。 一棵根树可以看成一棵家族树。 (1) 若顶点 邻接到顶点 ，则称 为 的儿子， 为 的父亲， (2) 若 同为 的儿子，则称 为兄弟， (3) 若 ，而 可达 ，则称 为 的祖先， 为 的后代。 5、根子树。 树 的根子树 —— 的非树根的顶点 及其 后代导出的子图。 例2、 二、 元树。 1、有序树 ——每一层上都规定次序的根树。 2、 元树 ——每个分支点至多有 个儿子的根树。 元正则树 ——每个分支点恰有 个儿子的根树。 元有序树 元有序正则树 二、 元树。 元有序完全正则树 注意：2元有序正则树是最重要的一种 元树。 1、有序树 ——每一层上都规定次序的根树。 2、 元完全正则树 的层数相同 (等于树高)。 —— 元正则树，且所有树叶 例3、 2元有序树 2元有序正则树 例3、 2元有序完全正则树 3、最优2元树。 (1) 的权 最优2元树 ——权最小的2元树。 —— 中每片树叶所带权与其层高 乘积的和。 记为 例4、下图中的 都是带权1，3，4，5，6 的2元树，求 ， ， 。 解： 例4、下图中的 都是带权1，3，4，5，6 的2元树，求 ， ， 。 解： 例4、下图中的 都是带权1，3，4，5，6 的2元树，求 ， ， 。 解： 但不能判定 是最优 2元树。 (2) 求最优2元树的算法。 算法： 给定实数 片树叶的权)，且 ( ， 选 连接得一分支点， 从 中选两个最小的，连接 得一分支点， 重复 。 例5、求带权1, 3, 4, 5, 6的最优2元树 及 。 解： 其实 等于 的 各分支点的权之和，即 例5、求带权1, 3, 4, 5, 6的最优2元树 及 。 解： 其实 等于 的 各分支点的权之和，即 最优树是不唯一的，但 算法得到的树 一定是最优树。 例6、(1) 求带权为2, 3, 5, 7, 8, 9的最优2元树 ， 解： (2) 例6、(1) 求带权为2, 3, 5, 7, 8, 9的最2优元树 ， 解： (3) 例6、(1) 求带权为2, 3, 5, 7, 8, 9的最2优元树 ， 解： (4) 有___片树叶。 例6、(1) 求带权为2, 3, 5, 7, 8, 9的最2优元树 ， 解： (5) 有__个2度顶点，__个3度顶点，__个4度顶点。 4、求最佳前缀码。(了解) 最优2元树的用途之一是求最佳前缀码。 在通讯中，我们常用0和1的符号串作为英文字母的传送信息，26个英文字母被使用的频率往往是不同的。为了使整个信息的长度尽可能短，自然希望用较短的符号串去表示使用频率高的英文字母，用较长的符号串表示使用频率低的英文字母。 4、求最佳前缀码。(了解) 最优元树的用途之一是求最佳前缀码。 为了使编码在使用中既快速又准确，可以用求 最优2元树的 算法解决这个问题。 * 内容：无向树，生成树。 重点：1、无向树的定义 (包括等价定义)， 2、无向树的性质， 3、生成树的定义，由连通图构造最小 生成树的方法。 本章中所谈回路均指简单回路或初级回路。 一、无向树。 1、无向树 ——连通且不含回路的无向图。 无向树简称树，常用 表示。 平凡树 ——平凡图。 森林 ——连通分支数大于等于2，且每个连通 分支都是树的无向图。 例1、 例1、 2、树的六个等价定义。 (1) 连通且不含回路。 (2) 的每对顶点间具有唯一的路径。 (3) 连通且 。 (4) 无回路且 。 定理：设 ， ， ， 则以下命题等价。 2、树的六个等价定义。 (5) 无回路，但在 中任两个不相邻的顶点 之间增加一条边，就形成唯一的一条初级 回路。 (6) 是连通的，但删除任何一条边后，就不 连通了。 3、性质。 (1) 树中顶点数与边数的关系： 。 (2) 定理：非平凡树至少2片树叶。 证明： 设 为 阶非平凡树， 设 有 片树叶，则有 个顶点度数大于等 于2， 由握手定理， 又由(1) ，代入上式，解得 ， 即 至少2片叶。 例2、画出所有的6个顶点的非同构的树。 解：所要画的树有6个顶点，则边数为5，因此 6个顶点的度数之和为10，可以产生以下五种 度数序列： (1) 例2、画出所有的6个顶点的非同构的树。 解：所要画的树有6个顶点，则边数为5，因此 6个顶点的度数之和为10，可以产生以下五种 度数序列： (2) 例2、画出所有的6个顶点的非同构的树。 解：所要画的树有6个顶点，则边数为5，因此 6个顶点的度数之和为10，可以产生以下五种 度数序列： (3) 例2、画出所有的6个顶点的非同构的树。 解：所要画的