内容发布更新时间 : 2024/11/6 7:51:27星期一 下面是文章的全部内容请认真阅读。
离散数学图论答案
【篇一：离散数学图论习题】
综合练习
一、 单项选择题
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(n1)个孤立结点构成的图是平凡图(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,e(?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一定是哈密顿图． 答案：?
8．如图1所示带权图中最小生成树的权是． 答案：12
三、化简解答题
1．设无向图g＝v,e，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
图1 5 图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＝v，e，其中 v＝{a,b,c,d,e}, e={(a,b),(b,c),(c,d), (a,e)}
试作出图g的图形，并指出图g是简单图还是多 重图？是连通图吗？说明理由.b e
解：图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?2
3x?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=23 如图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度顶 点．
五、证明题