- 1、本文档共7页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
★ 形成性考核作业 ★
PAGE
PAGE 5
姓 名:
姓 名:
学 号:
得 分:
教师签名:
离散数学作业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=V,E是具有n个结点的简单图,若在G中每一对结点度数之和大于等于 ︱v︱ ,则在G中存在一条汉密尔顿路.
6.若图G=V, E中具有一条汉密尔顿回路,则对于结点集V的每个非空子集S,在G中删除S中的所有结点得到的连通分支数为W,则S中结点数|S|与W满足的关系式为 W ≤ S .
7.设完全图K有n个结点(n?2),m条边,当 n为奇数时 时,K中存在欧拉回路.
8.结点数v与边数e满足 e=v - 1 关系的无向连通图就是树.
9.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去
条边后使之变成树.
10.设正则5叉树的树叶数为17,则分支数为i = 4 .
二、判断说明题(判断下列各题,并说明理由.)
1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路.
答:错误。应叙述为:“如果图G是无向连通图,且其结点度数均为偶数,则图G存在一条欧拉回路。”
2.如下图所示的图G存在一条欧拉回路.
答:错误。因为图中存在奇数度结点,所以不存在欧拉回路。
3.如下图所示的图G不是欧拉图而是汉密尔顿图.
G
G
答:正确。因为有4个结点的度数为奇数,所以不是欧拉图;而对于图中任意点集V中的非空子集V1,都有P(G-V1)≤ V1?。其中P(G-V1)是从图中删除V1结点及其关联的边。
4.设G是一个有7个结点16条边的连通图,则G为平面图.
答:错误。若G是连通平面图,那么若V≥ 3,就有e≤3v-6?而163×7-6,所以不满足定理条件,叙述错误。
5.设G是一个连通平面图,且有6个结点11条边,则G有7个面.
答:正确。因为连通平面图满足欧拉公式。即:v-e+r=2。由此题条件知6-11+7=2成立
三、计算题
1.设G=V,E,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)
(3)
?
deg(v1)=1, deg(v2)=2 ,deg(v3)=4 ,deg(v4)=3,deg(v5)=2
(4)
2.图G=V, E,其中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
3.已知带权图G如
文档评论(0)