离散数学常考题型梳理.doc

离散数学常考题型梳理第5章 树及其应用 一、题型分析树是图论中的重要部分之一，其在计算机科学与技术领域有着广泛的应用，二叉树更是程序设计中的一种基本的数据结构。本章主要介绍树、生成树、二叉树、树根、最优树等概念及相关的结论与算法，包括求最小生成树的Kruskal算法、构造最优树的Huffman算法以及前缀码的求法。经常涉及到的题型有：1-1树叶与结点间的计算1-2画最小生成树并求其权1-3构造最优树（Huffman算法）并求其权1-4求前缀码因此，在本章学习过程中希望大家要清楚地知道：1树 连通无简单回路的无向图G. 树中次数为1的顶点称为树叶。次数大于1的顶点称为分支点或内部顶点。森林 一个无向图称为森林，如果它的每个连通分图都是树树的判别 给定图T,则以下命题关于图T为树的定义等价(1) T是无回路的连通图； (2) 图T无回路且ev1，其中e是边数，v是顶点数；(3) 图T连通且ev1；(4) 图T无回路，若增加一条新边，得到且仅得到一个回路；(5) 图T连通，但删去任一边后图便不连通（v0）；(6) 图T的每一对顶点之间有且仅有一条路（v0）. 生成树 给定一个无向图G，若G的一个生成子图T是树，则称T为G的生成树或支撑树。T的边称为树枝。生成树的结论 任何连通图至少有一棵生成树权与带权图 n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图. G的生成树T中树枝的权之和称为T的权，记作W(T). 有向树 如果一个有向图在不考虑边的方向时是一棵树，那么该有向图就是有向树. 根树与树根 一棵有向树T，若恰有一个顶点的入度为0，其余顶点的入度都为1，则称T为根树；入度为0的顶点称为树根；出度为0的顶点称为树叶；入度为1出度不为0的顶点称为内点；根与内点统称为分支点；从树根到T的任一顶点v的通路（顶点不同的路）的长度称为v顶点的层数；层数最大的顶点的层数称为树高2求最小生成树的方法主要有避圈法与破圈法。 避圈法：图G有n个顶点，以下算法产生的是最小生成树（避圈法由kfuskal给出 （1）选择最小的边e1,置边数i1；（2）i=n-1结束，否则转3）；（3）设定已选定e1 ，e2,，ei，在G中选取不同于e1，e2,，ei的边ei+1，使 e1，e2,，ei，ei+1无回路，且ei+1是满足此条件的带权最小的边；（4）ii+1,转2） 破圈法：(1)初始令 G0,= G, i0；（2）若Gi中不含圈，则转（3）；否则，设C为Gi中的一个圈，ei为C上带权最大的边，令Gi+1= Gi - ei ； i i+1，转（1）（3）结束结束时G中的图为最小生成树。最小生成树的权等于最小生成树各边权值的和。 3设T是一棵根树，若T的每个分支点的出度至多为m，则称T为m叉树；若T的每个分支点的出度恰好等于m，则称T为m叉正则树；若T是m叉正则树，且每个树叶的层数均为树高，则称T为完全m叉正则树；若T是m叉树且为有序树，则称T为m叉有序树；若T是m叉正则树且为有序树，则称T为m叉正则有序树；若T是m叉完全正则树且为有序树，则称T为m叉完全正则有序树；若m=2，则T称为二叉树正则m叉树结论 设有正则m叉树，其树叶数为t，分枝数为i，则(m-1)i=t-1带权二叉树 给定一组权w1，w2，wt，不妨设w1w2wt设有一棵二叉树，共有t片树叶，分别带权w1，w2，wt，则该二叉树称为带权二叉树最优树 设在有t个树叶的带权二叉树T中，带权为wi (i=1,t)的树叶，其通路长度为L(wi)，则将w(T) =wiL(wi) (i=1,t)称为该带权二叉树的权在所有带权w1，w2，wt的二叉树中，w(T)最小的树称为最优树用Huffman算法得到的最优树 （Huffman）：设T为带权w1w2wt的最优树，若将以带权w1，w2的树叶为儿子的分枝点改为带权w1+w2的树叶，得到一棵树T，则T也是最优树 最优树的权：每片树叶的权乘以它到树根的长度取和。 4前缀码 给定一个序列集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码结论：任何一棵二叉树的树叶可对应一个前缀码 任何一个前缀码都对应一个二叉树。 二、常考知识点分析 常考知识点1：树叶与结点间的计算（历年考核次数：8次，本课程共考过6次；重要程度：） （2008年7月试卷第8题）设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 条边后使之变成树解题过程 4运用教材中的定理5.1.1，可以作出正确选择因为定理5.1.1中给出的图G为树的等价定义之一是图G连通且e=v-1（e是边数，v是顶点数）若图G变为树，则边数e=6-1=5。由于题中结点的总度数为18，根据定理3.1.1，总度数应为边数2倍，可知此图中有边数9条。所以应该删去9-5=4条边才能使图G 是树。 易错点：题中没有直接给出图G的边数，而是给出了结点的总度数，这里大家要清楚总度数和边数之间的关系。 提示：设G是有n个结点，m条边的连通图，必须删去G的( m-n+1 )条边，才能确定G的一棵生成树 （2009年1月试卷第9题）已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 解题过程 5设无向树T的树叶数为x，因为树叶是度数为1的结点那么，由定理3.1.1（握手定理） 设G是一个图，其结点集合为V，边集合为E，则得 4+3+2+x=2（8-1），即x=5应填5 提示：熟练掌握握手定理，树叶是度数为1的结点。 常考知识点2：画最小生成树并求其权（历年考核次数：1次，本课程共考过6次；重要程度：） （2009年1月试卷第18题）图G=，其中V= a, b, c, d, e，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形； （2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值 解题过程（1）因为V= a, b, c, d, e，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ，对应边的权值依次为2、1、2、3、6、1、4及5，则G的图形表示为： （2）根绝邻接矩阵的定义，写出邻接矩阵为： （3）用避圈法：第1步：选(a, b)边； 第2步：选(a c)边； 第3步：选(c, e)边； 第4步：选(b, d)边这样，得到了最小的生成树，如下图中粗线所示最小的生成树的权为2+1+1+3=7 提示：求最小生成树可以利用避圈法或者破圈法。求最小生成树的权就是各边权值之和。 常考知识点3：构造最优树（Huffman算法）并求其权（历年考核次数：2次，本课程共考过6次；重要程度：） （2009年7月试卷第17题）画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权 解题过程1234732512Huffman算法：从1, 2, 2, 3, 4中选1, 2为最低层结点，并从权数中删去，再添上他们的和数，从小到大排列，即2，3，3，4；再从2，3，3，4中选2，3为倒数第2层结点，并从上述数列中删去，再添上他们的和数，从小到大排列，即3，4，5； 然后，从3，4，5中选3，4为倒数第2层结点，并从上述数列中删去，再添上他们的和数，从小到大排列，即5，7；最优二叉树如右图所示。最优二叉树权值为：13+23+22+32+42=27 提示：最优树的权：每片树叶的权乘以它到树根的长度取和。 常考知识点4：求前缀码（历年考核次数：1次，本课程共考过6次；重要程度：） （2009年1月试卷第8题）给定一个序列集合000，001，01，10，0，若去掉其中的元素 ，则该序列集合构成前缀码 解题过程 0 根据定义5.2.10 给定一个序列集合，若没有一个序列是另一个序列的前缀，则该序列集合为前缀码。 三、模拟练习 练习1：（2008年9月试卷第8题）设G是有6个结点，8条边的连通图，则从G中删去 条边，可以确定图G的一棵生成树 解析：3 根据定理5.1.1可知，当图G成为生成树时，若其有6个结点，则应具有6-1=5条边，而题中具有8条边，则需删去8-5=3条边后才能使图G 成为生成树练习2 ：（2009年7月试卷第1题）结点数v与边数e满足 关系的无向连通图就是树 解析：e=v-1 根据定理5.1.1中给出的图T为树的等价定义之一是图T连通且e=v-1（e是边数，v是顶点数） 练习3 ：设正则5叉树的树叶数为17，则分支数为i = 解析：4 根据定理5.2.1 设有正则m叉树，其树叶数为t，分枝数为i，则(m-1)i=t-1其中m=5， t=17，由(5-1)i=17-1，得i =4 练习4 ：若无向树T中有5片树叶，3个2度分支点，其余的分支点都是3度结点，问T有几个顶点？ 解析：11 设3度结点为x个，则结点数n=5+3+x=8+x，边数m=7+x，利用握手定理可知 2m=14+2x=51+32+3x=11+3x 解得x=3，于是n=8+3=11练习5 ：图G=，其中V=a, b, c, d, e, f ，E=(a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f)，对应边的权值依次为5，2，1，2，6，1，9，3及8（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值ooooocabedof152261938解析：（1）因为V=a, b, c, d, e, f E=(a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f)， 权值依次为5，2，1，2，6，1，9，3及8 所以，G的图形如右图所示：（2）邻接矩阵的定义前面已经复习了,这里按照定义写出 邻接矩阵： （3）用避圈法： ooooocabedof152261938 第1步：选(a, e)和(c, e)边； 第2步：选(b, d)边；（为什么不选(a, c)？） 第3步：选(d, f)边； 第4步：选(a, b)边这样，得到了最小的生成树，如右图中粗线所示最小的生成树的权为1+1+5+2+3=12 注意：在用避圈法求最小的生成树的关键是：“取图中权数最小的边，且与前面取到的边不构成圈”，很多学生只注意到取权数最小的边了，而忽略了“不构成圈”的要求。练习6 ：设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权解析：Huffman算法：从2, 3, 5, 7, 17, 31中选2, 3为最低层结点，并从权数中删去，再添上他们的和数，即5, 5, 7, 17, 31；再从5, 5, 7, 17, 31中选5, 5为倒数第2层结点，并从上述数列中删去，再添上他们的和数，即7, 10, 17, 31；ooooo32755173410oooo1731oo65 然后，从7, 10, 17, 31中选7, 10为倒数第3层结点，并从上述数列中删去，再添上他们的和数，即17