《9.1无向树及生成树.ppt》由会员分享，可在线阅读，更多相关《9.1无向树及生成树.ppt（29页珍藏版）》请在三一文库上搜索。
1、1,第9章 树,9.1 无向树及生成树 9.2 根树及其应用,2,9.1 无向树及生成树,无向树、森林 树枝、弦、余树 生成树 基本回路与基本回路系统 基本割集与基本割集系统 最小生成树,3,无向树,无向树(树): 连通而无回路的无向图，用T表示. 平凡树: 平凡图 森林: 每个连通分支都是树的非连通的无向图 树叶: 树中度数为1的顶点 分支点: 树中度数2的顶点 右图为一棵12阶树. 声明:本章中所讨论的回路均 指简单回路或初级回路,4,无向树的性质,定理9.1 设G=是n阶m条边的无向图，则下面各命题是等价的： （1）G是树(连通无回路); （2）G中任意两个顶点之间存在惟一的路径; （3
2、）G中无回路且m=n1; （4）G是连通的且m=n1; （5）G是连通的且G中任何边均为桥; （6）G中没有回路, 但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.,5,无向树的性质(续),定理9.2 设T 是 n 阶非平凡的无向树，则T中至少 有两片树叶. 证 设T有x片树叶，由握手定理及定理9.1可知， 由上式解出x2.,6,例题,例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶点全是树叶. 试求树叶数, 并画出满足要求的非同构的无向树. 解 用树的性质m=n1和握手定理. 设有x片树叶，于是 n=1+2+x=3+x, 2m=2(n1)=2(2+x)=
3、13+22+x 解出x=3，故T有3片树叶. T的度数列为1, 1, 1, 2, 2, 3 有2棵非同构的无向树, 如图所示,7,例题,例2 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点的度数均为4. 求T的阶数n, 并画出满足要求的所有非同构的无向树. 解 设T的阶数为n, 则边数为n1, 4度顶点的个数为n7. 由握手定理得 2m=2(n1)=51+21+31+4(n7) 解出n=8, 4度顶点为1个. T的度数列为1,1,1,1,1,2,3,4 有3棵非同构的无向树,8,生成树,设G为无向连通图 G的生成树: G的生成子图并且是树 生成树T的树枝: G在T中的边 生成树T的
4、弦: G不在T中的边 生成树T的余树 : 所有弦的集合的导出子图 注意： 不一定连通, 也不一定不含回路. 右图黑边构成生成树 红边构成余树,9,生成树的存在性,定理 任何无向连通图都有生成树. 证 用破圈法. 若图中无圈, 则图本身就是自己的生成树. 否则删去圈上的任一条边, 这不破坏连通性, 重复进行 直到无圈为止,剩下的图是一棵生成树. 推论1 设n阶无向连通图有m条边, 则mn1. 推论2 设n阶无向连通图有m条边, 则它的生成树的余树 有mn+1条边.,推论3 设 为G的生成树 T 的余树，C 为G 中任意一个圈，则C与 一定有公共边.,10,基本回路与基本回路系统,定义 设T是n阶
5、m条边的无向连通图G的一棵生成 树，设e1, e2, , emn+1为T的弦. 设Cr为T添加弦er 产生的G中惟一的圈(由er和树枝组成), 称Cr为对应 弦er的基本回路或基本圈, r=1, 2, , mn+1. 称C1, C2, , Cmn+1为对应T的基本回路系统. 求基本回路的算法: 设弦e=(u,v), 先求T中u到v的路径 uv, 再并上弦e, 即得对应e的基本回路.,11,基本割集与基本割集系统,定义 设T是n阶连通图G的一棵生成树, e1, e2, , en1为T的树枝，Si是G的只含树枝ei, 其他边都是弦 的割集, 称Si为对应生成树T由树枝ei生成的基本割 集, i=1
6、, 2, , n1. 称S1, S2, , Sn1为对应T的基本 割集系统. 求基本割集的算法: 设e为生成树T的树枝, Te由两 棵子树T1与T2组成, 令 Se=e | eE(G)且e的两个端点分别属于T1与T2 则Se为e对应的基本割集.,12,实例,例 图中红边为一棵生成树, 求对应它的基本回路系统 与基本割集系统 解 弦e,f,g对应的基本回路分别为 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基=Ce, Cf, Cg. 树枝a,b,c,d对应的基本割集分别为 Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d,
7、g, S基=Sa, Sb, Sc, Sd.,13,无向图与最小生成树,对无向图或有向图的每一条边e附加一个实数w(e), 称作边e 的权. 图连同附加在边上的权称作带权图, 记作G=. 设G是G的子图, G所有边的权的和称作G的权, 记作W(G). 最小生成树: 带权图权最小的生成树 求最小生成树的算法避圈法 (Kruskal) 设G=, 将非环边按权从小到大排序：e1, e2, , em. (1) 取e1在T中 (2) 检查e2, 若e2与e1不构成回路, 则将e2加入T中, 否则弃去e2. (3) 检查e3, 重复进行直至得到生成树为止.,14,实例,例 求图的一棵最小生成树,W(T)=3
8、8,15,9.2 根树及其应用,有向树 根树、树根、树叶、内点、分支点 家族树、根子树、有序树 r元树（r元有序树） r元正则树（r元有序正则树） r元完全正则树（r元有序完全正则树） 最优2元树与Huffman算法 前缀吗与最佳前缀吗 中序行遍法、前序行遍法、后续行遍法 波兰符号法与逆波兰符号法,16,有向树与根树的定义,有向树: 基图为无向树的有向图 根树: 有一个顶点入度为0, 其余的入度均为1的 非平凡的有向树 树根: 有向树中入度为0的顶点 树叶: 有向树中入度为1, 出度为0的顶点 内点: 有向树中入度为1, 出度大于0的顶点 分支点: 树根与内点的总称 顶点v的层数: 从树根到v
9、的通路长度 树高: 有向树中顶点的最大层数,17,根树(续),根树的画法:树根放上方,省去所有有向边上的箭头 如右图所示 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,18,家族树,定义 把根树看作一棵家族树: (1) 若顶点 a 邻接到顶点 b, 则称 b 是 a 的儿子, a 是 b 的父亲; (2) 若b和c为同一个顶点的儿子, 则称b和c是兄弟; (3) 若ab且a可达b, 则称a是b的祖先, b是a的后代. 设v为根树的一个顶点且不是树根, 称v及其所有后 代的导出子图
10、为以v为根的根子树.,19,根树的分类,有序树: 将根树同层上的顶点规定次序 r元树:根树的每个分支点至多有r个儿子 r元正则树: 根树的每个分支点恰有r个儿子 r元完全正则树: 树叶层数相同的r元正则树 r元有序树: 有序的r元树 r元正则有序树: 有序的r元正则树 r元完全正则有序树: 有序的r元完全正则树,20,最优2元树,定义 设2元树T有t片树叶v1, v2, , vt, 树叶的权分别 为w1, w2, , wt, 称 为T的权, 记作 W(T), 其中l(vi)是vi的层数. 在所有有t片树叶, 带权 w1, w2, , wt 的 2元树中, 权最小的2元树称为最优 2元树.,21
11、,求最优树,Huffman算法: 给定实数w1, w2, , wt, 作t片树叶, 分别以w1, w2, , wt为权. 在所有入度为0的顶点(不一定是树叶)中选出两个权最小的顶点, 添加一个新分支点, 以这2个顶点为儿子, 其权等于这2个儿子的权之和. 重复, 直到只有1个入度为0 的顶点为止. W(T)等于所有分支点的权之和,22,实例,例 求带权为1, 1, 2, 3, 4, 5的最优树 解题过程由下图给出，W(T)=38,23,前缀码,设 =12n-1n是长度为n的符号串 的前缀: 12k , k=1,2,n-1 前缀码: 1, 2, , m, 其中1, 2, , m为非空字符 串,
12、且任何两个互不为前缀 2元前缀码: 只出现两个符号(如0与1)的前缀码 如 0,10,110, 1111, 10,01,001,110是2元前缀码 0,10,010, 1010 不是前缀码,24,前缀码(续),一棵2元树产生一个二元前缀码: 对每个分支点, 若关联2条边, 则给左边标0, 右边标1; 若只关联1条边, 则可以给它标0(看作左边), 也可以 标1(看作右边). 将从树根到每一片树叶的通路上标 的数字组成的字符串 记在树叶处, 所得的字符 串构成一个前缀码. 如右图所示,25,最佳前缀码,例 在通信中，设八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4
13、：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元树如图所示.,26,编码: 0-01 1-11 2-001 3-100 4-101 5-0001 6-00000 7-00001 传100个按比例出现的八进制数字所需
14、二进制数字的个数 为 W(T)=285. 传10n(n2)个所用二进制数字的个数为2.8510n, 而用等长 码(长为3)需要用 310n个数字.,27,波兰符号法与逆波兰符号法,行遍(周游)根树T : 对T 的每个顶点访问且仅访问一次. 行遍2元有序正则树的方式： 中序行遍法: 左子树、根、右子树 前序行遍法: 根、左子树、右子树 后序行遍法: 左子树、右子树、根 例如, 对图所示根树按中序、前序、 后序行遍法访问结果分别为： b a (f d g) c e a b (c (d f g) e) b (f g d) e c) a 带下划线的是(子)树根, 一对括号内是一棵子树,28,波兰符号法
15、与逆波兰符号法(续),用2元有序正则树表示算式: 最高层次运算放在树 根上, 然后依次将运算符放在根子树的根上, 数放 在树叶上, 规定被除数、被减数放在左子树树叶上. 例如, 右图表示算式 (b+(c+d)a)(ef)(g+h)(ij),29,波兰符号法与逆波兰符号法(续),波兰符号法(前缀符号法): 按前序行遍法访问表示 算式的2元有序正则树, 其结果不加括号, 规定每个 运算符号与其后面紧邻两个数进行运算. 例如, 对上页中树的访问结果为 b + c d a e f + g h i j 逆波兰符号法(后缀符号法): 按后序行遍法访问, 规定每个运算符与前面紧邻两数运算. 例如, 对上页中树的访问结果为 b c d + + a e f g h + i j ,