资源描述
2021国家开放大学离散数学(本)形考任务答案离散数学作业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=6若图G=7设完全图K n 有n 个结点(n 2),m 条边,当 n 为奇数时 时,K n 中存在欧拉回路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答:正确。因为有4个结点的度数为奇数,所以不是欧拉图;而对于图中任意点集V中的非空子集V1,都有P(G-V1)V1。其中P(G-V1)是从图中删除V1结点及其关联的边。4设G是一个有7个结点16条边的连通图,则G为平面图答:错误。若G是连通平面图,那么若V3,就有e3v-6 而16376,所以不满足定理条件,叙述错误。5设G是一个连通平面图,且有6个结点11条边,则G有7个面答:正确。因为连通平面图满足欧拉公式。即:v-e+r=2。由此题条件知6-11+7=2成立三、计算题1设G=(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=(1)画出G的图形;(2)写出G的邻接矩阵;(3)求出G权最小的生成树及其权值(2)(3)其中权值是:73已知带权图G如右图所示(1) 求图G的最小生成树;(2)计算该生成树的权值答:(1)(2)权值:184设有一组权为2, 3, 5, 7, 17, 31,试画出相应的最优二叉树,计算该最优二叉树的权权值:65四、证明题1设G是一个n阶无向简单图,n是大于等于3的奇数证明图G与它的补图G中的奇数度顶点个数相等 证明:设a 为G 中任意一个奇数度顶点,由定义,a 仍为顶点,为区分起见,记为a , 则deg(a)+deg(a )=n-1, 而n 为奇数,则a 必为奇数度顶点。由a 的任意性,容易得知结论成立。 2设连通图G 有k 个奇数度的结点,证明在图G 中至少要添加2k 条边才能使其成为欧拉图 证明:由定理推论知:在任何图中,度数为奇数的结点必是偶数个,则k 是偶数。又由欧拉图的充要条件是图G 中不含奇数度结点。因此,只要在每对奇数度结点间各加一条边,使图G 的所有结点的度数变为偶数,成为欧拉图。故最少要加条边才能使其成为欧拉图。
展开阅读全文