北大离散数学chap9

第九章

树第一节

无向树及生成树

2021/3/111内容：无向树，生成树。重点：1、无向树的定义(包括等价定义)，2、无向树的性质，3、生成树的定义，由连通图构造最小生成树的方法。本章中所谈回路均指简单回路或初级回路。2021/3/112一、无向树。1、无向树——连通且不含回路的无向图。无向树简称树，常用表示。平凡树——平凡图。森林

——连通分支数大于等于2，且每个连通分支都是树的无向图。2021/3/113例1、2021/3/114例1、2021/3/1152、树的六个等价定义。(1)连通且不含回路。(2)的每对顶点间具有唯一的路径。(3)连通且。(4)无回路且。定理：设，，，则以下命题等价。2021/3/1162、树的六个等价定义。(5)无回路，但在中任两个不相邻的顶点之间增加一条边，就形成唯一的一条初级回路。(6)是连通的，但删除任何一条边后，就不连通了。2021/3/1173、性质。(1)树中顶点数与边数的关系：。(2)定理：非平凡树至少2片树叶。证明：设为阶非平凡树，设有片树叶，则有个顶点度数大于等于2，由握手定理，又由(1)，代入上式，解得，即至少2片叶。2021/3/118例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(1)2021/3/119例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(2)2021/3/1110例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(3)2021/3/1111例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(4)2021/3/1112例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(5)2021/3/1113例3、(1)一棵树有7片叶，3个3度顶点，其余都是4度顶点，求4度顶点多少个？解：设有个4度顶点，则顶点数，边数，由握手定理，，解得，故这棵树有1个4度顶点。2021/3/1114例3、(2)一棵树有2个4度顶点，3个3度顶点，其余都是树叶，求这棵树共有多少个顶点？解：设有片树叶，则顶点数，边数，由握手定理，，解得，故顶点总数为个。2021/3/1115二、生成树。1、定义：设是无向连通图，是的生成子图，若是树，称是的生成树。树枝弦余树——在中的边，——不在中的边，——的所有的弦的集合的导出子图。2021/3/1116例4、上图中，(2)是(1)的生成树，(3)是(2)的余树。注意：(1)生成树不唯一，(2)余树不一定是树。2021/3/11172、连通图的性质。设为连通图，，，(1)至少有一棵生成树，(2)，(3)设是的生成树，是的余树，则中有条边。已知连通图，求其生成树步骤。2021/3/11183、最小生成树。对于有向图或无向图的每条边附加一个实数，则称为边上的权，连同附加在各边上的实数称为带权图，记为。最小生成树——各边权和最小的生成树。定义：设无向连通带权图，是的一棵生成树，各边带权之和称为的权，记作。2021/3/1119求最小生成树的方法——避圈法。设阶无向连通带权图中有条边，它们带的权分别为，不妨设，(1)取在中(非环，若为环，则弃)。(2)若不与构成回路，取在中，否则弃，再查，继续这一过程，直到形成树为止。2021/3/1120解：例5、求以下连通图的最小生成树及。2021/3/1121解：例5、求以下连通图的最小生成树及。2021/3/1122解：例5、求以下连通图的最小生成树及。2021/3/1123解：例5、求以下连通图的最小生成树及。2021/3/1124注意：的最小生成树可能不唯一，但的不同最小生成树权的值一样。2021/3/1125第二节

