离散数学第九章:树.ppt_第1页
离散数学第九章:树.ppt_第2页
离散数学第九章:树.ppt_第3页
离散数学第九章:树.ppt_第4页
离散数学第九章:树.ppt_第5页
已阅读5页,还剩25页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

9.1 9.1 无向树及生成树无向树及生成树 树:连通而不含回路的无向图称为无向树, 简称树,记作 T。 森林:连通分支数大于等于2,且每个连通 分支均是树的非连通无向图。 平凡树:平凡图为平凡树。 一、树的概念 森林 树叶: 树中度数为1的顶点 分支点: 树中度数2的顶点 树的性质: (1) G连通而不含回路; (2) 每对顶点之间具有唯一一条初级通路 (3) n = m+1 (4) 若在G中任意两个不相邻的顶点之间增加一 条边,就形成唯一一条初级回路。 (5) 连通且每条边都是桥 (6) 连通但删除任何一条边后就不连通 设G=是n阶m条边的无向树, 则下面各命题是等价的: 性质(7): 任一棵非平凡树 T = ,至少有 两片叶。 证明:设T有x片树叶,由握手定理及定理9.1知, 由上式解出x2. 生成树:若图G为无向连通图. T为G的生成子 图,且T为树,称T为G的生成树。 三、生成树及其构造方法 树枝与弦:G在T中的边称为T的树枝,G不 在T中的边称为T的弦。 余树:T的弦的集合的导出子图称为T的余树。 生成树 余树 生成树树 余树 例子 无向连通图的生成树不一定唯一 生成树的余树不一定是树 带权图的最小生成树:设G = 是带权 的连通简单图, 具有权最小的生成树称为最小生成树。 T是G的一棵生成树, T中所有枝的权之和称为T的权,记作 :W(T)。 四、最小生成树 方法:避圈法 在不产生回路的基础上依次画出 权值最小的边,直至画出n-1条边 为止 v1 5 6 5 6 5 4 1 v2 v4 v5 v3 2 3 例9.1.1 : 5 v1 5 4 1 v2 v4 v5 v3 2 3 W(T)=1+2+3+4+5=15 6 5 1 v2 v4 v5 v3 2 3 例9.1.2 : v1 5 5 1 v2 v4 v5 v3 2 3 v1 5 6 5 5 5 1 v2 v4 v5 v3 2 3 5 5 oror 5 5 1 v2 v4 v5 v3 2 3 W(T)=1+2+3+5+5=16 !最小生成树不一定唯一 定义: 设T是n阶m条边的无向连通图G的一棵 生成树,设e1, e2, , emn+1为T的弦. 设Cr为T添加弦er产生的G中惟一的圈 (由er和树枝组成), 称Cr为对应弦er的 基本回路 r=1, 2, , mn+1. 称C1,C2, , Cmn+1为对应T 的基本回路系统. 五:基本回路与基本回路系统 例9.1.3 : Ca=aef Cb=bde Cc=cdf 基本回路系统为:Ca, Cb, Cc 定义: 设T是n阶连通图G的一棵生成树, e1, e2, , en1为T的树枝,Si是G的只含树枝 ei, 其他边都是弦的割集, 称Si为对应 生成树T由树枝ei生成的基本割集。 i=1, 2, , n1. 称S1, S2, , Sn1为对应T的基 本割集系统. 六:基本割集与基本割集系统 例9.1.4: Sa=a,f,g Sb=b,g,h Sd=d,h,i Sc=c,f,h Se=e,f,i 基本割集系统为:Sa, Sb, Sc , Sd, Se 课后例题:9.5,9.6,9.7,9.8 课后作业:9.1,9.3,9.4,9.5,9.6,9.7,9.8 9.2 9.2 根树及其应用根树及其应用 一、树的概念 有向树: 基图为无向树的有向图 根树: 有一个顶点入度为0, 其余的入度均为1的 非平凡的有向树 树根: 有向树中入度为0的顶点 树叶: 有向树中入度为1, 出度为0的顶点 内点: 有向树中入度为1, 出度大于0的顶点 分支点: 树根与内点的总称(出度大于等于1) 顶点v的层数: 从树根到v的通路长度,记作l(v) 树高: 有向树中顶点的最大层数,记作h(T) 根树的画法:树根放上方,省去所有有向边上的箭头 如右图所示 a是树根 b,e,f,h,i是树叶 c,d,g是内点 a,c,d,g是分支点 a为0层;1层有b,c; 2层有d,e,f; 3层有g,h; 4层有i. 树高为4 定义 把根树看作一棵家族树: (1) 若顶点 a 邻接到顶点 b, 则称 b 是 a 的儿子 , a 是 b 的父亲; (2) 若b和c为同一个顶点的儿子, 则称b和c是 兄弟; (3) 若ab且a可达b, 则称a是b的祖先, b是a的 后代. (4)设v为根树的一个顶点且不是树根, 称v及其 所有后代的导出子图为以v为根的根子树. 家族树:家族树: 有序树: 每一层的结点均有序 r元树:根树的每个分支点至多有r个儿子 r元正则树: 根树的每个分支点恰有r个儿子 r元完全正则树: 所有树叶层数相同都等于树高的r元 正则树 r元有序树: 有序的r元树 r元正则有序树: 有序的r元正则树 r元完全正则有序树: 有序的r元完全正则树 根树的分类:根树的分类: 定义 设2元树T有t片树叶v1, v2, , vt, 树叶的权分别 为w1, w2, , wt, 称 为T的权, 记作 W(T), 其中l(vi)是vi的层数. 在所有有t片树叶, 带权 w1, w2, , wt 的 2元树中, 权最小的2元树称为最优 2元树. 最优二元树:最优二元树: 给定实数w1, w2, , wt, 作t片树叶, 分别以w1, w2, , wt为权. 在所有入度为0的顶点(不一定是树叶)中选出两个 权最小的顶点, 添加一个新分支点, 以这2个顶点为 儿子, 其权等于这2个儿子的权之和. 重复, 直到只有1个入度为0 的顶点为止. W(T)等于所有分支点的权之和 Huffman算法 例 求带权为1, 1, 2, 3, 4, 5的最优树. 解题过程由下图给出,W(T)=38 例9.2.1: 设 =12n-1n是长度为n的符号串 的前缀: 12k , k=1,2,n-1 前缀码: 1, 2, , m, 其中1, 2, , m为非空字符 串, 且任何两个互不为前缀 2元前缀码: 只出现两个符号(如0与1)的前缀码 如 0,10,110, 1111, 10,01,001,110是2元前缀码 0,10,010, 1010 不是2元前缀码 前缀码:前缀码: 一棵2元树产生一个二元前缀码: 对每个分支点, 若关联2条边, 则给左边标0, 右边标1; 若只关联1条边, 则可以给它标0(看作左边), 也可以 标1(看作右边). 将从树根到每一片树叶的通路上标 的数字组成的字符串 记在树叶处, 所得的字符 串构成一个前缀码. 如右图所示: 树的编码:树的编码: 最优2进制编码:使信息传 递的2进制数最短 例 在通信中,设八进制数字出现的频率如下: 0:25% 1:20% 2:15% 3:10% 4:10% 5:10% 6:5% 7:5% 采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前 缀码), 并求传输10n(n2)个按上述比例出现的八进制数字需 要多少个二进制数字?若用等长的 (长为3) 的码字传输需要 多少个二进制数字? 解 用Huffman算法求以频率(乘以100)为权的最优2元树. 这 里 w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 最优2元树如图所示. 例9.2.2: 编码: 0-01 1-11 2-001 3-100 4-101 5-0001 6-00000 7-00001 传100个按比例出现的八进制数字所需二进制数字的个数 为 W(T)=285. 传10n(n2)个所用二进制数字的个数为2.8510n, 而用等长 码(长为3)需要用 310n个数字. 课后习题:9.9,9.13 行遍(周游)根树T : 对T 的每个顶点访问且仅访问一次. 行遍2元有序正则树的方式: 中序行遍法: 左子树、根、右子树 前序行遍法: 根、左子树、右子树 后序行遍法: 左子树、右子树、根 例如, 对图所示根树按中序、前序、 后序行遍法访问结果分别为: b a (f d g) c e a b (c (d f g) e) b (f g d) e c) a 带下划线的是(子)树根, 一对括号内是一棵子树 树的遍历:树的遍历: 用2元有序正则树表示算式: 最高层次运算放在树 根上, 然后依次将运算符放在根子树的根上, 数放 在树叶上, 规定被除数、被减数放在左子树树叶上. 例如, 右图表示算式 (b+(c+d)a)(ef)(g+h)(ij) 应用:算术式的波兰符号法与逆波兰符号法 波兰符号法(前缀符号法): 按前序法遍历算式树, 其 结果不加括号. 例如, 对上页中树的访问结果为 b + c d a e f + g h i j 逆波兰符号法(后缀符号法): 按后序法遍历, 规定每 个运算符与前面紧邻两数运算. 例如,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论