2018国家开放大学离散数学本形考任务答案

.可修编.可修编. 离散数学作业4 离散敬学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，容主要分别是集合轮部分、图轮部分、数理遐辑部分的综合练习，基本上是按照考试的题型（除单顶选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握.本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业.要求：学生提交作业有以下三抻方式可供选择：可将此次作业用A4策打印出来，手工书写答题，字述工整，解答體要有解答过程，完成作业后交给浦导教邮批阅.在线提交word文档自备答题纸,将答题过程手工书写，并拍照上传.一、填空題已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，贝IIG的辺数是15 .设给定图G（如右由图协示），删图G的点制集是\/j⑴，{e,c} . /~°― 结点集合为V,边集合为E,i 丄」廿G的结点 等于边数的两倍.无向图G存在卜应回路，当且仅当G连通且不含奇数度结 设GmV,E＞是具有n个结点的简単图，若在G中每一时结点度数之和大于等于lv| ,则在G中存在一条汉密尔顿路.若图GxV,E＞中具有一条汉密尔物回路，则对于结点集V的每个非空子集S,在G中刪除S中的所有结点得到的连通分支数为W,|S中结点数|S|与W满足的关系式方 . 7.设完全图K有n个结点（42）,m条边，当n为奇数时时，Kn n.可修编.可修编.中存在Kfi0路.结点数v与巾数e满足 关系的无向连通图就是材.设图G是有6个结点的连通图，结点的总度数为18,删可从G中刪去条协后使之变设正则5叉材的材叶数为17,则分支她i=4 .二判断说明题（判断下列各題,并说明理由.）如果图G是无向图，且其结点度数均为偶数，删图G存在一条成拉回路.答：错误。应叙述万：“如果图G是无向连通图，且其结点度数均加偶数,删图G存在一条成拉回路。"如下图协示的图G存在一条或拉回路.答：错误。因为图中存在奇数度结点，所以不存在Rfi0路。如下图断示的图G不是0：拉图而是沢密尔项图.答：正确。因为有4个结点的度数力奇数，所以不是攻拉图；而对于图中任意点集V中的非空子集V1,都有P(G-V1)wV1。其中P(G-V1)是从图中UM除V1结点及其关Baffle设G是一个有7个结点16条辺的连通图，则G万平面图.答：錯误。若G是连通平面图，那么若VN3,就有ew3v-6而16>3x7-6,所以不満足定理条件,叙述错误。设G是一个连通平面图，且有6个结点11条边，删G有7个面.

答：正确。因为连通平面图满足畋拉公式。即：v-e+r=2o由此题条件如6-11+7=2成立计算題1.设GxV,E>,V={v,v,v,v,v),E={(v,v),(v,v),(v,v),(v,v),1 2 3 4 5 13 23 24 34(V,V),(V.V)},试(2)写出其邻接炬阵;(4)画出其补图的图形.35(1)(2)写出其邻接炬阵;(4)画出其补图的图形.(3)求岀每个结点的度数;100110011101110(3).可修编.可修编.deg(v1)=1,deg(v2)=2,deg(v3)=4,deg(v4)=3,deg(v5)=2Vl2.图GxV,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）.可修编.可修编.(2)(2).可修编.可修编.01101001r1A(O)=100110110111110(3)h0a0其中权值是：73.已如带权图G如右图所示.(1)求图G的最小生(2)计算该生成材的权值.

4.设有—组权为2,3,5,7,17,31,试画出相应的最优二叉材，计算该最优二叉树的权..可修编.可修编.四、证明題1.设G是一个n盼无向简単图，n是大于等于3的奇数.证明图G与它的补图G中的奇数度顶点个教相等.证明：设a方G中任意一个奇数度顶点，由定义，a仍为顶点，方区分起见,记力a',ideg(a)+deg(a,)=n-1,而n力奇数，删a'必为奇数度顶点。由a的任意性，容易得知结施成立。2.设连通图G有k个奇数度的结点，证明在图G中至少要添加£条边才能2使其JO攻拉图.证明：由定理推论知：在任何图中，度数为奇