图论树的应用ppt课件.ppt

《图论树的应用ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、作业问题：欧拉图的判定已经很完善，主要是关于哈密顿图的判定从哈密顿图的定义给定一个无向图G=(a)穿程图G中的每个结点一次且仅一次的通路，称为该图G的哈密顿通路(b)穿程图G中的每个结点一次且仅一次的回路，定义为该图G的哈密顿回路。(c)具有哈密顿回路的图。称为哈密顿图。具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图从定义可以得出哈密顿图G必须满足：1、每一个哈密顿图G都必定是个连通无向图2、G中的边数m必须大于等于n3、哈密顿通路是一条初级通路哈密顿回路是初级回路4、G中存在哈密顿回路，则一定存在哈密顿通路。反之不成立。8题根据这些特征来判断K2不满足2，

2、且回路不是初级回路，K2故不是哈密顿图16题：顶点分别为：v1,v2,…vnKn存在多少条不同的哈密顿回路？当起始点确定为v1时有（n-1）!当起始点不确定时有n!§16.3根树及其应用设D是有向图，若D的基图是无向树，则称D为有向树在所有的有向树中，根树最重要，所以在此只讨论根树一、根树1、定义：设T是n(n≥2)阶有向树若T中有一个顶点的入度为0，其余顶点的入度均为1，则称T为根树入度为0的顶点称为树根（相当于文件系统的盘符）入度为1出度为0的顶点称为树叶（具体文件）。入度为1出度不为0的顶点称为内点（文件夹），内点和树根统称为分支结点从树根到T的任意顶点v的通路(路

3、径)长度称为v的层数。层数最大顶点的层数称为树高．将平凡树也称为根树在根树中，由于各有向边的方向是一致的，所以画根树时可以省去各边上的所有箭头，并将树根画在最上方2、根树中顶点的关系定义：设T为一棵非平凡的根树，∀vi,vj∈V(T)，若vi可达vj，则称vi为vj的祖先，vj为vi的后代；若vi邻接到vj(即∈E(T)则称vi为vj的父亲，而vj为vi的儿子若vj,vk的父亲相同，则称vj与vk是兄弟3、有序树设T为根树，若将T中层数相同的顶点都标定次序，则称T为有序树根据根树T中每个分支点儿子数以及是否有序，可以将根树分成下列各类：(1)若T的每个分支点

4、至多有r个儿子，则称T为r叉树；又若r叉树是有序的，则称它为r叉有序树．(2)若T的每个分支点都恰好有r个儿子，则称T为r叉正则树；又若T是有序的，则称它为r叉正则有序树．(3)若T是r叉正则树，且每个树叶的层数均为树高，则称T为r叉完全正则树，又若T是有序的，则称它为r叉完全正则有序树。4、r叉树的子树定义：设T为一棵根树，∀v∈V(T)称v及其后代的导出子图Tv为T的以v为根的根子树如：2叉正则有序树的每个分支点的两个儿子导出的根子树分别称为左子树和右子树．二、根树的应用1、最优2叉树定义：设2叉树T有t片树叶v1，v2，…，vt，权分别为w1，w2，…，wt，称W(

5、T)＝∑wi

6、(vi)｜为T的权，其中

7、(vi)｜是vi的层数（也可以是从根到该叶子的通路长度）．在所有有t片树叶，带权w1，w2，…，wt的2叉树中，总权值权W(T)最小的2叉树称为最优2叉树三棵带权2叉树W(T1)＝2（2+2)+3*3+5*3+3*2＝38W(T2)＝4(3+5)+3*3+2*2+2＝47W(T3)＝3*(3+3)+5*2+2(2+2)＝36下面介绍一种算法：Huffman算法（在给定权值下，如何构造最优2叉树）给定实数(权值)：w1，w2，…，wt，按从小到大排序为w1≤w2≤…≤wt.(1)连接权为w1，w2的两片树叶，得一个分支点，其权为w1+

8、w2(2)在w1+w2，w3，w4…，wt中选出两个最小的权，连接它们对应的顶点(不一定是树叶)，得新分支点及所带的权．(3)重复(2)，直到形成t—1个分支点，t片树叶为止．例：给定一组权值3，5，6，9，11，14，16，18构造相应的最优二叉树最优二叉树总的原则是：权值较大的叶子距根较近，权值较小的可以距根较远2、前缀编码在通信中，常用二进制编码表示符号．1）等长编码与不等长编码：不等长编码可以使总电文总长度较短2）不等长编码中编码的问题：如何识别？3)前缀编码定义：设a1a2，…，an-1an为长为n的符号串，称其子串a1,a1a2,…，a1a2…an-1分别为该

9、符号串的长度为1，2，…，n-1的前缀．设A＝{b1，b2，…bm}为一个符号串集合，若对于任意的bi，bj∈A(i≠j)bi与bj互不为前缀，则称A为前缀码．若符号串bi(i＝1，2，…，m)中只出现0，1两个符号，则称A为二元前缀码{1，10，101，0101，1010，0100，01001}不是前缀码{1，00，011，0101，01001，01000}为前缀码．{1，01，111，1100，0111}不是前缀码2）利用二叉树产生二元前缀码规定二叉树的左子树的边为0，右子树的边为1则将从根到叶子结点的通路中边的序列即为叶