当前位置:首页 >> 高中教育 >> 图论 (6)

图论 (6)


杨春
Email:yc517922@126.com
2013年7月10日星期三

10.3

根树

定义10.3.1 一个有向图,若略去所有有向边的 方向所得到的无向图是一棵树,则称这个有向 图为有向树。 例1 在下图中,图a~图d所示的有向图均为有 向树。在有向树中,我们主要讨论像图b、图c 所

示的有向树,它们均称为根树。

2013-7-10

数学学院

49--2

根树
定义10.3.2 一棵非平凡的有向树,如果 恰有一个结点的入度为0,其余所有结点的 入度均为1,则称为根树或外向树。入度为 0的结点称为树根;出度为0的结点称为 树叶;入度为1,出度大于0的结点称为内 点;又将内点同树根统称为分支点。

2013-7-10

数学学院

49--3

倒置法 层数、高

? 倒置法:把树根画在最上方,树叶画在下方, 在根树中,从树根到任一结点v的通路长度, 有向边的方向均指向下方,这样就可以省去全 称为该结点的层数;称层数相同的结点在同一层 部箭头,不会发生误解。 上;所有结点的层数中最大的称为根树的高。
2013-7-10 数学学院 49--4

有序树、子树
? 定义10.3.3 在根树中,若从vi 到vj 可达,则 称vi 是vj 的祖先,vj 是vi 的后代;又若<vi,vj> 是根树中的有向边,则称vi 是vj 的父亲,vj 是 vi的儿子;如果两个结点是同一个结点的儿子, 则称这两个结点是兄弟。 ? 定义10.3.4 如果在根树中规定了每一层上结 点的次序,这样的根树称为有序树。 ? 在有序树中同一层中结点的次序为从左至右。 有时也可以用边的次序来代替结点的次序。 ? 定义10.3.5 在根树T中,任一结点v及其所有 后代导出的子图T'称为T的以v为树根的子树。
2013-7-10 数学学院 49--5

m元树
定义10.3.6 在根树T中,若每个分支点至多 有m个儿子,则称T为m元树;若每个分支点都恰 有m个儿子,则称T为m元完全树;若m元树T是有 序的,则称T为m元有序树;若m元完全树T是有序 的,则称T为m元有序完全树。二元有序树的每个 结点v至多有两个儿子,分别称为v的左儿子和右 儿子。二元有序树的每个结点 v 至多有两棵 子 树,分别称为v的左子树和右子树。
注意区分以v为树根的子树和v的左(右)子 树,v为树根的子树包含v,而v的左(右)子树 不包含v。
2013-7-10 数学学院 49--6

例2

三元树

三元 有序树

三元 完全树

三元有序 完全树

2013-7-10

数学学院

49--7

定理10.3.1
在m元完全树中,若树叶数为t,分支点数为 i,则下式成立: (m-1)i=t-1 证明 由假设知,该树有i+t个结点。 ? 由定理13.6知,该树的边数为i+t-1。 ? 因为所有结点的出度之和等于边数,所以根据 m元完全树的定义知,有 m×i=i+t-1 ? 即 (m-1)i=t-1
2013-7-10 数学学院 49--8

例3
假设有一台计算机,它有一条加法指令,可 计算3个数的和。如果要求9个数x1,x2,x3,x4,x5,

x6,x7,x8,x9之和,问至少要执行几次加法指令?
解 用3个结点表示3个数,将表示3个数之和的 结点作为它们的父结点。这样本问题可理解为 求一个三元完全树的分支点问题。把9个数看 成树叶。由定理13.9知,有(3-1)i = 9-1,得 i = 4。所以至少要执行4次加法指令。
2013-7-10 数学学院 49--9

把有序树转换为二元树
1) 从根开始,保留每个父亲同其最左边儿子的 连线,撤销与别的儿子的连线。 2) 兄弟间用从左向右的有向边连接。 3) 按如下方法确定二元树中结点的左儿子和右 儿子:直接位于给定结点下面的结点,作为 左儿子,对于同一水平线上与给定结点右邻 的结点,作为右儿子,依此类推。 ? 反过来,我们也可以将二元树还原为有序树。
2013-7-10 数学学院 49--10

例4
将下图a转化为一棵二元树。

2013-7-10

数学学院

49--11

把森林转换为二元树
1) 先把森林中的每一棵树都表示成二元树。 2) 除第一棵二元树外,依次将剩下的每棵二元 树作为左边二元树的根的右子树,直到所有 的二元树都连成一棵二元树为止。

? 反过来,我们也可以将二元树还原为森林。
2013-7-10 数学学院 49--12

例5
将下图a所示的森林转化成一棵二元树。

2013-7-10

数学学院

49--13

二元树的遍历
1. 先根次序遍历法: 1) 访问根; 2) 按先根次序遍历根的左子树; 3) 按先根次序遍历根的右子树。 2. 中根次序遍历法: 1) 按中根次序遍历根的左子树; 2) 访问根; 3) 按中根次序遍历根的右子树。 3. 后根次序遍历法: 1) 按后根次序遍历根的左子树; 2) 按后根次序遍历根的右子树; 3) 访问根。
2013-7-10 数学学院 49--14

例6
对右图中的二元
树,写出3种遍历方 法得到的结果。



先根遍历次序为v1v2v4v6v7v3v5v8v9v10v11v12;

中根遍历次序为v6v4v7v2v1v8v5v11v10v12v9v3;
后根遍历次序为v6v7v4v2v8v11v12v10v9v5v3v1。
2013-7-10 数学学院 49--15

