离散数学图论习题[优秀]_离散数学图论习题

离散数学图论习题[优秀]由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学图论习题”。

第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)2

2答案：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的所有非同构生成子图有个． 答案：

43．设图GV,E，其中Vn,Em．则图G是树当且仅当G是连通的，且m． 答案：n－

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

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

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

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

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

答案：1

2三、化简解答题

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的图形；

图

1图

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＝，其中

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

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

重图？是连通图吗？说明理由.be

解：图G如图8所示．.图G中既无环，也无平行边，是简单图． cd 图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

23x24211827x＝9 故图G有9个结点． 图

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

2．设图G(如图5表示)是6个结点a,b,c, d,e,f的图，试求，图G的最小生成树，并计算它的权．

c 解：构造连通无圈的图，即最小生成树，用

克鲁斯克尔算法：

第一步： 取ab＝1；第二步： 取af=4第三步： 取fe＝3；第四步： 取ad=9图5第五步： 取bc=2

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

3．一棵树T有两个2度顶点，1个3度顶点；3个4

问它有几片树叶？

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

点．

由握手定理： 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一定是连通的．