《离散数学第九章ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学第九章ppt课件.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第九章第九章 树树第一节第一节 无向树及生成树无向树及生成树 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物内容：内容：无向树，生成树。重点：重点：1、无向树的定义 (包括等价定义)，2、无向树的性质，3、生成树的定义，由连通图构造最小生成树的方法。本章中所谈回路均指简单回路或初级回路。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也
2、感到愉快，证实我的猜测没有错：表里边有一个活的生物一、无向树。一、无向树。1、无向树无向树 连通且不含回路的无向图。无向树简称树，常用表示。T平凡树平凡树 平凡图。森林森林 连通分支数大于等于2，且每个连通分支都是树的无向图。T树叶度数为1的顶点树 的顶点分支点度数大于1的顶点我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例1、(1)fceadb(2)我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物(3)例例1、(4
3、)我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物2、树的六个等价定义。(1)连通且不含回路。G(2)的每对顶点间具有唯一的路径。G(3)连通且G1nm。(4)无回路且G1nm。定理：定理：设,GV EVnEm，则以下命题等价。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物2、树的六个等价定义。(5)无回路，但在G中任两个不相邻的顶点G之间增加一条边，就形成唯一的一条初级回路。(6)是连通的，但删除任何一条边后，就不G
4、连通了。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3、性质性质。(1) 树中顶点数与边数的关系：1nm。(2) 定理定理：非平凡树至少2片树叶。证明：证明：设为阶非平凡树，,TV En设有 片树叶，则有Tk个顶点度数大于等()nk于2，12( )2()niimd vknk由握手定理，又由(1)1mn，代入上式，解得2k ，即至少2片叶。T我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例2、画出所有的6个顶点的非
5、同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(1)1 1 1 1 151T我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例2、画出所有的6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(2)1 1 1 1242T我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例2、画出所有的6个顶
6、点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(3)1 1 1 1333T我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例2、画出所有的6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(4)1 1 12234T5T我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例2、画出所有的
7、6个顶点的非同构的树。解：解：所要画的树有6个顶点，则边数为5，因此6个顶点的度数之和为10，可以产生以下五种度数序列：(5)1 122226T我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例3、(1) 一棵树有7片叶，3个3度顶点，其余都是4度顶点，求4度顶点多少个？解：解：设有 个4度顶点，则顶点数x73x ，边数731x，由握手定理，43 372(731)xx ，解得1x ，故这棵树有1个4度顶点。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实
8、我的猜测没有错：表里边有一个活的生物例例3、(2) 一棵树有2个4度顶点，3个3度顶点，其余都是树叶，求这棵树共有多少个顶点？解：解：设有 片树叶，则顶点数x23x ，边数231x，由握手定理，243 32(231)xx ，解得9x ，故顶点总数为23914 个。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物二、生成树。二、生成树。1、定义：定义：设是无向连通图，,GV ET是G的生成子图，若T是树，称T是G的生成树。树枝树枝弦弦余树余树GT在中的边，GT不在中的边，T的所有的弦的集合的导出子图。我吓了一
9、跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例4、(3)(2)(1)上图中，(2)是(1)的生成树，(3)是(2)的余树。注意：注意：(1) 生成树不唯一，(2) 余树不一定是树。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物2、连通图的性质连通图的性质。设,GV E为连通图，Vn，Em，(1)至少有一棵生成树，G(2)1mn，(3) 设是TG的生成树，T是T的余树，则T中有1mn条边。已知连通图，求其生成树步骤。G我吓
10、了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3、最小生成树。对于有向图或无向图的每条边附加一个实数G( )w e，则称( )w e为边e上的权权，G连同附加在各边上的实数称为带权图带权图，记为,GV E W。最小生成树最小生成树 各边权和最小的生成树。定义：定义：设无向连通带权图,GV E W，T是G的一棵生成树，T各边带权之和称为T的权，记作( )W T。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物求最小生成树的方
11、法Kruskal避圈法避圈法。设阶无向连通带权图n,GV E W中有m条边12,me ee，它们带的权分别为12,ma aa，不妨设12maaa，(1) 取1e在T中 (非环，若1e为环，则弃1e)。(2) 若不与2e1e构成回路，取2e在T中，否则弃2e，再查3e，继续这一过程，直到形成树为止。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物cdefba解：解：1T例例5、求以下连通图的最小生成树及T( )W T。(1)6643215555fabcde123541( )15W T我吓了一跳，蝎子是多么丑恶
12、和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物54321bcdefa解：解：1T例例5、求以下连通图的最小生成树及T( )W T。(1)6643215555fabcde1()15( )W TW T我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物fedcba解：解：2T例例5、求以下连通图的最小生成树及T( )W T。(2)987764321105abcdef123572()18W T我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个
13、美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物75321fedcba解：解：2T例例5、求以下连通图的最小生成树及T( )W T。(2)987764321105abcdef2()18( )W TW T我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物注意：注意：的最小生成树可能不唯一，G但G的不同最小生成树权的值一样。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第二节第二节 根树及其应用根树
14、及其应用我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物内容：内容：有向树，根树，最优二元树。重点：重点：1、有向树及根树的定义，2、家族树，有序树， 元树的概念，r3、最优2元树的概念及哈夫曼()Huffman算法。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物一、根树。一、根树。1、有向树有向树：一个有向图，若略去有向边的D方向所得的无向图为一棵无向树，则称D为有向树有向树。2、根树根树：一棵非平凡的有向树，如果有
15、一个顶点的入度为0，其余顶点的入度均为1，则称此有向树为根树根树。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物根树的顶点树叶(入度为1，出度为0)分支点树根(入度为0)内点(入度为1，出度大于0)我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例1、我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例1、我吓了一跳，蝎子是多么丑
16、恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3、树高。的层数的层数v从树根到顶点v的通路长度，记( )l v。树高树高 树中顶点的最大层数，记( )h T。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物如例1(2)中，我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物4、家族树。一棵根树可以看成一棵家族树家族树。(1) 若顶点 邻接到顶点，则称为abba
17、的儿子，为ab的父亲，(2) 若a, b c同为 的儿子，则称, b c为兄弟兄弟，(3) 若ad，而 可达a，则称da为d的祖先祖先，d为a的后代后代。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物5、根子树。树的根子树根子树TT的非树根的顶点a及其后代导出的子图。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物T8v7v6v5v4v3v2v1v例例2、3vT8v7v6v5v4v我吓了一跳，蝎子是多么丑恶和恐怖的东西
18、，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物二、二、 元树。元树。r1、有序树有序树 每一层上都规定次序的根树。2、 元树元树r每个分支点至多有 个儿子的根树。rr元正则树元正则树 每个分支点恰有 个儿子的根树。rr元有序树元有序树r元有序正则树元有序正则树我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物二、二、 元树。元树。rr元有序完全正则树元有序完全正则树注意：注意：2元有序正则树是最重要的一种r元树。1、有序树有序树 每一层上都规定次序的根树。2
19、、r元完全正则树元完全正则树的层数相同 (等于树高)。元正则树，且所有树叶r我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例3、(1)22111(2)2221112元有序树2元有序正则树我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物(3)222111例例3、2元有序完全正则树我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物三、三
20、、树的遍历。树的遍历。1、前序遍历前序遍历 根，左，右。2、中序遍历中序遍历左，根，右。3、后序遍历后序遍历左，右，根。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3、最优2元树。(1)的权权T最优最优2元树元树 权最小的2元树。中每片树叶所带权与其层高T乘积的和。记为1( )()tiiiW Tw L w我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例4、下图中的都是带权1，3，4，5，6123,T T T的2元
21、树，求1( )W T，2()W T3()W T，。654311T解：解：1( )(63) 3(45 1)247W T 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例4、下图中的都是带权1，3，4，5，6123,T T T的2元树，求1( )W T，2()W T3()W T，。解：解：2()(16)45 34 23 154W T 2T65431我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例4、下图中的都是带权1
22、，3，4，5，6123,T T T的2元树，求1( )W T，2()W T3()W T，。解：解：3()(1 3) 3(645) 242W T 3T65431312()( )()W TW TW T但不能判定3T是最优2元树。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物(2) 求最优2元树的算法。Huffman算法：给定实数12,tw ww片树叶的权)，且t(12twww，( )a选12,w w连接得一分支点，( )b123,tww ww从中选两个最小的，连接得一分支点，( )c重复( )b。我吓了一跳，
23、蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例5、求带权1, 3, 4, 5, 6的最优2元树及T( )W T。34184116519解：解：( )(1 3) 3(456)242W T 其实( )W T等于T的各分支点的权之和，即( )48 11 19W T 42我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例5、求带权1, 3, 4, 5, 6的最优2元树及T( )W T。34184116519解：解：其实( )W T等
24、于T的各分支点的权之和，即( )48 11 19W T 42最优树是不唯一的，但Huffman算法得到的树一定是最优树。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例6、(1) 求带权为2, 3, 5, 7, 8, 9的最优2元树T，532105199158734解：解：( )_W T (2)5 1019153483我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例6、(1) 求带权为2, 3, 5, 7, 8,
25、 9的最2优元树T，532105199158734解：解：(3)( )_h T 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
26、)T有_个2度顶点，_个3度顶点，_个4度顶点。140我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物4、求最佳前缀码。(了解)最优2元树的用途之一是求最佳前缀码。在通讯中，我们常用0和1的符号串作为英文字母的传送信息，26个英文字母被使用的频率往往是不同的。为了使整个信息的长度尽可能短，自然希望用较短的符号串去表示使用频率高的英文字母，用较长的符号串表示使用频率低的英文字母。 我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活
27、的生物4、求最佳前缀码。(了解)最优元树的用途之一是求最佳前缀码。为了使编码在使用中既快速又准确，可以用求 最优2元树的Huffman算法解决这个问题。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物第九章第九章 小结与例题小结与例题我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物一、无向树及生成树。一、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林；平凡树；生成树，最小生成树。2、运用。(1) 无向树的六个等
28、价定义。(2) 画顶点数为6n 的所有非同构的无向树。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物一、无向树及生成树。一、无向树及生成树。1、基本概念。无向树；树叶，分支点；森林；平凡树；生成树，最小生成树。2、运用。(3) 根据握手定理及树的某些性质，求顶点数或某些顶点的度数。(4) 求生成树，最小生成树。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物二、根树及其应用。二、根树及其应用。1、基本概念。有向树；根树
29、；树根，内点，树叶，分支点；顶点的层数与树高；有序树，正则树，完全树；最优二元树。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物二、根树及其应用。二、根树及其应用。2、运用。(1) 按定义画出等等。r元树，r元正则树，r元有序树(2) 利用算法求最优二元树。Huffman我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例1、画出满足下列要求的所有非同构的无向树。(1) 2个顶点(2) 3个顶点(3) 4个顶点我吓了一
30、跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例1、画出满足下列要求的所有非同构的无向树。(4) 5个顶点我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例2、若无向图G中有n个顶点，条边，则1nG为树。这个命题正确吗？解：解：命题不正确。反例：我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例3、设连通图12,G G如下图所示，分别
31、求出它们的所有非同构的生成树。1G解：解：1G的生成树有：我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例3、设连通图12,G G如下图所示，分别求出它们的所有非同构的生成树。解：解：2G的生成树有：2G我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例4、一棵树有个顶点的度数为2，2n3n个顶点的度数为3，kn个顶点的度数为k，而其余的顶点都是树叶。求该树的树叶数。解：解：设有片树叶，1n依握手定理及树的性质1m
32、n，1231232321kknnnknmnnnnm得解得：1342(2)2knnnkn我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物解：解：不一定，反例：例例5、一个有向图，仅有一个顶点入度为0，D其余顶点的入度均为1， 一定是根树吗？D我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例6、设 为二元正则树， 为边数， 为树叶数。Tmt证明：，其中22mt2t 。证法一：证法一：设中顶点数为 ，分支点数为Tni，由二
33、元正则树的定义，知nit 2mi1mn由以上三个式子，得22mt。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例6、设 为二元正则树， 为边数， 为树叶数。Tmt证明：，其中22mt2t 。证法二：证法二：在二元正则树中，除树叶外，每个顶点的出度为2，除树根外，每个顶点的入度都为1，我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例6、设 为二元正则树， 为边数， 为树叶数。Tmt证明：，其中22mt2t 。证法
34、二：证法二：由握手定理知，1112( )( )( )nnniiiiiimd vdvdv2()1ntn321nt3(1)21mt所以，22mt。我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物例例7、求带权为0.5，1，2，3.5，4，5，6的最优 二元树，并求( )W T。1.510.53.5273.513654922解：解：( )(0.5 1) 5W T 2 43.5 3 (645)256我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物结 束 语课 程 结 束 ， 谢 谢 大 家 ！