离散数学第九章

第九章树第一节无向树及生成树内容：无向树，生成树。重点：1、无向树的定义(包括等价定义)，2、无向树的性质，3、生成树的定义，由连通图构造最小生成树的方法。本章中所谈回路均指简单回路或初级回路。一、无向树。1、无向树——连通且不含回路的无向图。无向树简称树，常用表示。T平凡树——平凡图。森林——连通分支数大于等于2，且每个连通分支都是树的无向图。T树叶——度数为1的顶点树的顶点分支点——度数大于1的顶点例1、(1)fceadb(2)(3)例1、(4)2、树的六个等价定义。(1)连通且不含回路。G(2)的每对顶点间具有唯一的路径。G(3)连通且G1nm。(4)无回路且G1nm。定理：设,GVEVnEm，，，则以下命题等价。2、树的六个等价定义。(5)无回路，但在G中任两个不相邻的顶点G之间增加一条边，就形成唯一的一条初级回路。(6)是连通的，但删除任何一条边后，就不G连通了。3、性质。(1)树中顶点数与边数的关系：1nm。(2)定理：非平凡树至少2片树叶。证明：设为阶非平凡树，,TVEn设有片树叶，则有Tk个顶点度数大于等()nk于2，12()2()niimdvknk由握手定理，又由(1)1mn，代入上式，解得2k，即至少2片叶。T例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(1)1111151T例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(2)1111242T例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(3)1111333T例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(4)1112234T5T例2、画出所有的6个顶点的非同构的树。解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(5)1122226T例3、(1)一棵树有7片叶，3个3度顶点，其余都是4度顶点，求4度顶点多少个？解：设有个4度顶点，则顶点数x73x，边数731x，由握手定理，43372(731)xx，解得1x，故这棵树有1个4度顶点。例3、(2)一棵树有2个4度顶点，3个3度顶点，其余都是树叶，求这棵树共有多少个顶点？解：设有片树叶，则顶点数x23x，边数231x，由握手定理，24332(231)xx，解得9x，故顶点总数为23914个。二、生成树。1、定义：设是无向连通图，,GVET是G的生成子图，若T是树，称T是G的生成树。树枝弦余树——GT在中的边，——GT不在中的边，——T的所有的弦的集合的导出子图。例4、(3)(2)(1)上图中，(2)是(1)的生成树，(3)是(2)的余树。注意：(1)生成树不唯一，(2)余树不一定是树。2、连通图的性质。设,GVE为连通图，Vn，Em，(1)至少有一棵生成树，G(2)1mn，(3)设是TG的生成树，'T是T的余树，则'T中有1mn条边。已知连通图，求其生成树步骤。G3、最小生成树。对于有向图或无向图的每条边附加一个实数G()we，则称()we为边e上的权，G连同附加在各边上的实数称为带权图，记为,,GVEW。最小生成树——各边权和最小的生成树。定义：设无向连通带权图,,GVEW，T是G的一棵生成树，T各边带权之和称为T的权，记作()WT。求最小生成树的方法Kruskal——避圈法。设阶无向连通带权图n,,GVEW中有m条边12,,,meee，它们带的权分别为12,,,maaa，不妨设12maaa，(1)取1e在T中(非环，若1e为环，则弃1e)。(2)若不与2e1e构成回路，取2e在T中，否则弃2e，再查3e，继续这一过程，直到形成树为止。cdefba解：1T例5、求以下连通图的最小生成树及T()WT。(1)6643215555fabcde123541()15WT54321bcdefa解：1'T例5、求以下连通图的最小生成树及T()WT。(1)6643215555fabcde1(')15()WTWTfedcba解：2T例5、求以下连通图的最小生成树及T()WT。(2)987764321105abcdef123572()18WT75321fedcba解：2'T例5、求以下连通图的最小生成树及T()WT。(2)987764321105abcdef2(')18()WTWT注意：的最小生成树可能不唯一，G但G的不同最小生成树权的值一样。第二节根树及其应用内容：有向树，根树，最优二元树。重点：1、有向树及根树的定义，2、家族树，有序树，元树的概念，r3、最优2元树的概念及哈夫曼()Huffman算法。一、根树。1、有向树：一个有向图，若略去有向边的D方向所得的无向图为一棵无向树，则称D为有向树。2、根树：一棵非平凡的有向树，如果有一个顶点的入度为0，其余顶点的入度均为1，则称此有向树为根树。根树的顶点树叶(入度为1，出度为0)分支点树根(入度为0)内点(入度为1，出度大于0)例1、例1、3、树高。的层数v——从树根到顶点v的通路长度，记()lv。树高——树中顶点的最大层数，记()hT。如例1(2)中，4、家族树。一棵根树可以看成一棵家族树。(1)若顶点邻接到顶点，则称为abba的儿子，为ab的父亲，(2)若a,bc同为的儿子，则称,bc为兄弟，(3)若ad，而可达a，则称da为d的祖先，d为a的后代。5、根子树。树的根子树T——T的非树根的顶点a及其后代导出的子图。T8v7v6v5v4v3v2v1v例2、3v'T8v7v6v5v4v二、元树。r1、有序树——每一层上都规定次序的根树。2、元树r——每个分支点至多有个儿子的根树。rr元正则树——每个分支点恰有个儿子的根树。rr元有序树r元有序正则树二、元树。rr元有序完全正则树注意：2元有序正则树是最重要的一种r元树。1、有序树——每一层上都规定次序的根树。2、r元完全正则树的层数相同(等于树高)。——元正则树，且所有树叶r例3、(1)22111(2)2221112元有序树2元有序正则树(3)222111例3、2元有序完全正则树三、树的遍历。1、前序遍历——根，左，右。2、中序遍历——左，根，右。3、后序遍历——左，右，根。3、最优2元树。(1)的权T最优2元树——权最小的2元树。——中每片树叶所带权与其层高T乘积的和。记为1()()tiiiWTwLw例4、下图中的都是带权1，3，4，5，6123,,TTT的2元树，求1()WT，2()WT3()WT，。654311T解：1()(63)3(451)247WT例4、下图中的都是带权1，3，4，5，6123,,TTT的2元树，求1()WT，2()WT3()WT，。解：2()(16)453423154WT2T65431例4、下图中的都是带权1，3，4，5，6123,,TTT的2元树，求1()WT，2()WT3()WT，。解：3()(13)3(645)242WT3T65431312()()()WTWTWT但不能判定3T是最优2元树。(2)求最优2元树的算法。Huffman算法：给定实数12,,t片树叶的权)，且t(12t，()a选12,ww连接得一分支点，()b123,,,t从中选两个最小的，连接得一分支点，()c重复()b。例5、求带权1,3,4,5,6的最优2元树及T()WT。34184116519解：()(13)3(456)242WT其实()WT等于T的各分支点的权之和，即()481119WT42例5、求带权1,3,4,5,6的最优2元树及T()WT。34184116519解：其实()WT等于T的各分支点的权之和，即()481119WT42最优树是不唯一的，但Huffman算法得到的树一定是最优树。例6、(1)求带权为2,3,5,7,8,9的最优2元树T，532105199158734解：()____________________WT(2)51019153483例6、(1)求带权为2,3,5,7,8,9的最2优元树T，532105199158734解：(3)()____hT4例6、(1)求带权为2,3,5,7,8,9的最2优元树T，532105199158734解：(4)T有___片树叶。6例6、(1)求带权为2,3,5,7,8,9的最2优元树T，532105199158734解：(5)T有__个2度顶点，__个3度顶点，__个4度顶点。1404、求最佳前缀码。(了解)最优2元树的用途之一是求最佳前缀码。在通讯中，我们常用0和1的符号串作为英文字母的传送信息，26个英文字母被使用的频率往往是不同的。为了使整个信息的长度尽可能短，自然希望用较短的符号串去表示使用频率高的英文字母，用较长的符号串表示使用频率低的英文字母。4、求最佳前缀码。(了解)最优元树的用途之一是求最佳前缀码。为了使编码在使用中既快速又准确，可以用求最优2元树的Huffman算法解决这个问题。第九章小结与例题一、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林；平凡树；生成树，最小生成树。2、运用。(1)无向树的六个等价定义。(2)画顶点数为6n的所有非同构的无向树。一、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林；平凡树；生成树，最小生成树。2、运用。(3)根据握手定理及树的某些性质，求顶点数或某些顶点的度数。(4)求生成树，最小生成树。二、根树及其应用。1、基本概念。有向树；根树；树根，内点，树叶，分支点；顶点的层数与树高；有序树，正则树，完全树；最优二元树。二、根树及其应用。2、运用。(1)按定义画出等等。r元树，r元正则树，r元有序树(2)利用算法求最优二元树。Huffman例1、画出满足下列要求的所有非同构的无向树。(1)2个顶点(2)3个顶点(3)4个顶点例1、画出满足下列要求的所有非同构的无向树。(4)5个顶点例2、若无向图G中有n个顶点，条边，则1nG为树。这个命题正确吗？解：命题不正确。反例：例3、设连通图12,GG如下图所示，分别求出它们的所有非同构的生成树。1G解：1G的生成树有：例3、设连通图12,GG如下图所示，分别求出它们的所有非同构的生成树。解：2G的生成树有：2G例4、一棵树有个顶点的度数为2，2n3n个顶点的度数为3，···，kn个顶点的度数为k，而其余的顶点都是树叶。求该树的树叶数。解：设有片树叶，1n依握手定理及树的性质1mn，1231232321kknnnknmnnnnm得解得：1342(2)2knnnkn解：不一定，反例：例5、一个有向图，仅有一个顶点入度为0，D其余顶点的入度均为1，一定是根树吗？D例6、设为二元正则树，为边数，为树叶数。Tmt证明：，其中22mt2t。证法一：设中顶点数为，分支点数为Tni，由二元正则树的定义，知nit2mi1mn由以上三个式子，得22mt。例6、设为二元正则树，为边数，为树叶数。Tmt证明：，其中22mt2t。证法二：在二元正则树中，除树叶外，每个顶点的出度为2，除树根外，每个顶点的入度都为1，例6、设为二元正则树，为边数，为树叶数。Tmt证明：，其中22mt2t。证法二：由握手定理知，1112()()()nnniiiiiimdvdvdv2()1ntn321nt3(1)21mt所以，22mt。例7、求带权为0.5，1，2，3.5，4，5，6的最优二元树，