2016离散数学作业5答案
更新时间:2024-03-20 19:25:01 阅读量: 综合文库 文档下载
★ 形成性考核作业 ★
离散数学作业5
姓 名: 学 号: 得 分: 教师签名: 离散数学图论部分形成性考核书面作业
本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业。
要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求2010年12月5日前完成并上交任课教师(不收电子稿)。并在05任务界面下方点击“保存”和“交卷”按钮,以便教师评分。
一、填空题
1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是 15 .
2.设给定图G(如右由图所示),则图G的点割集是 {f,c}.
3.设G是一个图,结点集合为V,边集合为E,则 G的结点 度数之和 等于边数的两倍.
4.无向图G存在欧拉回路,当且仅当G连通且 所有结点的度数全为偶数 . 5.设G=
6.若图G=
7.设完全图Kn有n个结点(n?2),m条边,当n为奇数时,Kn中存在欧拉回路.
8.结点数v与边数e满足 e= v-1 关系的无向连通图就是树. 9.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去 4 条边后使之变成树.
10.设正则5叉树的树叶数为17,则分支数为i = 4 .
二、判断说明题(判断下列各题,并说明理由.)
1
★ 形成性考核作业 ★
1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路.. 答:不正确,图G是无向图,当且仅当G是连通,且所有结点度数均为偶数,这里不能确定图G是否是连通的。
2.如下图所示的图G存在一条欧拉回路.
答:错误。
因为图G为中包含度数为奇数的结点
3.如下图所示的图G不是欧拉图而是汉密尔顿图.
G
答:错,既不是欧拉图也不是汉密尔顿图,欧拉图要求所有结点度数均为偶数,这里结点bd各有三个节点;汉密尔顿图要求每一对结点度数之和大于等于总结点数,这里不满足。
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=
(1) 给出G的图形表示; (2) 写出其邻接矩阵; (3) 求出每个结点的度数; (4) 画出其补图的图形.
答:(1) v1°
v2
° °v3
2
★ 形成性考核作业 ★
v4° °v5
?00100??00110???(2) A(D)??11011?
??01101????00110??
(3) deg(v1)?1、deg(v2)?2、deg(v3)?4、deg(v4)?3、deg(v5)?2
(4) °v1
v2° °v3
v4° °v5
2.图G=
(1)画出G的图形; (2)写出G的邻接矩阵; (3)求出G权最小的生成树及其权值. b c
解:(1) 。 。
2 1 a。 6 4 2 1 3 。 。 e 5 d
?0?1?(2) A(D)??1??0??1
1101? 0011??0011?
?(3) b c 1101? 。 。 1110??3
★ 形成性考核作业 ★
2 1 3
a。 1 。 。 e d 其权值为:7 3.已知带权图G如右图所示.
(1) 求图G的最小生成树; (2)计算该生成树的权值.
答:(1)
1 2
7
5 3
(2) 权值为18。
4.设有一组权为2, 3, 5, 7, 17, 31,试画出相应的最优二叉树,计算该最优二叉树的权.
解: 65
17 48
5 12
17 31
2 3 5 7
权值为65。 四、证明题
1.设G是一个n阶无向简单图,n是大于等于3的奇数.证明图G与它的补图G中的奇数度顶点个数相等.
证明:设a为G中任意一个奇数度顶点,由G定义,a仍为G顶点,为区分起见,记为a’, 则deg(a)+deg(a’)=n-1, 而n为奇数,则a’必为奇数度顶点。由a的任意性,容易得知结论成立。
2.设连通图G有k个奇数度的结点,证明在图G中至少要添加使其成为欧拉图.
证明:由定理推论知:在任何图中,度数为奇数的结点必是偶数个,则k是
k条边才能2 2
★ 形成性考核作业 ★
偶数。又由欧拉图的充要条件是图G中不含奇数度结点。因此,只要在每对奇数度结点间各加一条边,使图G的所有结点的度数变为偶数,成为欧拉图。故
k最少要加条边才能使其成为欧拉图。
2 2
正在阅读:
2016离散数学作业5答案03-20
我学会了滑滑板作文400字07-06
童年的游戏作文02-04
幼儿园纲要学习心得体会03-08
2013年开学第一课主题02-18
2015年深圳中考语文解读01-30
摄影高考基础知识考题07-18
30亿资金的操盘手对缠论的理解05-26
- 计算机试题
- 【2012天津卷高考满分作文】鱼心人不知
- 教育心理学历年真题及答案--浙江教师资格考试
- 20180327-第六届“中金所杯”全国大学生金融知识大赛参考题库
- 洪林兴达煤矿2018年度水情水害预测预报
- 基本要道讲义
- 机电设备安装试运行异常现象分析与对策
- 《有机化学》复习资料-李月明
- 非常可乐非常MC2--非常可乐广告策划提案 - 图文
- 2011中考数学真题解析4 - 科学记数法(含答案)
- 企业人力资源管理师三级07- 09年真题及答案
- 基于单片机的光控自动窗帘控制系统设计说明书1 - 图文
- 20160802神华九江输煤皮带机安装方案001
- (共53套)新人教版一生物必修2(全册)教案汇总 word打印版
- 2014行政管理学总复习
- 中国银监会关于加强地方政府融资平台贷款风险监管的指导意见
- 民宿酒店核心竞争与研究
- 游园活动谜语大全2012
- 河南省天一大联考2016届高三英语5月阶段性测试试题(六)(A卷)
- 小型超市管理系统毕业论文详细设计4
- 离散
- 作业
- 答案
- 数学
- 2016