4 图论单元测试(answer)

本文格式为Word版，下载可任意编辑——4图论单元测试(answer)《离散数学》单元测试（图论）

一、填空题

1.任意两点之间都有边相连的无向简单图称为完全图；只有点，没有边的图称为零图；只有一个点的图称为平凡图。

2.有n个顶点的连通无向图中至少有n-1条边。

3.无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点的度数均小于3，问G

的阶数n至少为11。4.写出如下无向图的关联矩阵：

关联矩阵：

20M?0011001100101000115.对任何连通平面图恒有：顶点数－边数＋面数＝2。

8.设Ｇ是一个有n个结点的有向完全简单图，则Ｇ的边数为n(n-1)。9.设T为一棵树，边数为m，顶点个数为n，则B。

A．n?m

B．n?m?1

C．n?m?1

D.n?m?2

10.以下所示图中，(2)(3)(5)(6)是平面图，(1)(2)(5)是二部图，(1)(2)(3)(4)(5)(6)

是哈密尔顿图，(4)是欧拉图。

A（1）

B（2）

（3）

D（4）

1

（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)TT

2.判断以下命题的真假值。

（1）完全图Kn(n≥3)都是欧拉图。

F（2）n(n≥2)阶有向完全图都是欧拉图。

T（3）完全二部图Kr,s(r,s均为非0正偶数)都是欧拉图T（4）完全图Kn(n≥1)都是哈密顿图。

F（5）设T是n阶非平凡的无向树，则T中至少有两片树叶。T（6）哈密顿图一定是连通图。T（7）欧拉图中只有2个奇度点。

F（8）在简单图中，连通但删去一条边后就不连通的图一定是树。T

三、简答与计算题1.设有向图D如下图，

2

（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的可达矩阵。

1200解:（1）A?001010010010计算出：

122032225642A2?101031022211210,A?122221,A4?4432100112102221可知：

（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条是回路。

1111（7）写出D的可达矩阵P?11111111。1111

3

2.求如下两个图的最小生成树。

解：利用prim或kruscal算法求解，画出最小生成树（略），其代价分别为：6和12。4.一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个

顶点？

解：设T有n个顶点（其中有x个3度顶点），m条边，根据题意和相关性质有：

n=5+3+xm=n-1

?d(v)?5?1?3?2?3?x?2m

ii?1n联立求解，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画出的最优树为（可不唯一，但其权不变）

4

（2）a,b,…,g对应的编码分别为：a——01b——11c——001d——101e——100f——0001g——0000

（3）W(T)=255，这是传输100个按给定比例出现的字母所需要的二进制数字。于是传输10n（n≥2）个按给定比例出现的字母需要的二进制字个数为五、证明题

1.在n个顶点的无向完全图中共有

w(T)?10n?2.55?10n。100n(n?1)条边。22.设9阶无向图的每个顶点的度数为5或6，证明它