离散数学图论习题

第4章 图论

综合练习

一、 单项选择题

1．设L是n阶无向图G上的一条通路，则下面命题为假的是( )． (A) L可以不是简单路径，而是基本路径 (B) L可以既是简单路径,又是基本路径 (C) L可以既不是简单路径，又不是基本路径 (D) L可以是简单路径，而不是基本路径 答案：A

2．下列定义正确的是( )．

(A) 含平行边或环的图称为多重图 (B) 不含平行边或环的图称为简单图 (C) 含平行边和环的图称为多重图 (D) 不含平行边和环的图称为简单图 答案：D

3．以下结论正确是 ( )．

(A) 仅有一个孤立结点构成的图是零图 (B) 无向完全图Kn每个结点的度数是n (C) 有n(n>1)个孤立结点构成的图是平凡图 (D) 图中的基本回路都是简单回路 答案：D

4．下列数组中，不能构成无向图的度数列的数组是( )． (A) (1,1,1,2,3) (B) (1,2,3,4,5) (C) (2,2,2,2,2) (D) (1,3,3,3) 答案：B

5．下列数组能构成简单图的是( )． (A) (0,1,2,3) (B) (2,3,3,3) (C) (3,3,3,3) (D) (4,2,3,3) 答案：C

6．无向完全图K3的不同构的生成子图的个数为（ ）． (A) 6 (B) 5 (C) 4 (D) 3 答案：C

7．n阶无向完全图Kn中的边数为（ ）．

(A)

n(n?1)n(n?1) (B) (C) n (D)n(n+1) 22答案：B

8．以下命题正确的是( )．

(A) n(n?1)阶完全图Kn都是欧拉图 (B) n(n?1)阶完全图Kn都是哈密顿图

(C) 连通且满足m=n－1的图(?V?=n,?E?=m)是树 (D) n(n?5)阶完全图Kn都是平面图 答案：C

10．下列结论不正确是( )．

(A) 无向连通图G是欧拉图的充分必要条件是G不含奇数度结点

(B) 无向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点 (C) 有向连通图D是欧拉图的充分必要条件是D的每个结点的入度等于出度

(D) 有向连通图D有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等

1

于出度 答案：D

11．无向完全图K4是（ ）．

（A）欧拉图 （B）哈密顿图 （C）树 答案：B

12．有4个结点的非同构的无向树有 ( )个．

(A) 2 (B) 3 (C) 4 (D) 5 答案：A

13．设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．

(A) m?n?1 (B) n?m (C) m?n?1 (D) n?m?1 答案：A

14．设G是有6个结点的完全图，从G中删去( )条边，则得到树． (A) 6 (B) 9 (C) 10 (D) 15 答案：C

二、 填空题

1．数组{1，2，3，4，4}是一个能构成无向简单图的度数序列， 此命题的真值是 . 答案：0

2．无向完全图K3的所有非同构生成子图有 个． 答案：4

3．设图G??V,E?，其中?V??n,?E??m．则图G是树当且仅当G是连通的，且m? ． 答案：n－1

4．连通图G是欧拉图的充分必要条件是 ． 答案：图G无奇数度结点

5．连通无向图G有6个顶点9条边，从G中删去 条边才有可能得到G的一棵生成树T． 答案：4

6．无向图G为欧拉图，当且仅当G是连通的，且G中无 结点． 答案：奇数度

7．设图G??V,E?是简单图，若图中每对结点的度数之和 ，则G一定是哈密顿图． 答案：?V

8．如图1所示带权图中最小生成树的权是 ．

答案：12

三、化简解答题

1．设无向图G＝，V={v1，v2，v3，v4，v5，v6}， E={( v1，v2), ( v2，v2), ( v4，v5), ( v3，v4), ( v1，v3),

( v3，v1), ( v2，v4)}． (1) 画出图G的图形；

? 2 2 3 ? 1 ? 7 9 2

? 8 ? 6 图1

v1 v2

v6 v5

v3 v4 图2

2

(2) 写出结点v2, v4，v6的度数； (3) 判断图G是简单图还是多重图． 解：(1) 图G的图形如图5所示．

(2) deg(v2)?4,deg(v4)?3,deg(v6)?0．

(3) 图G是多重图．作图如图2. 2．设图G＝，其中

a? V＝{a,b,c,d,e}, E={(a,b),(b,c),(c,d), (a,e)}

试作出图G的图形，并指出图G是简单图还是多

重图？是连通图吗？说明理由. b? ?e

解：图G如图8所示．. 图G中既无环，也无平行边，是简单图． c? ?d 图G是连通图．G中任意两点都连通.

图3

所以，图G有9个结点．作图如图3．

四、计算题

1．设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图．

解：设图G有x个结点，由握手定理

2?1+2?2+3?4+3?（x?2?2?3）＝12?2

3x?24?21?18?27 x＝9 故图G有9个结点． 图4

满足该条件的简单无向图如图4所示

b ?

2．设图G(如图5表示)是6个结点a,b,c, d,e,f

23 1 15 的图，试求，图G的最小生成树，并计算它的权．

c? 25 ?a 4 ? f 解：构造连通无圈的图，即最小生成树，用

28 9 16 3 克鲁斯克尔算法：

第一步： 取ab＝1；第二步： 取af=4 d ? 15 ? e 第三步： 取fe＝3；第四步： 取ad=9 图5 第五步： 取bc=23

b ? 如图6．权为1+4+3+9+23=40

3．一棵树T有两个2度顶点，1个3度顶点；3个4度顶点， 23 1 c? ? a 4 ? f 问它有几片树叶？

解：设T有n顶点，则有n－1条边．T中有2个 9 3 2度顶点，1个3度顶点，3个4度顶点， d ? ? e 其余n－2－1-3个1度顶

图6 点．

由握手定理： 2·2+1·3+3·4+ (n－2－1-3)=2(n－1) 解得 n=15．于是T有15-6=9片树叶

五、证明题

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

证：用反证法．设G中的两个奇数度结点分别为u和v．假若u和v不连通．

即它们之间无任何通路，则G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点．这与握手定理的推论矛盾．因而u和v一定是连通的．

3

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