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

《离散数学》单元测试（图论） 一、 填空题 完全图 ；只有点，没有边的图称为 零图 ；只有一个点的图称为 平凡图 。 有n个顶点的连通无向图中至少有 n -1 条边。 无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点的度数均小于3，问G的阶数n至少为 对任何连通平面图恒有：顶点数－边数＋面数＝ 2 。 设Ｇ是一个有n个结点的有向完全简单图，则Ｇ的边数为 n(n-1) 。 设为一棵树，边数为 ，顶点个数为，则 B 。 A． B． C． D. 下列所示图中， (2)(3)(5)(6) 是平面图， (1)(2)(5) 是二部图， (1)(2)(3)(4)(5)(6) 是哈密尔顿图， (4) 是欧拉图。 （1） （2） （3） （4） （5） （6） 二、判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？ (5,5,4,4,2,1) F F (5,4,3,2,2) T F (3,3,3,1) T F (4,4,3,3,2,2) T T 2.判断下列命题完全图Kn(n≥3)都是欧拉图。n(n≥2)阶有向完全图都是欧拉图。完全二部图Kr,s(r,s均为非0正偶数)都是欧拉图完全图Kn(n≥1)都是哈密顿图设T是n阶非平凡的无向树，则T中至少有两片树叶。计算题 求出图D中V1到V4长度为1，2，3，4的通路各有多少条？中V1到V1长度为1，2，3，4的回路各为多少条？中长度为4的通路（不含回路）有多少条？中长度为4的回路有多少条?中长度小于等于4的通路共有多少条？其中有几条是回路？ 计算出： 可知： （2）图D中V1到V4长度为1，2，3，4的通路各有中V1到V1长度为1，2，3，4的回路各为中长度为4的通路（不含回路）有条中长度为4的回路有条中长度小于等于4的通路共有条其中有是回路。 求两个图的最小生成树。 解：利用prim或kruscal算法求解，画出最小生成树（略），其代价分别为：6和12。 一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点？n=5+3+x m=n-1 联立求解，x=3，n=11。 可知T有顶点设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（n≥2）个按给定比例出现的字母需要的二进制字个数为 。 、 证明题 n个顶点的无向完全图中共有条边。 设9阶无向图的每个顶点的度数为5或6， 证明它至少有5个6度顶点或者至少有6个5度顶点。 若G是有n个点m条边，且每个面至少由t条边（t≥3）围成的连通平面图，则。并利用该结论，证明K5和K3,3是非平面图。 5