离散数学教学PPT作者刘贵龙第九章

《离散数学教学PPT作者刘贵龙第九章》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第九章树与平面图的人类是番得如、问一图套用嘉访的个好成藝一树很断构散鬻祝叉景判结离机埴取二北昙类鹼异好、及际方-、实的是£社应成法是绍树为它时生•本节介绍树的一些最基本旳概念与结论.1.概念有:树,树叶，分支点(或内点),森林，年凡树等2.结论：设G是n阶无向图，则下列条件等价：I22013-4-24(1)G是树；(2)G连通并且删去G的任一边，、所得之鹵却不连適；(3)对6中的任意两点U，V(UHV)，恰有一条从U到V的简单路；(4)G不含回路，且G有n-l条边；(5)G连通，且G有n-1条边.<返

2、回本章首页〉第二节生成树与最优支撑树•本节讨论连通图的生成树与连通权图的最优生成树（或称为最优支扌事褂）.1.基本概念:生成树，余树，树枝，最优（小）笙成树等；2•定理：图G有生成树当且仅当G是连通的;1.算法：⑴无向连通图可采用破坏回路与不形成回路两种方法寻找生歳树；（2）权图中求最优生成树的两种算法，即克鲁斯卡尔算痙与管梅谷百勺茂歯法.I32013-4-24第三节韦"向枢T与根树(1)•有向树是有向图中结构最为简单的一类鹵•它是一种典型阳罪线性结构，在讦算机算臺分析、数据结构等方面有广泛胡应角；在

3、有向树中，粮树最为重要，我们主要考虑根淑*1.概念:有向树，根树，树叶,內点、，分支点，屢数，树咼，祖芜j后代，父亲，丿匚孑?兄弟'有序树，m叉树，完全m文树，粮子树，左子树，右子树，带权二叉树，最优二叉树，前缀，前缀码，二元前缀码，二叉树遍历等；第三节有向树与根树(2)2•定理：设T是一棵根树，r是T的树根，则对于T的任一顶点V，存在唯一的有向路从I•到V；3.算法:最优二叉树的Huffman算法;4.前缀码问题:前缀码与二叉树的对应关系；5.二叉树的遍历：三种遍历方法，即先根遍历，中根遍历?后根遍

4、历法.第四节平面图•平面图是很多实际问题的模型.例如在集成电路的布线设计中就遇到了平面图的问题.1•基本概念:平面图，平面嵌入，面，无限面（外部面），内部面，边界，次数等；2•基本非平面图：％,3与％；3.平面图的欧拉公扎4•平面图的判定:库拉图斯基定理.返回本章首页I62013-4-24本章小结•本章我们介绍树与平面图，但以介绍树为主•给出树的定义及树的充要条件，生成树、最优生成树及最优生成树的克鲁斯卡尔算法，特另是二叉树，我们讨论了二叉树的Huffman算法、前缀码、二叉树的遍历等问题.最后介绍了

5、一类实际背景很强的一类图——平面图.■72013-4-24