图论

一、选择题（每小题2分，共50分）

1、设D??V,E?为有向图，则有（ A ）

(A) E?V?V (B) E?V?V (C)V?V?E (D) V?V?E

2、设G??V,E?为无环的无向图，V＝6，E?16，则G 是（D ）

(A) 完全图 (B) 零图 (C) 简单图 (D) 多重图

3、含有5个结点，3条边的不同构的简单图有（ C ）

(A) 2个 (B) 3个 (C) 4个 (D) 5个

4、设图G有n个结点，m条边，且G中每个结点的度数不是k就是k?1，则G中度为k的结点的个数是（ D ）

(A) n/2个 (B) n(n?1)个 (C)nk个 (D) n(k?1)?2m个

5、给定下列序列，哪一个可以构成无向简单图的结点度数序列（ B ）

(A) (1,1,2,2,3) (B) (1,1,2,2,2) (C) (0,1,3,3,3) (D) (1,3,4,4,5)

6、图G和G1的结点和边分别存在一一对应关系是G和G1同构的（ B ）

(A) 充分条件 (B) 必要条件

(C) 充要条件 (D) 既不充分也不必要

7、K4中含有3条边的不同构生成子图有（ B ）

(A) 1个 (B) 3个 (C) 4个 (D) 2个

8、设G??V,E?为无向图，u,v?V，若u,v连通，则（ D ）

(A) d(u,v)?0 (B) d(u,v)?0

(C)d(u,v)?0 (D) d(u,v)?0

9、任何无向图中结点间的连通关系是（ B ）

(A) 偏序关系 (B) 等价关系 (C) 相容关系 (D) 拟序关系

10、设D??V,E?为有向图，V?{a,b,c,d,e,f}，

E?{?a,b?,?b,c?,?a,d?,?d,e?,?f,e?}是（ C ）

(A) 强连通图 (B) 单向连通图 (C) 弱连通图 (D) 不连通图

11、设V?1，D??V,E?是强连通图，当且仅当（ D ）

(A) D中至少有一条通路。 (B) D中至少有一条回路。

(C) D中有通过每个结点至少一次的通路。 (D) D中有通过每个结点至少一次的回路。

12、无向图G中的边e是G的割边的充要条件为（ C ）

(A) e是重边 (B) e不是重边 (C) e不包含在G的任一简单回路中 (D) e不包含在G的某一回路中。

13、在有n个结点的连通图中，其边数（ B ）

(A) 最多 n－1条 (B)至少n－1条 (C) 最多有n条 (D) 至少有n条

14、欧拉回路是（ B ）

(A) 路径 (B) 简单回路 (C) 既是基本回路也是简单回路 (D) 既非基本回路也非简单回路

15、哈密尔顿回路是（ C ）

(A) 路径 (B) 简单回路 (C) 既是基本回路也是简单回路 (D) 既非基本回路也非简单回路

16、设欧拉图G有n个结点，m条边，则n,m有关系（ D ）

(A)n?m (B) n,m的奇偶性必相同 (C) n,m的奇偶性必相反 (D) n,m的奇偶性既可相同也可相反

17、下列命题中，（ D ）是正确的

(A) 欧拉图是哈密尔顿图 (B) 哈密尔顿图是欧拉图 (C) 平面图是树 (D) 树是平面图

18、连通简单无向图有17条边，则该图至少有（ C ）个结点。

(A) 5 (B) 6 (C) 7 (D) 8

19、下列三元组为图的结点数、边数和面数，哪一个不能构成连通平面图（ C ）

(A)(4,4,2) (B) (4,5,3) (C)(9,6,6) (D) (7,8,3)

20、一个无向图有4个结点，其中3个度数为2，3，3，则第4个结点度数不可能是（ B ）

(A) 0个 (B) 1个 (C) 2个 (D) 4个

21、二部图K2,3是（ D ）

(A) 欧拉图 (B) 哈密尔顿图 (C) 非平面图 (D) 平面图

22、下面哪一种图不一定是树（ C ）

(A) 无回路的连通图。 (B) 有n个结点n－1条边的连通图 (C) 每对结点之间都有通路的图 (D) 连通但删去一条边则不连通的图

23、一棵树有2个2度结点，1个3度结点，3个4度结点，则其1度结点数为（ D ）

(A) 5个 (B) 7个 (C) 8个 (D) 9个

24、完全m元树T中有t片树叶，i个分支点，则有关系式（ B ）

(A) i?t?1 (B) (m?1)i?1?t (C)(m?1)i?t (D) (m?1)t?i?1

25、带权为10、15、20、30的最优二叉树的权为（ B ）

(A) 100个 (B) 225个 (C) 400个 (D) 625个

二、有向图D如图所示：（共30分）

v1e2e1e3e5v2

(1) 求D的邻接矩阵A；

v4e6e4v3

(2) 求D的完全关联矩阵M(D)。

(3) D中v1到v4长度为4的通路数为多少？ (4) D中v1到自身长度为3的回路数为多少？

(5) D中长度为4的通路总数为多少？其中有几条回路？

(6) D中长度小于等于4的通路有多少条？其中有多少条是回路？ (7) D是哪类连通图？ (8) 求D的可达矩阵P。 (9) 求出强分图。 解：

?0?1(1) A???0??0?0?13 A???0??0110??1?0010?2? A???0001???010??0011?111?? 010??001?22?22?? 10??01?121??10?01021?4? A???00001???010??001000???11?1?10?100? (2)M(D)???00?1?11?1???0000?11??(4)(3)由A4中a14＝2可知，v1到v4长度为4的通路有2条。 (3)(4)由A3中a11＝0可知，v1到自身长度为3的回路有0条。

(4)(5)D中长度为4的通路总数为??aij＝12，其中对角元素之和为4，说明

i?1j?144D中长度为4的回路为4条。

(6)D中长度小于等于4的通路总数为A,A2,A3,A4中全体元素之和： 6＋8＋10＋12＝36，回路数为0＋4＋0＋4＝8。

?2?2234(7)B?A?A?A?A???0??0264?264??，可知D是单侧连通图。 022??022??1?1???0??0111?111?? 011??011?(8)P?A?A(2)?A(3)?A(4)?1?1T(9)P???1??1100??11?11100?T? ，P?P???00111???111??0000?00?? 11??11?所以，强分图的顶点集为：{v1,v2}，{v3,v4}。

三、用Kruskal算法求给定图的一棵最小生成树。（共8分）

213122C223123

四、韦尔奇·鲍威尔法对给定图着色，求图的着色数n。（共6分）

BAHDEFG

五、给定一组权：2,3,5,7,11,13,17,19,23，构造一棵最优数。（共6分）

?1?1T(9)P???1??1100??11?11100?T? ，P?P???00111???111??0000?00?? 11??11?所以，强分图的顶点集为：{v1,v2}，{v3,v4}。

三、用Kruskal算法求给定图的一棵最小生成树。（共8分）

213122C223123

四、韦尔奇·鲍威尔法对给定图着色，求图的着色数n。（共6分）

BAHDEFG

五、给定一组权：2,3,5,7,11,13,17,19,23，构造一棵最优数。（共6分）

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