离散数学第九章课件

第九章

树第一节

无向树及生成树

第九章树第一节无向树及生成树1内容：无向树，生成树。重点：1、无向树的定义

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

——连通分支数大于等于2，且每个连通分支都是树的无向图。一、无向树。1、无向树——连通且不含回路的无向图。无向树简称3例1、例1、4例1、例1、52、树的六个等价定义。(1)连通且不含回路。(2)的每对顶点间具有唯一的路径。(3)连通且。(4)无回路且。定理：设，，，则以下命题等价。2、树的六个等价定义。(1)连通且不含回路。(2)的每对顶点62、树的六个等价定义。(5)无回路，但在中任两个不相邻的顶点之间增加一条边，就形成唯一的一条初级回路。(6)是连通的，但删除任何一条边后，就不连通了。2、树的六个等价定义。(5)无回路，但在中任两个不相邻的顶点73、性质。(1)树中顶点数与边数的关系：。(2)定理：非平凡树至少2片树叶。证明：设为阶非平凡树，设有片树叶，则有个顶点度数大于等于2，由握手定理，又由(1)，代入上式，解得，即至少2片叶。3、性质。(1)树中顶点数与边数的关系：。(2)定理：非8例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(1)例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶9例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(2)例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶10例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(3)例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶11例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(4)例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶12例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(5)例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶13例3、(1)一棵树有7片叶，3个3度顶点，其余都是4度顶点，求4度顶点多少个？解：设有个4度顶点，则顶点数，边数，由握手定理，，解得，故这棵树有1个4度顶点。例3、(1)一棵树有7片叶，3个3度顶点，其余都是4度顶点14例3、(2)一棵树有2个4度顶点，3个3度顶点，其余都是树叶，求这棵树共有多少个顶点？解：设有片树叶，则顶点数，边数，由握手定理，，解得，故顶点总数为个。例3、(2)一棵树有2个4度顶点，3个3度顶点，其余都是树15二、生成树。1、定义：设是无向连通图，是的生成子图，若是树，称是的生成树。树枝弦余树——在中的边，——不在中的边，——的所有的弦的集合的导出子图。二、生成树。1、定义：设是无向连通图，是的生成子图，若是树，16例4、上图中，(2)是(1)的生成树，(3)是(2)的余树。注意：(1)生成树不唯一，(2)余树不一定是树。例4、上图中，(2)是(1)的生成树，(3)是(2)的余树。172、连通图的性质。设为连通图，，，(1)至少有一棵生成树，(2)，(3)设是的生成树，是的余树，则中有条边。已知连通图，求其生成树步骤。2、连通图的性质。设为连通图，，，(1)至少有一棵生成树，(183、最小生成树。对于有向图或无向图的每条边附加一个实数，则称为边上的权，连同附加在各边上的实数称为带权图，记为。最小生成树——各边权和最小的生成树。定义：设无向连通带权图，是的一棵生成树，各边带权之和称为的权，记作。3、最小生成树。对于有向图或无向图的每条边附加一个实数，则称19求最小生成树的方法——避圈法。设阶无向连通带权图中有条边，它们带的权分别为，不妨设，(1)取在中

(非环，若为环，则弃)。(2)若不与构成回路，取在中，否则弃，再查，继续这一过程，直到形成树为止。求最小生成树的方法——避圈法。设阶无向连通带权图中有条边，它20解：例5、求以下连通图的最小生成树及。解：例5、求以下连通图的最小生成树及。21解：例5、求以下连通图的最小生成树及。解：例5、求以下连通图的最小生成树及。22解：例5、求以下连通图的最小生成树及。解：例5、求以下连通图的最小生成树及。23解：例5、求以下连通图的最小生成树及。解：例5、求以下连通图的最小生成树及。24注意：的最小生成树可能不唯一，但的不同最小生成树权的值一样。注意：的最小生成树可能不唯一，但的不同最小生成树权的值一样。25第二节

根树及其应用第二节根树及其应用26内容：有向树，根树，最优二元树。重点：1、有向树及根树的定义，2、家族树，有序树，元树的概念，3、最优2元树的概念及哈夫曼算法。内容：有向树，根树，最优二元树。重点：1、有向树及根树的定义27一、根树。1、有向树：一个有向图，若略去有向边的方向所得的无向图为一棵无向树，则称为有向树。2、根树：一棵非平凡的有向树，如果有一个顶点的入度为0，其余顶点的入度均为1，则称此有向树为根树。一、根树。1、有向树：一个有向图，若略去有向边的方向所得的无28根树的顶点树叶(入度为1，出度为0)分支点树根(入度为0)内点(入度为1，出度大于0)根树的顶点树叶(入度为1，出度为0)分支点树根(入度为0)内29例1、例1、30例1、例1、313、树高。的层数——从树根到顶点的通路长度，记。树高——树中顶点的最大层数，记。3、树高。的层数——从树根到顶点的通路长度，记。树高——树中32如例1(2)中，如例1(2)中，334、家族树。一棵根树可以看成一棵家族树。(1)若顶点邻接到顶点，则称为的儿子，为的父亲，(2)若同为的儿子，则称为兄弟，(3)若，而可达，则称为的祖先，为的后代。4、家族树。一棵根树可以看成一棵家族树。(1)若顶点邻接到345、根子树。树的根子树——的非树根的顶点及其后代导出的子图。5、根子树。树的根子树——的非树根的顶点及其后代导出的子图。35例2、例2、36二、元树。1、有序树——每一层上都规定次序的根树。2、元树——每个分支点至多有个儿子的根树。元正则树——每个分支点恰有个儿子的根树。元有序树元有序正则树二、元树。1、有序树——每一层上都规定次序的根树。2、元树—37二、元树。元有序完全正则树注意：2元有序正则树是最重要的一种元树。1、有序树——每一层上都规定次序的根树。2、元完全正则树的层数相同

(等于树高)。——元正则树，且所有树叶二、元树。元有序完全正则树注意：2元有序正则树是最重要的一种38例3、2元有序树2元有序正则树例3、2元有序树2元有序正则树39例3、2元有序完全正则树例3、2元有序完全正则树40三、树的遍历。1、前序遍历——根，左，右。2、中序遍历——左，根，右。3、后序遍历——左，右，根。三、树的遍历。1、前序遍历——根，左，右。2、中序遍历——左413、最优2元树。(1)的权最优2元树——权最小的2元树。——中每片树叶所带权与其层高乘积的和。记为3、最优2元树。(1)的权最优2元树——权最小的2元树。——42例4、下图中的都是带权1，3，4，5，6的2元树，求，，。解：例4、下图中的都是带权1，3，4，5，6的2元树，求，，。解43例4、下图中的都是带权1，3，4，5，6的2元树，求，，。解：例4、下图中的都是带权1，3，4，5，6的2元树，求，，。解44例4、下图中的都是带权1，3，4，5，6的2元树，求，，。解：但不能判定是最优2元树。例4、下图中的都是带权1，3，4，5，6的2元树，求，，。解45(2)求最优2元树的算法。算法：给定实数片树叶的权)，且(，选连接得一分支点，从中选两个最小的，连接得一分支点，重复。(2)求最优2元树的算法。算法：给定实数片树叶的权)，且(46例5、求带权1,3,4,5,6的最优2元树及。解：其实等于的各分支点的权之和，即例5、求带权1,3,4,5,6的最优2元树及。解：其47例5、求带权1,3,4,5,6的最优2元树及。解：其实等于的各分支点的权之和，即最优树是不唯一的，但算法得到的树一定是最优树。例5、求带权1,3,4,5,6的最优2元树及。解：其48例6、(1)求带权为2,3,5,7,8,9的最优2元树，解：(2)例6、(1)求带权为2,3,5,7,8,9的最优49例6、(1)求带权为2,3,5,7,8,9的最2优元树，解：(3)例6、(1)求带权为2,3,5,7,8,9的最250例6、(1)求带权为2,3,5,7,8,9的最2优元树，解：(4)有___片树叶。例6、(1)求带权为2,3,5,7,8,9的最251例6、(1)求带权为2,3,5,7,8,9的最2优元树，解：(5)有__个2度顶点，__个3度顶点，__个4度顶点。例6、(1)求带权为2,3,5,7,8,9的最2524、求最佳前缀码。(了解)最优2元树的用途之一是求最佳前缀码。在通讯中，我们常用0和1的符号串作为英文字母的传送信息，26个英文字母被使用的频率往往是不同的。为了使整个信息的长度尽可能短，自然希望用较短的符号串去表示使用频率高的英文字母，用较长的符号串表示使用频率低的英文字母。

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

最优2元树的算法解决这个问题。4、求最佳前缀码。(了解)最优元树的用途之一是求最佳前缀码。54第九章

小结与例题第九章小结与例题55一、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林；平凡树；生成树，最小生成树。2、运用。(1)无向树的六个等价定义。(2)画顶点数为的所有非同构的无向树。一、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林56一、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林；平凡树；生成树，最小生成树。2、运用。(3)根据握手定理及树的某些性质，求顶点数或某些顶点的度数。(4)求生成树，最小生成树。一、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林57二、根树及其应用。1、基本概念。有向树；根树；树根，内点，树叶，分支点；顶点的层数与树高；有序树，正则树，完全树；最优二元树。二、根树及其应用。1、基本概念。有向树；根树；树根，内点，树58二、根树及其应用。2、运用。(1)按定义画出等等。元树，元正则树，元有序树(2)利用算法求最优二元树。二、根树及其应用。2、运用。(1)按定义画出等等。元树，元59例1、画出满足下列要求的所有非同构的无向树。(1)2个顶点(2)3个顶点(3)4个顶点例1、画出满足下列要求的所有非同构的无向树。(1)2个顶点60例1、画出满足下列要求的所有非同构的无向树。(4)5个顶点例1、画出满足下列要求的所有非同构的无向树。(4)5个顶点61例2、若无向图中有个顶点，条边，则为树。这个命题正确吗？解：命题不正确。反例：例2、若无向图中有个顶点，条边，则为树。这个命题正确吗？解：62例3、设连通图如下图所示，分别求出它们的所有非同构的生成树。解：的生成树有：例3、设连通图如下图所示，分别求出它们的所有非同构的生成树。63例3、设连通图如下图所示，分别求出它们的所有非同构的生成树。解：的生成树有：例3、设连通图如下图所示，分别求出它们的所有非同构的生成树。64例4、一棵树有个顶点的度数为2，个顶点的