离散数学测试题 第6章自测题

第6章自测题

一、填空题(每小题3分，共15分)

1. 对于n阶简单无向图图G，若其边数为m，则G的补图G的边数为( ). 2. 任意n阶简单图G有?(G)? ( ). 3. K3的所有不同构的非空子图有( )个.

?014. 设有向图G = (V, E)，V = {v1，v2，v3，v4}，若G的邻接矩阵A=??1??1101001001?1?, 则v

1

0?1??的出度od(v1) =________, v1的入度id(v1) =________, 从v2到v4长度为2的路有________条.

5.在边赋权图中, 从节点u到节点v的路中, ( )的路称为u到v的最短路径.

二、单选题(每小题3分，共15分)

1. 一个连通无向图有3个5度点、1个4度点、3个2度点，其它的都是1度，那么它

的节点个数是≤（ ）

(A) 17 (B) 18

(C) 19

(D) 20.

2. 4阶完全无向图K4中含3条边的不同构的生成子图有 (A)3 (B)4 (C)5 (D)2.

3. 设G是简单图，G是G的补图，若G?G，则称G为自补图. 5阶不同构的自补图个数为( ).

(A)0. (B)1. (C)2. (D)3. 4. 在任意n阶连通图中，其边数( ).

(A)至多n – 1条. (B)至少n – 1条. (C)至多n条. (D) 至少n条 5. 任何无向图中，节点之间的可达关系是( )关系. (A)等价. (B)相容. (C)偏序. (D)拟序

三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.

1. 设G是简单无向图，则G与G中度数为奇数的节点个数相同. ( ) 2. 设G是简单无向图，则G或G是连通图. ( ) 3. 若无向图G中恰有两个度数为奇数的节点，则该两点必可达. ( )

4. 设G有12条边，6个3度节点，其余节点度数小于3，则G至少有9个节点. ( )

5.存在度数序列为7, 5, 4, 2, 2, 1的图. ( )

四、(15分) 若n个人，每个人恰有3个朋友，则n必为偶数，试证明之. 五、(15分) 下图给出了一个有向图.

(1) 求出它的邻接矩阵A和可达矩阵P. (2) 求出A2，A3，A4.

.

六、(15分) 证明：在至少两个人的人群中，必有两个人有相同个数的朋友.

七、(10分) 证明：一个图是强连通的，当且仅当图中有一个回路，它至少包含每个结点

一次.

本文来源：https://www.bwwdw.com/article/fw9v.html