第一范文网 - 专业文章范例文档资料分享平台

2018国家开放大学离散数学(本)形考任务4答案 

来源:用户分享 时间:2025/6/10 9:50:28 本文由loading 分享 下载这篇文档手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:xxxxxxx或QQ:xxxxxx 处理(尽可能给您提供完整文档),感谢您的支持与谅解。

★ 形成性考核作业 ★

离散数学作业4

姓 名: 学 号: 得 分: 教师签名: 离散数学图论部分形成性考核书面作业

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

要求:学生提交作业有以下三种方式可供选择:

1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅.

2. 在线提交word文档

3. 自备答题纸张,将答题过程手工书写,并拍照上传.

一、填空题

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

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

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

4.无向图G存在欧拉回路,当且仅当G连通且 不含奇数度结点 .

5.设G=是具有n个结点的简单图,若在G中每一对结点度数之和大于等于 ︱v︱ ,则在G中存在一条汉密尔顿路.

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

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

8.结点数v与边数e满足 e=v - 1 关系的无向连通图就是树.

1

★ 形成性考核作业 ★

9.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去 条边后使之变成树.

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

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

1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路. 答:错误。应叙述为:“如果图G是无向连通图,且其结点度数均为偶数,则图G存在一条欧拉回路。”

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

答:错误。因为图中存在奇数度结点,所以不存在欧拉回路。

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

G

答:正确。因为有4个结点的度数为奇数,所以不是欧拉图;而对于图中任意点集V中的非空子集V1,都有P(G-V1)≤ V1除V1结点及其关联的边。

P(G-V1)是从图中删

2

★ 形成性考核作业 ★

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

答:错误。若G是连通平面图,那么若V≥ 3,就有e≤3v-6 而16>3×7-6,所以不满足定理条件,叙述错误。

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

答:正确。因为连通平面图满足欧拉公式。即:v-e+r=2。由此题条件知6-11+7=2成立

三、计算题

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) 画出其补图的图形.

3

★ 形成性考核作业 ★

答:(1)

(2)

(3)

deg(v1)=1, deg(v2)=2 ,deg(v3)=4 ,deg(v4)=3,deg(v5)=2

(4)

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权最小的生成树及其权值.

(2)

(3)

其中权值是:7

5

★ 形成性考核作业 ★

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

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

答:(1)

(2)

权值:18

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

权值:65

6

★ 形成性考核作业 ★

四、证明题

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

证明:设a为G中任意一个奇数度顶点,由定义,a仍为顶点,为区分起见,记为a’, 则deg(a)+deg(a’)=n-1, 而n为奇数,则a’必为奇数度顶点。由a的任意性,容易得知结论成立。

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

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

证明:由定理推论知:在任何图中,度数为奇数的结点必是偶数个,则k是偶数。又由欧拉图的充要条件是图G中不含奇数度结点。因此,只要在每对奇数度结点间各加一条边,使图G的所有结点的度数变为偶数,成为欧拉图。故最少要加条边才能使其成为欧拉图。

7

2018国家开放大学离散数学(本)形考任务4答案 .doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印
本文链接:https://www.diyifanwen.net/c273dv0fnid1qw0b8cvba7dd7d92wae01arr_1.html(转载请注明文章来源)
热门推荐
Copyright © 2012-2023 第一范文网 版权所有 免责声明 | 联系我们
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ:xxxxxx 邮箱:xxxxxx@qq.com
渝ICP备2023013149号
Top