高等学校计算机专业教材：《离散数学》课程PPT课件_第九章 树与平面图

第九章村与平面图 努是较￥第是用 是很好掉好类经 取 问次等 资的軻舒国为 返回首页 2021/1/21

2021/1/21 1 第九章 树与平面图 树是一类结构较为简单的图，是用途极 为广泛的离散数学模型，特别是二叉树， 它在计算机科学中用得最多.因此在学习 时应很好地掌握好诸如树的充要条件、 生成树、最优生成树、根树、树的各种 算法、及二叉树的访问次序等内容.平面 图是实际背景很强的一类图，能用本章 介绍的方法判断一个图是否为平面图. 返回首页

第一节树的概念 ●本节介绍树的一些最基本的概念与结论. 1概念有树树叶分支点或内点森林平 凡树等 2结论:设G是n阶无向图,则下列条件等 (1)G是树;(2)G连通并且删去G的 边,所得之图都不连通(3)对G 的意点 u,(U),恰有一条从u到v 简单路;(4)G不含回路,直G有n-1 条迈;5)G连通,且G有n-1条边 返回本章首页 2021/1/21

2021/1/21 2 第一节 树的概念 ⚫ 本节介绍树的一些最基本的概念与结论. 1.概念有:树,树叶,分支点(或内点),森林,平 凡树等 2.结论: 设G是n阶无向图，则下列条件等 价： （1）G是树；(2）G连通并且删去G的任 一边，所得之图都不连通；(3）对G中 的任意两点u,v(u≠v)，恰有一条从u到v 的简单路；(4）G不含回路，且G有n-1 条边；(5）G连通，且G有n-1条边. 返回本章首页

第二节生成树与最优支撑树 ●本节讨论连通图的生成树与连通权图的 最优生成树叵称为最优支撑树 1基本概念生成树余树树枝最优(小生 成树等; 2定理:图G有生成树当且仅当G是连通的 3.算法:(1)无向连通图可采用破坏回路与 不形成回路两种方法寻找生成树 2权图中求最优生成树的两种算法即克 鲁斯卡尔算法与管梅谷的破阔法 3 返回本章首页 2021/1/21

2021/1/21 3 第二节 生成树与最优支撑树 ⚫ 本节讨论连通图的生成树与连通权图的 最优生成树(或称为最优支撑树). 1.基本概念:生成树,余树,树枝,最优(小)生 成树等; 2.定理:图G有生成树当且仅当G是连通的； 3.算法:(1)无向连通图可采用破坏回路与 不形成回路两种方法寻找生成树； (2)权图中求最优生成树的两种算法,即克 鲁斯卡尔算法与管梅谷的破圈法. 返回本章首页

第三节有向树与根树(1) 有向树是有向图中结构最为简单的一类 是种典型的续性结构在计 算机算法分析、数据结构等方面有广泛 我们生要号晨粉中,根树最为量要 1概念有向树根树树址肉点分支点层 树高祖先后代父亲儿子兄弟有序 又树完全m议树粮子树左子树右 子树带权二叉树最优二文树前绫前缀 码二元前缀码二叉树遍历等 返回本章首页 2021/1/21

2021/1/21 4 第三节 有向树与根树(1) ⚫ 有向树是有向图中结构最为简单的一类 图. 它是一种典型的非线性结构，在计 算机算法分析、数据结构等方面有广泛 的应用；在有向树中，根树最为重要， 我们主要考虑根树. 1.概念:有向树,根树,树叶,内点,分支点,层 数,树高,祖先,后代,父亲,儿子,兄弟,有序 树,m叉树,完全m叉树,根子树,左子树,右 子树,带权二叉树,最优二叉树,前缀,前缀 码,二元前缀码,二叉树遍历等; 返回本章首页

第三节有向树与根树(2 2定理:设T是一棵根树,「是T的树根则对 于T的任顶点存在唯的有向路从r 到 3算法最优二叉树的 Huffman算法 4前缀码问题前缀码与二叉树的对应关系; 5.二叉树的遍历:三种遍历方法即先根遍 历,中根遍历,后根遍历法 5 返回本章首页 2021/1/21

2021/1/21 5 第三节 有向树与根树(2) 2.定理: 设T是一棵根树，r是T的树根,则对 于T的任一顶点v,存在唯一的有向路从r 到v； 3.算法:最优二叉树的Huffman算法; 4.前缀码问题:前缀码与二叉树的对应关系； 5.二叉树的遍历:三种遍历方法,即先根遍 历,中根遍历,后根遍历法. 返回本章首页

第四节平面图 平面图是很多实际问题的模型例如在 集成电路的布线设计中就遇到了平面图 的问题 1基本概念平面图平面嵌入,面无限面(外 部面),内部面边界次数等; 2基本非平面图K32与Ks; 3平面图的欧拉公式; 4.平面图的判定库拉图斯基定理 6 返回本章首页 2021/1/21

2021/1/21 6 第四节 平面图 ⚫ 平面图是很多实际问题的模型. 例如在 集成电路的布线设计中就遇到了平面图 的问题. 1.基本概念:平面图,平面嵌入,面,无限面(外 部面),内部面,边界,次数等; 2.基本非平面图:K3,3与K5； 3.平面图的欧拉公式； 4.平面图的判定:库拉图斯基定理. 返回本章首页

本章小结 ●本章我们介绍树与平面图,但以介绍树 为主给出树的定义及树的充要条件,生 成树、最优生成树及最优生成树的克鲁 斯卡尔算法,特别是二叉树,我们讨论 了二叉树的 Huffman算法、前缀码、 叉树的遍历等问题最后介绍了一类实际 肯景很强的一类图平面图 返回本章首页 2021/1/21

2021/1/21 7 本章小结 ⚫ 本章我们介绍树与平面图，但以介绍树 为主.给出树的定义及树的充要条件，生 成树、最优生成树及最优生成树的克鲁 斯卡尔算法，特别是二叉树，我们讨论 了二叉树的Huffman算法、前缀码、二 叉树的遍历等问题.最后介绍了一类实际 背景很强的一类图——平面图. 返回本章首页