对一般树的遍历
? 先根次序遍历 ? 后根次序遍历 ? 图a的先根次序遍历的结果为: v1v2v5v6v3v4v7v9v10v11v8; ? 图c的先根次序遍历的结果为: v1v2v5v6v3v4v7v9v10v11v8; ? 图a的后根次序遍历的结果为: v5v6v2v3v9v10v11v7v8v4v1; ? 图c的中根次序遍历的结果为: v5v6v2v3v9v10v11v7v8v4v1。 ? 树的先根次序正是相应二元树的先根次序; ? 树的后根次序正是相应二元树的中根次序。
2013-7-10 数学学院 49--16

最优树
定义10.3.6 设有一棵二元树,若对其所有的 t片树叶赋以权值W1、W2、…、Wt,则称之为赋权 二元树;若权为Wi的树叶的层数为L(Wi),则称

W(T) =

? Wi ? L(Wi )
i=1

t

为该赋权二元树的权;而在所有赋权W1 、W2 、…、 Wt的二元树中,W(T)最小的二元树称为最优树。

2013-7-10

数学学院

49--17

最优树的应用
? 最优树问题源于计算机科学、生产管理等领域。 ? 举一个简单的例子,用机器分辨一些币值为1 分、2分、5分的硬币,假设各种硬币出现的概 率分别为0.5、0.4、0.1。问如何设计一个分 辨硬币的算法,使所需的时间最少(假设每作 一次判别所用的时间相同,以此为一个时间单 位)? ? 这个问题就是构造一个有3片树叶的最优树问 题。
2013-7-10 数学学院 49--18

哈夫曼算法
假设W1≤W2≤…≤Wt。1952年哈夫曼给出了求 最优树的方法。该方法的关键是:从带权为W1+W2、 W 3 、…、W t 的最优树T'中得到带权为W 1 、W 2 、…、 Wt的最优树。 算法的具体步骤如下: 1) 初始:令S={W1,W2,…,Wt}; 2) 从S中取出两个最小的权Wi 和Wj ,画结点vi , 带权Wi,画结点vj,带权Wj。画vi和vj的父亲v, 连接vi和v,vj和v,令v带权Wi+Wj; 3) 令S=(S-{Wi,Wj})∪{Wi+Wj}; 4) 判断S是否只含一个元素?若是,则停止,否 则转2)。
2013-7-10 数学学院 49--19

分辨硬币的算法
? 实际上该问题归结为求带权0.1、0.4、0.5的 最优树问题; ? 利用哈夫曼算法,答案的图示见图a或图b。所 需时间为 2×0.1+2×0.4+1×0.5=1.5

2013-7-10

数学学院

49--20

例7
求带权7、8、9、12、16的最优树。 解 全部过程见下图a~图d。

2013-7-10

数学学院

49--21


更多相关文档:

图论第六次作业答案

图论次作业答案 5.28 设 sn 是满足下列条件的最小整数:把{1,2…. sn}任划分成 n 个子集后,总有一个子集中含方程 x+y=z 的根,求 s1,s2,s3 是...

第六章 图论

图论_管理学_高等教育_教育专区。介绍运筹学中的图论图论 §8.1 图论发展史第一阶段:瑞士数学家欧拉(E. Euler)在 1736 年发表了一篇题为“依...

离散数学习题解答第6部分(图论)

离散数学习题解答 习题 (图论) 1. 从日常生活中列举出三个例子, 并由这些例子自然地导出两个无向图及一个向图。 [解] ①用 V 代表全国城市的...

4~离散数学习题解答习题六(第六章 图论)6

4~离散数学习题解答习题六(图论)6_理学_高等教育_教育专区。西交版 离散数学答案4离散数学习题解答 习题 (图论) 1.从日常生活中列举出三个...

数学建模作业实验6图论组合优化实验

数学建模作业 (实验 6 图论(组合优化)实验) 基本实验 1.设备更新问题某公司需要对一台已经使用了 2 年的机器确定今后 4 年(n=4)的最优更新策略.公司要求, ...

图论部分自测题答案13-12-6

图论部分自测题答案: 1、 选择题 1) 7) 1 1 2) 2 8) 2 13) 4 18) 1 23) 1 28) 3 33) 2 3) 3 4) 2 5) 3 6) 11)1 16)2 21) 2 ...

离散数学习题解答习题六 (第六章 图论)

离散数学习题解答 习题 (图论) 1. 从日常生活中列举出三个例子, 并由这些例子自然地导出两个无向图及一个向图。 [解] ①用 V 代表全国城市的...

图论基础知识

图论基础知识_数学_自然科学_专业资料。图论基本知识对于网络的研究,最早是从数学...图 a 是 10 阶有向图,顶点集为 {1,2,3,4,5,6,7,8,9,10} ,边集...

北京工业大学-数学建模6-图论(组合优化)实验201311

北京工业大学-数学建模6-图论(组合优化)实验201311_数学_自然科学_专业资料。图论(组合优化)实验作业一、 基本实验 1.设备更新问题 某公司需要对一台已经使用了 2...

图论复习题(中文)

图论习题 9页 免费图​论​复​习​题​(​中​文​) ...树图 6、割边 7、割点 8、关联矩阵 9、邻接矩阵 10、连通度 11、完全图 ...
更多相关标签:
图论算法 | 图论导引 | 图论及其算法 | 图论论文 | 图论及其应用 | 图论与代数结构 | 集合论与图论 | 图论教程 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com