离散数学测验题--图论部分

离散数学图论单元测验题

一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G＝中，结点总度数与边数的关系是( )

(A) deg(vi)=2?E? (B) deg(vi)=?E? (C)

?deg(v)?2E (D) ?deg(v)?E

v?Vv?V2、设D是n个结点的无向简单完全图，则图D的边数为( ) (A) n(n－1) (B) n(n+1) (C) n(n－1)/2 (D) n(n+1)/2

3、 设G＝为无向简单图，?V?=n，?(G)为G的最大度数，则有

(A) ?(G)n (D) ?(G)?n

4、图G与G?的结点和边分别存在一一对应关系，是G≌G?(同构)的( ) (A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件 5、设V?{a,b,c,d}，则与V能构成强连通图的边集合是( )

(A) E?{?a,d?,?b,a?,?b,d?,?c,b?,?d,c?} (B) E?{?a,d?,?b,a?,?b,c?,?b,d?,?d,c?} (C) E?{?a,c?,?b,a?,?b,c?,?d,a?,?d,c?}

6、有向图的邻接矩阵中，行元素之和是对应结点的( )，列元素之和是对应结点的( (A)度数 (B) 出度 (C)最大度数 (D) 入度

7、设图G的邻接矩阵为

??00100??00011?

??10000??

?01001????01010??则G的边数为( )．

A．5 B．6 C．3 D．4

8、设G??V,E?,V?n,E?m为连通平面图且有r个面，则r＝( ) (A) m－n+2 (B) n－m－2 (C) n+m-2 (D) m+n+2

9、在5个结点的二元完全树中，若有4条边，则有 ( )片树叶。 (A) 2 (B) 3 (C) 5 (D) 4 10、图2是( ) (A) 完全图 (B)欧拉图 (C) 平面图 (D) 哈密顿图 ? ? ?

? ? ?

图2

)

二、填空题(本大题共10小题，每题2分，共20分)

1、设图G＝和G?＝,若 ，则G?是G的真子图，若 ，则G?是G的生成子图.

2、设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有 条边，G的总度数是 ，G的分支点数是 ，G中度数为3的结点数是 . 3、一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，问它有几个度数为1的结点。

4、画出满足下列条件的图：

(1) 画一个有一条欧拉回路和一条哈密顿回路的图； (2) 画一个有一条欧拉回路，但没有哈密顿回路的图； (3) 画一条没有欧拉路，但有一条哈密顿回路的图.

5、设G是n个结点的简单图，若G中每对结点的度数之和 ，则G一定是哈密顿图.

6、一个有向树T称为根树，若 ，其中 称为树根，

称为树叶. 7、设G是平面图，G有8个面，每个面的度数都是3，则G有__________条边，G有__________个顶点。 8、设G是有n个结点，m条边的连通图，要确定G的一棵生成树，必须删去G的 条边.

9、在下图中，哪些是欧拉图？哪些是哈密顿图？哪些是平面图？

? ?

? ? ? （1） ? ? (3) （2） ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (4) ? ? ? ? （6） (5) 10、设G是n阶无向带权边连通图，各边的权均为a(a>0),设T是G的一棵最小生成树，则T的权W(T)=________（n-1）*a_______________。

三、计算题(本大题共4小题，每小题10分，共40分)

1、设G＝是一个无向图，V?{v1,v2,...,v8},

E?{(v1,v2),(v2,v3),(v3,v1),(v1,v5),(v5,v4),(v3,v4),(v7,v8)}

(1) G＝的?V?，?E?各是多少？ (2) 画出G的图示； (3) 指出与v3邻接的结点，以及与v3关联的边； (4) 指出与e1关联的结点； (5) 该图是否有孤立结点和孤立边？ (6) 求出各结点的度数；

2、设图G是具有3个顶点的无向完全图，试问

(1) G有多少个子图？ (2) G有多少个生成子图？

(3) 如果没有任何两个子图是同构的，则G的子图个数是多少？将它们构造出来.

3．图G=，其中V={a, b, c, d, e, f }，E={(a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d,

f), (e, f)}，对应边的权值依次为5，2，1，2，6，1，9，3及8．

（1）画出G的图形； （2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值．

4．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试

（1）画出相应的最优二叉树； （2）计算它们的权值．

四、证明题(本大题共3小题，任选2题，每小题10分，共20分)

1．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的．

2．设G是一个n阶无向简单图，n是大于等于2的奇数．证明图G与它的补图G中的奇数度顶点个数相等．

3．设连通图G有k个奇数度的结点，证明在图G中至少要添加欧拉图．

k条边才能使其成为2

补充

1、若图G是不连通的，则G的补图G是连通的。

2、当且仅当G的一条边e不包含在G的回路中时，e才是G的割边。 3、设G是简单平面图，则它—定有一个度数≤5的结点。

解答：

一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G＝中，结点总度数与边数的关系是( )

(A) deg(vi)=2?E? (B) deg(vi)=?E? (C)

?deg(v)?2E (D) ?deg(v)?E

v?Vv?V 答案：(C)

2、设D是n个结点的无向简单完全图，则图D的边数为( ) (A) n(n－1) (B) n(n+1) (C) n(n－1)/2 (D) n(n+1)/2 答案： （C）

3、 设G＝为无向简单图，?V?=n，?(G)为G的最大度数，则有 (A) ?(G)n (D) ?(G)?n 答案：(A)

解答：因为G中无平行边和环，任何结点最多有n－1条边与其相关联，最大度数小于或等于n－1. 故选择(A)

4、图G与G?的结点和边分别存在一一对应关系，是G≌G?(同构)的( ) (A) 充分条件 (B) 必要条件 (C)充分必要条件 (D)既非充分也非必要条件 答案：(B) 解答：见图的同构定义. 5、设V?{a,b,c,d}，则与V能构成强连通图的边集合是( )

(D) E?{?a,d?,?b,a?,?b,d?,?c,b?,?d,c?} (E) E?{?a,d?,?b,a?,?b,c?,?b,d?,?d,c?} (F) E?{?a,c?,?b,a?,?b,c?,?d,a?,?d,c?} (G) E?{?a,b?,?a,c?,?a,d?,?b,d?,?c,d?}

答案：(A) 解答：有向图G任何一对结点间都互相可达，称该图是强连通的. (A)所给的边的集合存在一个通过所有结点的通路. 故选择(A).

6、有向图的邻接矩阵中，行元素之和是对应结点的( )，列元素之和是对应结点的( ) (A)度数 (B) 出度 (C)最大度数 (D) 入度 答案：(B)，(D)

解答：见邻接矩阵的定义. 7、设图G的邻接矩阵为

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