离散数学第十六章课件

离散数学第十六章离散数学第十六章树的举例判断图G1、G2、G3是否为树？是不是有回路不是不连通2无向树的等价定义无向树的等价定义定理定理16.1 设设G=是是n阶阶m条边的无向图，则下面各命题条边的无向图，则下面各命题是等价的：是等价的：(1)G 是树是树(2)G 中任意两个顶点之间存在惟一的路径中任意两个顶点之间存在惟一的路径.(3)G 中无回路且中无回路且 m=n 1.(4)G 是连通的且是连通的且 m=n 1.(5)G 是连通的且是连通的且 G 中任何边均为桥中任何边均为桥.(6)G 中没有回路，但在任何两个不同的顶点之间加一条新边，中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈在所得图中得到惟一的一个含新边的圈.3(3)(4).只需证明只需证明G连通连通.用反证法用反证法.否则否则G有有s（s 2）个连）个连通通分支都是小树分支都是小树.于是有于是有mi=ni 1,，这及这及m=n 1矛盾矛盾.证明思路证明思路(2)(3).若若G中有回路，则回路上任意两点之间的路径不中有回路，则回路上任意两点之间的路径不惟一惟一.对对n用归纳法证明用归纳法证明m=n 1.n=1正确正确.设设n k时对，证时对，证n=k+1时也对：取时也对：取G中边中边e，G e有且仅有两个连通分支有且仅有两个连通分支G1,G2(为什么为什么?).ni k，由归，由归纳纳假设得假设得mi=ni 1,i=1,2.于是，于是，m=m1+m2+1=n1+n2 2+1=n 1.(1)(2).关键一步是关键一步是,若路径不惟一必有回路若路径不惟一必有回路.4(4)(5).只需证明只需证明G 中每条边都是桥中每条边都是桥.为此只需证明命题为此只需证明命题 “G 是是 n 阶阶 m 条边的无向连通图，则条边的无向连通图，则 m n 1”.命题的证明命题的证明:对对n归纳归纳.e E,G e只有只有n 2条边，由命题可知条边，由命题可知G e不连通，故不连通，故e为为桥桥.证明思路证明思路(5)(6).由由(5)易知易知G为树，由为树，由(1)(2)知，知，u,v V（u v）,u到到v有惟一路径，加新边有惟一路径，加新边(u,v)得惟一的一个圈得惟一的一个圈.(6)(1).只需证明只需证明G连通，这是显然的连通，这是显然的.5由上式解出由上式解出x 2.定理定理16.2 设设T是是n阶非平凡的无向树，则阶非平凡的无向树，则T 中至少有两片树叶中至少有两片树叶.无向树的性质无向树的性质证证 设设 T 有有 x 片树叶，由握手定理及定理片树叶，由握手定理及定理16.1可知，可知，6例题例题例例1 已知无向树已知无向树T中有中有1个个3度顶点，度顶点，2个个2度顶点，其余顶点度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树全是树叶，试求树叶数，并画出满足要求的非同构的无向树.解解 解本题用树的性质解本题用树的性质m=n 1，握手定理，握手定理.设有设有x片树叶，于是片树叶，于是 n=1+2+x=3+x,2m=2(n 1)=2(2+x)=1 3+2 2+x解出解出x=3，故，故T有有3片树叶片树叶.T 的度数列应为的度数列应为 1,1,1,2,2,3，易知易知3度顶点及度顶点及1个个2度顶点相邻度顶点相邻及和及和2个个2度顶点均相邻是非同度顶点均相邻是非同构的，因而有构的，因而有2棵非同构的无向棵非同构的无向树树T1,T2，如图所示，如图所示.7例例2 已知无向树已知无向树T有有5片树叶，片树叶，2度及度及3度顶点各度顶点各1个，其余顶个，其余顶点的度数均为点的度数均为4，求，求T的阶数的阶数n，并画出满足要求的所有非同，并画出满足要求的所有非同构的无向树构的无向树.例题例题解解 设设T的阶数为的阶数为n,则边数为则边数为n 1，4度顶点的个数为度顶点的个数为n 7.由握手定理得由握手定理得 2m=2(n 1)=5 1+2 1+3 1+4(n 7)解出解出n=8，4度顶点为度顶点为1个个.8T的度数列为的度数列为1,1,1,1,1,2,3,4，共有，共有3棵非同构的无向树，棵非同构的无向树，如图所示如图所示.例题例题9不一定连通，也不一定不含回路，如图所示定义定义16.2 设设G为无向图为无向图(1)G的的生成树生成树T 是是G 的生成子图并且是树的生成子图并且是树(2)生成树生成树T的的树枝树枝T 中的边中的边(3)生成树生成树T的的弦弦不在不在T 中的边中的边(4)生成树生成树T的的余树余树 全体弦组成的集合的导出子图全体弦组成的集合的导出子图16.2 生成树生成树10生成树举例求图G的生成树图图T T1 1和和T T2 2均为均为G G的生成树。的生成树。11定理定理16.3 无向无向图G具有生成具有生成树当且当且仅当当G连通通.生成树存在条件生成树存在条件证证 必要性显然必要性显然.充分性用破圈法（注意：在圈上删除任何一条边，不破坏充分性用破圈法（注意：在圈上删除任何一条边，不破坏连通性）连通性）12最小生成树最小生成树定义定义16.5 T是是G=的生成树的生成树(1)W(T)T各边权之和各边权之和(2)最小生成树最小生成树G的所有生成树中权最小的的所有生成树中权最小的求最小生成树的一个算法求最小生成树的一个算法避圈法避圈法（Kruskal）设）设G=，将，将G中非环边按权从小中非环边按权从小到大排序：到大排序：e1,e2,em.(1)取取e1在在T中中(2)查查e2，若，若e2及及e1不构成回路，取不构成回路，取e2也在也在T 中，否则弃中，否则弃e2.(3)再查再查e3,直到得到生成树为止直到得到生成树为止.13避圈法求最小生成树举例用避圈法求图G的最小生成树14解答abcdef(1)选择权值为选择权值为1的边的边(c,d);1(2)选择权值为选择权值为2的边的边(b,f);2(3)选择权值为选择权值为3的边的边(b,c);3(4)选择权值为选择权值为4的边的边(a,b);4(5)权值为权值为5的边的边(a,f),形成回路形成回路,避开避开权值为权值为6的边的边(a,c),形成回路形成回路,避开避开;权值为权值为7的边的边(d,f),形成回路形成回路,避开避开;(6)选择权值为选择权值为8的边的边(f,e);8加权长度加权长度1234818最小生成树最小生成树15求最小生成树举例求图求图G G的最小生成树的最小生成树v5v4v3v2v1(1)选择权值为选择权值为3的边的边(v1,v5);3(2)选择权值为选择权值为4的边的边(v1,v4);4(3)选择权值为选择权值为4的边的边(v4,v5);形成回路形成回路,避开避开(4)选择权值为选择权值为5的边的边(v2,v5);5(5)选择权值为选择权值为6的边的边(v3,v5);6加权长度为加权长度为3+4+5+618最小生成树最小生成树16解答(2)v5v4v3v2v1(1)选择权值为选择权值为3的边的边(v1,v5);3(2)选择权值为选择权值为4的边的边(v4,v5);4(3)选择权值为选择权值为4的边的边(v1,v4);形成回路形成回路,避开避开(4)选择权值为选择权值为5的边的边(v2,v5);5(5)选择权值为选择权值为6的边的边(v3,v5);6加权长度为加权长度为3+4+5+618最小生成树不唯一，最小生成树的加权长度相同最小生成树不唯一，最小生成树的加权长度相同1716.3 根根树及其应用树及其应用定义定义16.6 T是有向树（基图为无向树）是有向树（基图为无向树）(1)T 为为根树根树T 中一个顶点入度为中一个顶点入度为0，其余的入度均为，其余的入度均为1.(2)树根树根入度为入度为0的顶点的顶点(3)树叶树叶入度为入度为1，出度为，出度为0的顶点的顶点(4)内点内点入度为入度为1，出度不为，出度不为0的顶点的顶点(5)分支点分支点树根及内点的总称树根及内点的总称(6)顶点顶点v的的层数层数从树根到从树根到v的通路长度的通路长度(7)树高树高T 中层数最大顶点的层数中层数最大顶点的层数(8)平凡根树平凡根树平凡图平凡图18根根树实例树实例根树的画法根树的画法树根放上方，省去所有有向边上的箭头树根放上方，省去所有有向边上的箭头19根树举例根树举例树叶树叶:树根树根树的高度：树的高度：3v4,v5,v6,v7,v8,v10,v11,v12分枝结点：分枝结点：v0,v1,v2,v3,v9根结点是分枝结点根结点是分枝结点家族树及根子树家族树及根子树定义定义16.7 T 为非平凡根树为非平凡根树(1)祖先及后代祖先及后代(2)父亲及儿子父亲及儿子(3)兄弟兄弟定义定义16.8 设设v为根树为根树T中任意一顶点，称中任意一顶点，称v及其后代的导出子及其后代的导出子图为以图为以v为根的为根的根子树根子树.21有序树举例有序树举例不考虑同一层上结点的次序，是同一棵树不考虑同一层上结点的次序，是同一棵树两棵不同的有序树。两棵不同的有序树。大大小小(1)T 为为有序根树有序根树同层上顶点标定次序的根树同层上顶点标定次序的根树根树的分类根树的分类(2)分类分类 r 叉树叉树每个分支点至多有每个分支点至多有r 个儿子个儿子 r 叉有序树叉有序树r 树是有序的树是有序的 r 叉正则树叉正则树每个分支点恰有每个分支点恰有r 个儿子个儿子 r 叉正则有序树叉正则有序树 r 叉完全正则树叉完全正则树树叶层数相同的树叶层数相同的r叉正则树叉正则树 r 叉完全正则有序树叉完全正则有序树23定义定义16.9 设设2叉树叉树T 有有t片树叶片树叶v1,v2,vt，权分别为，权分别为w1,w2,wt，称，称 为为T 的权，其中的权，其中l(vi)是是vi 的层数的层数.在所有有在所有有t片树叶，带权片树叶，带权w1,w2,wt 的的2叉树中，权最小的叉树中，权最小的2叉树称为叉树称为最优最优2叉树叉树.最优二叉树最优二叉树求最优树的算法求最优树的算法 Huffman算法算法给定实数给定实数w1,w2,wt，且，且w1 w2 wt.(1)连接权为连接权为w1,w2的两片树叶，得一个分支点，其权为的两片树叶，得一个分支点，其权为w1+w2.(2)在在w1+w2,w3,wt 中选出两个最小的权，连接它们对应的中选出两个最小的权，连接它们对应的顶点顶点(不一定是树叶不一定是树叶)，得新分支点及所带的权，得新分支点及所带的权.(3)重复重复(2)，直到形成，直到形成 t 1个分支点，个分支点，t片树叶为止片树叶为止.24例例 5 求带权为求带权为1,1,2,3,4,5的最优树的最优树.解题过程由图解题过程由图9给出，给出，W(T)=3825求最优二叉树举例求最优二叉树举例设有一组权设有一组权2 2，3 3，5 5，7 7，1111，1313，1717，1919，2020，求相应的最优树。，求相应的最优树。解答解答235711131719205571113171920解答（续）解答（续）5 5 711131719201071113171920解答（续）解答（续）1711131719202417 17 19 20解答（续）解答（续）17 2417192034 241920解答（续）解答（续）24341920392434解答（续）解答（续）2434 395839解答（续）解答（续）58 3997W(T)=6(2+3)+5*5+4*7+3(11+13+17)+2(19+20)=264最佳前缀码最佳前缀码定义定义16.10 设设 1,2,n-1,n是长度为是长度为 n 的符号串的符号串(1)前缀前缀 1,1 2,1 2 n 1 (2)前缀码前缀码 1,2,m中任何两个元素互不为前缀中任何两个元素互不为前缀(3)二元前缀码二元前缀码 i(i=1,2,m)中只出现两个符号，如中只出现两个符号，如0及及1.如何产生二元前缀码？如何产生二元前缀码？定理定理16.6 一棵一棵2叉树产生一个二元前缀码叉树产生一个二元前缀码.推论推论 一棵正则一棵正则2叉树产生惟一的前缀码（按左子树标叉树产生惟一的前缀码（按左子树标0，右子树标，右子树标1）34图所示二叉树产生的前缀码为图所示二叉树产生的前缀码为 00,10,11,011,0100,0101 35用用Huffman算法产生最佳前缀码算法产生最佳前缀码例例6 在通信中，八进制数字出现的频率如下：在通信中，八进制数字出现的频率如下：0：25%1：20%2：15%3：10%4：10%5：10%6：5%7：5%求传输它们的最佳前缀码，并求传输求传输它们的最佳前缀码，并求传输10n（n 2）个按上述）个按上述比比例出现的八进制数字需要多少个二进制数字？若用等长的例出现的八进制数字需要多少个二进制数字？若用等长的（长为（长为3）的码字传输需要多少个二进制数字？）的码字传输需要多少个二进制数字？36解解 用用100个八进制数字中各数字出现的个数，即以个八进制数字中各数字出现的个数，即以100乘各频乘各频率为权，并将各权由小到大排列，得率为权，并将各权由小到大排列，得w1=5,w2=5,w3=10,w4=10,w5=10,w6=15,w7=20,w8=25.用此权产生的最优树如图所示用此权产生的最优树如图所示.求最佳前缀码求最佳前缀码 01-0 11-1 001-2 100-3 101-4 0001-500000-6 00001-7W(T)=285，传传10n(n 2)个个用二进制数字需用二进制数字需2.85 10n个个，用等长码需用等长码需3 10n个数字个数字.37波兰符号法及逆波兰符号法波兰符号法及逆波兰符号法行遍或行遍或周游根树周游根树T对对T的每个顶点访问且仅访问一次的每个顶点访问且仅访问一次.对对2叉有序正则树的周游方式：叉有序正则树的周游方式：中序行遍法中序行遍法次序为：左子树、根、右子树次序为：左子树、根、右子树 前序行遍法前序行遍法次序为：根、左子树、右子树次序为：根、左子树、右子树 后序行遍法后序行遍法次序为：左子树、右子树、根次序为：左子树、右子树、根对图所示根树按中序、前序、对图所示根树按中序、前序、后序行遍法访问结果分别为：后序行遍法访问结果分别为：b a(f d g)c e，a b(c(d f g)e)，b(f g d)e c)a38用用2叉有序正则树存放算式叉有序正则树存放算式存放规则存放规则l最高层次运算放在树根最高层次运算放在树根l后依次将运算符放在根子后依次将运算符放在根子树的根上树的根上l数放在树叶上数放在树叶上l规定：被除数、被减数放规定：被除数、被减数放在左子树树叶上在左子树树叶上 算式算式(b+(c+d)a)(e f)(g+h)(i j)存放在图所示存放在图所示2叉树上叉树上.39波兰符号法波兰符号法波兰符号法波兰符号法按前序行遍法访问存放算式的按前序行遍法访问存放算式的2叉有序正则树，其结果不加叉有序正则树，其结果不加括号，规定每个运算符号及其后面紧邻两个数进行运算，运括号，规定每个运算符号及其后面紧邻两个数进行运算，运算结果正确算结果正确.称此算法为波兰符号法或前缀符号法称此算法为波兰符号法或前缀符号法.对上图的对上图的访问结果为访问结果为 b+c d a e f +g h i j 逆波兰符号法逆波兰符号法按后序行遍法访问，规定每个运算符及前面紧邻两数运算，按后序行遍法访问，规定每个运算符及前面紧邻两数运算，称为逆波兰符号法或后缀符号法称为逆波兰符号法或后缀符号法.对上图的访问结果为对上图的访问结果为 b c d+a e f g h+i j 40第十六章第十六章 习题课习题课主要内容主要内容l无向树及其性质无向树及其性质l生成树、最小生成树、基本回路系统、基本割集系统生成树、最小生成树、基本回路系统、基本割集系统l根树及其分类、最优树、最佳前缀码、波兰符号法、逆波根树及其分类、最优树、最佳前缀码、波兰符号法、逆波兰符号法兰符号法基本要求基本要求l深刻理解无向树的定义及性质深刻理解无向树的定义及性质l熟练地求解无向树熟练地求解无向树l准确地求出给定带权连通图的最小生成树准确地求出给定带权连通图的最小生成树l深刻理解基本回路、基本割集的概念，并会计算深刻理解基本回路、基本割集的概念，并会计算l理解根树及其分类等概念理解根树及其分类等概念l会画会画n阶（阶（n较小）非同构的无向树及根树（较小）非同构的无向树及根树（1 n 6）l熟练掌握求最优树及最佳前缀码的方法熟练掌握求最优树及最佳前缀码的方法l掌握波兰符号法及逆波兰符号法掌握波兰符号法及逆波兰符号法41（2）（3）从而解出从而解出练习练习11.无向树无向树 T 有有ni个个i 度顶点，度顶点，i=2,3,k，其余顶点全是树叶，其余顶点全是树叶，求求T 的树叶数的树叶数.解解 用树的性质：边数用树的性质：边数 m=n 1（n为阶数），及握手定理为阶数），及握手定理.(1)422设设n阶非平凡的无向树阶非平凡的无向树T中，中，(T)k，k 1.证明证明T至少至少 有有k片树叶片树叶.证证 反证法反证法.否则，否则，T至多有至多有s片树叶，片树叶，s k，下面利用握手定理及树的，下面利用握手定理及树的性质性质m=n 1推出矛盾推出矛盾.由于由于(T)k，故存在，故存在v0，d(v0)k.于是，于是，由此解出由此解出s k，这及及s k矛盾矛盾.证本本题的方法有多种，的方法有多种，请用分支点都是割点来用分支点都是割点来证明明.练习练习2433设G为n 阶无向无向简单图，n 5，证明明G 或或 中必含圈中必含圈.本本题的方法很多，的方法很多，证明中用：明中用：G与与 边数之和为边数之和为Kn的边的边数数 ，以及树的性质：，以及树的性质：m=n 1.方法一方法一.反反证法法.否否则G与与 的各连通分支都是树的各连通分支都是树.设设G与与 的连通分支分别为的连通分支分别为G1,G2,Gs和和G 1,G 2,G s.令令ni,mi与与 n j,m j 分别为分别为Gi,G j的顶点数和边数的顶点数和边数.于是于是得得 n2 5n+4 0，解出解出 1 n 4,矛盾于矛盾于n 5.练习练习344谢谢