您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 薪酬管理 > 离散数学网络课程形成性考核第4次形考任务答案
★形成性考核作业★1离散数学作业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中每一对结点度数之和大于等于n,则在G中存在一条汉密尔顿路.6.若图G=V,E中具有一条汉密尔顿回路,则对于结点集V的每个非空子集S,在G中删除S中的所有结点得到的连通分支数为W,则S中结点数|S|与W满足的关系式为W≤|S|.7.设完全图Kn有n个结点(n2),m条边,当n为奇数时,Kn中存在欧拉回路.8.结点数v与边数e满足e=v-1关系的无向连通图就是树.9.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去4条边后使之变成树.姓名:学号:得分:教师签名:★形成性考核作业★210.设正则5叉树的树叶数为17,则分支数为i=4.二、判断说明题(判断下列各题,并说明理由.)1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路.答:不正确。因为图是否是连通的与结点的度数为奇数还是偶数无关。故图G的结点度数均为偶数,并不能保证图G一定连通。当图G不连通时,图G中就不存在欧拉回路。2.如下图所示的图G存在一条欧拉回路.答:不正确。因为图G虽然是连通的。但b,c两结点的度数都是奇数,所以图G中不存在欧拉回路。3.如下图所示的图G不是欧拉图而是汉密尔顿图.答:正确。因为结点a,b,d,f的度数均为3度,故不是欧拉图。去掉边(a,d)、(b,c)、(c,f)后,该图就是一个回路,且只经过所有的结点一次,故是汉密尔顿图。4.设G是一个有7个结点16条边的连通图,则G为平面图.答:不正确。因为如果G是平面图,由于37=v,则G应满足欧拉公式的。推论63-≤ve,因此15673=-⨯≤e。与已知条件16=e矛盾,故G不是平面图。5.设G是一个连通平面图,且有6个结点11条边,则G有7个面.答:正确。因为G是连通平面图,故G应满足欧拉公式2=+-rev,于是面数762112=-+=-+=ver。G★形成性考核作业★3三、计算题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)画出其补图的图形.解:V1(1)如右图V5V2V3V4(2)邻接矩阵如下:0110010110110110110000100(3)v1的度数为1,v2的度数为2,v3的度数为4,v4的度数为3,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权最小的生成树及其权值.解:(1)G的图形表示如图十四:★形成性考核作业★4图十四(2)邻接矩阵:0111110110110011100110110(3)粗线表示最小的生成树,如图十五如图十五最小的生成树的权为1+1+2+3=7:3.已知带权图G如右图所示.(1)求图G的最小生成树;(2)计算该生成树的权值.解:(1)图G有6个结点,其生成树有5条边,用Kruskal算法求其权最小的生成树T:1.取具最小权1的边:2.取剩余边具有最小权2的边:3.取剩余边中不与前2条边构成回路的具最小权3的边:4.取剩余边中不与前3条边构成回路的具最小权5的边;5.取剩余边中不与前4条边构成回路的具最小权7的边:6.所求最小生成树T如下图:★形成性考核作业★5(2)该最小生成树的权为W(T)=1+2+3+5+7=184.设有一组权为2,3,5,7,17,31,试画出相应的最优二叉树,计算该最优二叉树的权.解:最优二叉树如下图所示:最优二叉树权值为:131四、证明题1.设G是一个n阶无向简单图,n是大于等于3的奇数.证明图G与它的补图G中的奇数度顶点个数相等.证明:设G=V,E,G=V,E’,则E’是由n阶无向完全图Kn的边删去E所得到的,所以对于任意结点u∈V,u在G和G中的度数之和等于u在Kn中的度数,由于n是大于等于3的奇数,从而Kn的每个结点都是偶数度的(n-1(≥2)度),于是若u∈V在G中是奇数度结点,则它在G中也是奇数度结点,帮图G与它的补图G中的奇数度结点个数相等。2.设连通图G有k个奇数度的结点,证明在图G中至少要添加2k条边才能使其成为欧拉图.证明:由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k是偶数.又根据定理4.1.1的推论,图G是欧拉图的充分必要条件是图G不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G的所有结点的度数★形成性考核作业★6变为偶数,成为欧拉图.故最少要加2k条边到图G才能使其成为欧拉图
本文标题:离散数学网络课程形成性考核第4次形考任务答案
链接地址:https://www.777doc.com/doc-5894605 .html