根树及其应用2021/3/1126内容：有向树，根树，最优二元树。重点：1、有向树及根树的定义，2、家族树，有序树，元树的概念，3、最优2元树的概念及哈夫曼算法。2021/3/1127一、根树。1、有向树：一个有向图，若略去有向边的方向所得的无向图为一棵无向树，则称为有向树。2、根树：一棵非平凡的有向树，如果有一个顶点的入度为0，其余顶点的入度均为1，则称此有向树为根树。2021/3/1128根树的顶点树叶(入度为1，出度为0)分支点树根(入度为0)内点(入度为1，出度大于0)2021/3/1129例1、2021/3/1130例1、2021/3/11313、树高。的层数——从树根到顶点的通路长度，记。树高——树中顶点的最大层数，记。2021/3/1132如例1(2)中，2021/3/11334、家族树。一棵根树可以看成一棵家族树。(1)若顶点邻接到顶点，则称为的儿子，为的父亲，(2)若同为的儿子，则称为兄弟，(3)若，而可达，则称为的祖先，为的后代。2021/3/11345、根子树。树的根子树——的非树根的顶点及其后代导出的子图。2021/3/1135例2、2021/3/1136二、元树。1、有序树——每一层上都规定次序的根树。2、元树——每个分支点至多有个儿子的根树。元正则树——每个分支点恰有个儿子的根树。元有序树元有序正则树2021/3/1137二、元树。元有序完全正则树注意：2元有序正则树是最重要的一种元树。1、有序树——每一层上都规定次序的根树。2、元完全正则树的层数相同(等于树高)。——元正则树，且所有树叶2021/3/1138例3、2元有序树2元有序正则树2021/3/1139例3、2元有序完全正则树2021/3/11403、最优2元树。(1)的权最优2元树——权最小的2元树。——中每片树叶所带权与其层高乘积的和。记为2021/3/1141例4、下图中的都是带权1，3，4，5，6的2元树，求，，。解：2021/3/1142例4、下图中的都是带权1，3，4，5，6的2元树，求，，。解：2021/3/1143例4、下图中的都是带权1，3，4，5，6的2元树，求，，。解：但不能判定是最优2元树。2021/3/1144(2)求最优2元树的算法。算法：给定实数片树叶的权)，且(，选连接得一分支点，从中选两个最小的，连接得一分支点，重复。2021/3/1145例5、求带权1,3,4,5,6的最优2元树及。解：其实等于的各分支点的权之和，即2021/3/1146例5、求带权1,3,4,5,6的最优2元树及。解：其实等于的各分支点的权之和，即最优树是不唯一的，但算法得到的树一定是最优树。2021/3/1147例6、(1)求带权为2,3,5,7,8,9的最优2元树，解：(2)2021/3/1148例6、(1)求带权为2,3,5,7,8,9的最2优元树，解：(3)2021/3/1149例6、(1)求带权为2,3,5,7,8,9的最2优元树，解：(4)有___片树叶。2021/3/1150例6、(1)求带权为2,3,5,7,8,9的最2优元树，解：(5)有__个2度顶点，__个3度顶点，__个4度顶点。2021/3/11514、求最佳前缀码。(了解)最优2元树的用途之一是求最佳前缀码。在通讯中，我们常用0和1的符号串作为英文字母的传送信息，26个英文字母被使用的频率往往是不同的。为了使整个信息的长度尽可能短，自然希望用较短的符号串去表示使用频率高的英文字母，用较长的符号串表示使用频率低的英文字母。

2021/3/11524、求最佳前缀码。(了解)最优元树的用途之一是求最佳前缀码。为了使编码在使用中既快速又准确，可以用求

最优2元树的算法解决这个问题。2021/3/1153第九章

小结与例题2021/3/1154一、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林；平凡树；生成树，最小生成树。2、运用。(1)无向树的六个等价定义。(2)画顶点数为的所有非同构的无向树。2021/3/1155一、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林；平凡树；生成树，最小生成树。2、运用。(3)根据握手定理及树的某些性质，求顶点数或某些顶点的度数。(4)求生成树，最小生成树。2021/3/1156二、根树及其应用。1、基本概念。有向树；根树；树根，内点，树叶，分支点；顶点的层数与树高；有序树，正则树，完全树；最优二元树。2021/3/1157二、根树及其应用。2、运用。(1)按定义画出等等。元树，元正则树，元有序树(2)利用算法求最优二元树。2021/3/1158例1、画出满足下列要求的所有非同构的无向树。(1)2个顶点(2)3个顶点(3)4个顶点2021/3/1159例1、画出满足下列要求的所有非同构的无向树。(4)5个顶点2021/3/1160例2、若无向图中有个顶点，条边，则为树。这个命题正确吗？解：命题不正确。反例：2021/3/1161例3、设连通图如下图所示，分别求出它们的所有非同构的生成树。解：的生成树有：2021/3/1162例3、设连通图如下图所示，分别求出它们的所有非同构的生成树。解：的生成树有：2021/3/1163例4、一棵树有个顶点的度数为2，个顶点的度数为3，···，个顶点的度数为，而其余的顶点都是树叶。求该树的树叶数。解：设有片树叶，依握手定理及树的性质，得解得：2021/3/1164解：不一定，反例：例5、一个有向图，仅有一个顶点入度为0，其余顶点的入度均为1，一定是根树吗？2021/3/1165例6、设为二元正则树，为边数，为树叶数。证明：，其中。证法一：设中顶点数为，分支点数为，由二元正则树的定义，知由以上三个式子，得。2021/3/1166例6、