离散数学测试三

北京联合大学 师范学院

第 1 页 共 2 页

离散数学测试题（三）

一、 单项选择题（本大题共4个小题，每小题5分，共20分）

1、若供选择答案中的数值表示一个简单图中各个顶点的度数，能画出图的是

( )

A. ()1,1,1,2,3

B. ()1,2,3,4,5

C. ()1,3,3,3,3

D. ()3,3,4,5,6

2、 仅有孤立点组成的图是 （ ） A. 零图 B. 平凡图 C. 完全图 D. 子图

3、 已知图关系G 的邻接矩阵为01001

01101010

11

0?????

???????

，则G 中长度为2的路径共有 （ ）

A. 8条

B. 13条

C. 14条

D. 18条

4、设G 为7阶无向图,下列命题中可能为真的是 （ ） A. G 的每个顶点的度数都是3; B. G 的每个顶点的度数都是5; C. G 的每个顶点的度数都是6; D. G 的每个顶点的度数都是7.

二、填空题（本大题共6个小题，每小题5分，共30分）

5、设无向图G =是哈密尔顿图， V 1是V 的任意非空子集，则

p (G -V 1)_______1V .

6、连通无向图G 为欧拉图当且仅当_________________________________.

7、3个顶点2条边的所有非同构的子图的有向简单图有____________个.

8、任何图G 中所有顶点的度数之和为G 中边数的________________________.

9、已知无向图G 有35条边，每个顶点的度数至少为3度， G 中顶点个

数最多为____________________.

10、____________n =时,无向完全图n K 是欧拉图.

三、计算演算题（本大题共2个小题，每小题15分，共30分）

11、教育部门打算在某新建小区建一所学校,让附近七个居民区(A 、B 、C 、D 、E 、

F 、G)的学生就近入学.七个居民区之间的道路如图所示,问学校应建在(D 、

北京联合大学 师范学院

第 2 页 共 2 页

E)哪个居民区更合理?(单位:百米)

12、有向图D 如图所示，求D 中长度为4的通路总数，并指出其中有

多少条是回路？又有几条是3v 到4v 的通路.

四、证明题（本大题共2个小题，每小题10分共20分）：

13、无向图G 如图所示.证明：G 既不是欧拉图，也不是哈密尔顿图.

b

h f

e g 14、设 ,T V E =<>是非n 阶平凡树，证明：T 中至少有2片树叶。

a C