文档库

最新最全的文档下载
当前位置:文档库 > 电大离散数学作业5答案(图论部分)

电大离散数学作业5答案(图论部分)

电大离散数学作业5答案(图论部分)

离散数学作业5

离散数学图论部分形成性考核书面作业

本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业。

要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求2010年12月5日前完成并上交任课教师(不收电子稿)。并在05任务界面下方点击“保存”和“交卷”按钮,以便教师评分。

一、填空题

1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G 的边数是 15 .

电大离散数学作业5答案(图论部分)

2.设给定图G (如右由图所示),则图G 的点割集是 {f} .

3.设G 是一个图,结点集合为V ,边集合为E ,则 G 的结点 度数之和 等于边数的两倍.

4.无向图G 存在欧拉回路,当且仅当G 连通且 等于出度 . 5.设G=是具有n 个结点的简单图,若在G 中每一对结点度数之和大于等于 n-1 ,则在G 中存在一条汉密尔顿路.

6.若图G=中具有一条汉密尔顿回路,则对于结点集V 的每个非空子集S ,在G 中删除S 中的所有结点得到的连通分支数为W ,则S 中结点数|S|与W 满足的关系式为 W(G-V1) ≤∣V 1∣ .

7.设完全图K n 有n 个结点(n ≥2),m 条边,当 n 为奇数 时,K n 中存在欧拉回路.

8.结点数v 与边数e 满足 e=v-1 关系的无向连通图就是树. 9.设图G 是有6个结点的连通图,结点的总度数为18,则可从G 中删去 4 条边后使之变成树.

10.设正则5叉树的树叶数为17,则分支数为i = 5 .

二、判断说明题(判断下列各题,并说明理由.)

1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路..

(1) 不正确,缺了一个条件,图G应该是连通图,可以找出一个反例,比如图G是一个有孤立结点的图。

2.如下图所示的图G存在一条欧拉回路.

电大离散数学作业5答案(图论部分)

(2) 不正确,图中有奇数度结点,所以不存在是欧拉回路。

3.如下图所示的图G不是欧拉图而是汉密尔顿图.

G

解:正确

因为图中结点a,b,d,f的度数都为奇数,所以不是欧拉图。

如果我们沿着(a,d,g,f,e,b,c,a),这样除起点和终点是a外,我们经过每个点一次仅一次,所以存在一条汉密尔顿回路,是汉密尔顿图

4.设G是一个有7个结点16条边的连通图,则G为平面图.

解:(1) 错误

假设图G是连通的平面图,根据定理,结点数v,边数为e,应满足e小于等于3v-6,但现在16小于等于3*7-6,显示不成立。所以假设错误。

5.设G是一个连通平面图,且有6个结点11条边,则G有7个面.

(2) 正确

根据欧拉定理,有v-e+r=2,边数v=11,结点数e=6,代入公式求出面数r=7

三、计算题

1.设G=,V={ v1,v2,v3,v4,v5},E={ (v1,v3),(v2,v3),(v2,v4),(v3,v4),(v3,v5),(v4,v5) },试

(1) 给出G的图形表示;(2) 写出其邻接矩阵;

(3) 求出每个结点的度数;(4) 画出其补图的图形.

解:(1)

(2) 邻接矩阵为

???

???

?

?

?

?0110010110110110110000100

(3) v 1结点度数为1,v 2结点度数为2,v 3结点度数为3,v 4结点度数为2,v 5结点度数为2

(4) 补图图形为

2.图G =,其中V ={ a , b , c , d , e },E ={ (a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (c , d ), (d , e ) },对应边的权值依次为2、1、2、3、6、1、4及5,试

(1)画出G 的图形; (2)写出G 的邻接矩阵; (3)求出G 权最小的生成树及其权值.

(1)G 的图形如下:

ο

ο ο ο v 1 ο v 5

v 2 v 3 v 4

ο

ο ο ο v 1 ο

v 5

v 2 v 3

v 4

电大离散数学作业5答案(图论部分)

(2)写出G的邻接矩阵

电大离散数学作业5答案(图论部分)

(3)G权最小的生成树及其权值

电大离散数学作业5答案(图论部分)

3.已知带权图G如右图所示.

(1) 求图G的最小生成树;(2)计算该生成树的权值.解:(1) 最小生成树为

(2) 该生成树的权值为(1+2+3+5+7)=18

4.设有一组权为2, 3, 5, 7, 17, 31,试画出相应的最优二叉树,计算该最优二叉树的权.

3

5

2

5

1

7

17

31

1

3

61

2

3

5

7

权为 2*5+3*5+5*4+7*3+17*2+31=131

四、证明题

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

证明:设,G V E =<>,,G V E '=<>.则E '是由n 阶无向完全图n K 的边删去E 所得到的.所以对于任意结点u V ∈,u 在G 和G 中的度数之和等于u 在n K 中的度数.由于n 是大于等于3的奇数,从而n K 的每个结点都是偶数度的( 1 (2)n -≥度),于是若u V ∈在G 中是奇数度结点,则它在G 中也是奇数度结点.故图G 与它的补图G 中的奇数度结点个数相等.

2.设连通图G 有k 个奇数度的结点,证明在图G 中至少要添加2

k

条边才能使其成为欧拉图.

证明:由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k 是偶数. 又根据定理4.1.1的推论,图G 是欧拉图的充分必要条件是图G 不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G 的所有结点的度数变为偶数,成为欧拉图.

故最少要加2

k

条边到图G 才能使其成为欧拉图.