资源描述:
《电大离散数学(本)形考任务_1.doc》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、★形成性考核作业★姓名:王稼骏学号:49得分:教师签名:离散数学作业4离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握.本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业.要求:学生提交作业有以下三种方式可供选择:1.可将此次作业用A4纸打印出来,手工书写答题
2、,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅.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中每一对结点度数之和
3、大于等于︱v︱,则在G中存在一条汉密尔顿路. 6.若图G=中具有一条汉密尔顿回路,则对于结点集V的每个非空子集S,在G中删除S中的所有结点得到的连通分支数为W,则S中结点数
4、S
5、与W满足的关系式为W≤S.7.设完全图K有n个结点(n³2),m条
6、边,当n为奇数时时,K中存在欧拉回路.8.结点数v与边数e满足e=v-1关系的无向连通图就是树.9.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去7★形成性考核作业★条边后使之变成树.10.设正则5叉树的树叶数为17,则分支数为i=4.二、判断说明题(判断下列各题,并说明理由.)1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路.答:错误。应叙述为:“如果图G是无向连通图,且其结点度数均为偶数,则图G存在一条欧拉回路。”2.如下图所示的图G存在一条欧拉回路.答:错误。因为
7、图中存在奇数度结点,所以不存在欧拉回路。3.如下图所示的图G不是欧拉图而是汉密尔顿图.G答:正确。因为有4个结点的度数为奇数,所以不是欧拉图;而对于图中任意点集V中的非空子集V1,都有P(G-V1)≤V1½。其中P(G-V1)是从图中删除V1结点及其关联的边。7★形成性考核作业★4.设G是一个有7个结点16条边的连通图,则G为平面图.答:错误。若G是连通平面图,那么若V≥3,就有e≤3v-6 而16>3×7-6,所以不满足定理条件,叙述错误。
8、 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
9、)},试(1)给出G的图形表示;(2)写出其邻接矩阵;(3)求出每个结点的度数;(4)画出其补图的图形.7★形成性考核作业★答:(1)(2)(3)=deg(v1)=1,deg(v2)=2,deg(v3)=4,deg(v4)=3,deg(v5)=2(4)7★形成性考核作业★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)
10、写出G的邻接矩阵;(3)求出G权最小的生成树及其权值.(2)(3)其中权值是:77★形成性考核作业★3.已知带权图G如右图所示.(1)求图G的最小生成树;(2)计算该生成树的权值.答:(1)(2)权值:184.设有一组权为2,3,5,7,17,31,试画出相应的最优二叉树,计算该最优二叉树的权.权值:657★形成性考核作业★四、证明题1.设G是一个n阶无向简单图,n是大于等于3的奇数.证明图G与它的补图中的奇数度顶点个数相等.证明:设a为G