4 图论单元测试(answer).doc

离散数学单元测试（图论）一、 填空题1. 任意两点之间都有边相连的无向简单图称为 完全图 ；只有点，没有边的图称为 零图 ；只有一个点的图称为 平凡图 。2. 有n个顶点的连通无向图中至少有 n -1 条边。3. 无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点的度数均小于3，问G的阶数n至少为 11 。4. 写出如下无向图的关联矩阵：关联矩阵：5. 对任何连通平面图恒有：顶点数边数面数 2 。8. 设是一个有n个结点的有向完全简单图，则的边数为 n(n-1) 。9. 设为一棵树，边数为 ，顶点个数为，则 B 。ABCD.10. 下列所示图中， (2)(3)(5)(6) 是平面图， (1)(2)(5) 是二部图， (1)(2)(3)(4)(5)(6) 是哈密尔顿图， (4) 是欧拉图。 （1）（2）（3）（4）（5） （6）二、判断题1. 判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？ 非负整数序列可图化可简单图化(5,5,4,4,2,1)FF(5,4,3,2,2)TF(3,3,3,1)TF(4,4,3,3,2,2)TT2.判断下列命题的真假值。（1）完全图Kn(n3)都是欧拉图。F（2）n(n2)阶有向完全图都是欧拉图。T（3）完全二部图Kr,s(r,s均为非0正偶数)都是欧拉图T（4）完全图Kn(n1)都是哈密顿图。F（5）设T是n阶非平凡的无向树，则T中至少有两片树叶。T（6）哈密顿图一定是连通图。T（7）欧拉图中只有2个奇度点。F（8）在简单图中，连通但删去一条边后就不连通的图一定是树。T三、简答与计算题1. 设有向图D如下图，（1） 写出D的邻接矩阵；（2） 求出图D中V1到V4长度为1，2，3，4的通路各有多少条？（3） 求出图D中V1到V1长度为1，2，3，4的回路各为多少条？（4） D中长度为4的通路（不含回路）有多少条？（5） D中长度为4的回路有多少条?（6） D中长度小于等于4的通路共有多少条？其中有几条是回路？（7） 写出D的可达矩阵。 解:（1） 计算出：可知：（2）图D中V1到V4长度为1，2，3，4的通路各有0、0、2、2条。（3）图D中V1到V1长度为1，2，3，4的回路各为1、1、3、5条。（4）D中长度为4的通路（不含回路）有33条。（5）D中长度为4的回路有11条。（6）D中长度小于等于4的通路共有88条，其中有22条是回路。（7）写出D的可达矩阵。2. 求如下两个图的最小生成树。 解：利用prim或kruscal算法求解，画出最小生成树（略），其代价分别为：6和12。4. 一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点？解：设T有n个顶点（其中有x个3度顶点），m条边，根据题意和相关性质有：n=5+3+xm=n-1联立求解，x=3，n=11。可知T有11个顶点。5. 设7个字母在通信中出现的频率如下：a：35% b：20% c：15% d：10%e：10% f：5% g：5%用Huffman算法求传输它们的最优前缀码。要求画出最优树，指出每个字母对应的编码。并指出传输10n个按上述频率出现的字母，需要多少个二进制数字。解：（1）根据权为5,5,10,10,15,20,35画出的最优树为（可不唯一，但其权不变） （2）a,b,g对应的编码分别为： a 01 b 11 c 001 d 101 e 100 f 0001 g 0000（3）W(T)=255，这是传输100个按给定比例出现的字母所需要的二进制数字。于是传输 10n（n2）个按给定比例出现的字母需要的二进制字个数为 。 五、 证明题1. 在n个顶点的无向完全图中共有条边。2. 设9阶无向图的每个顶点的度数为5或6， 证明它至