资源描述：
《2019电大离散数学形成性考核作业5答案(图论部分)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、名号分鋅lip姓学得剳电大离散数学作业5离散数学图论部分形成性考核书面作业木课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。要求：将此作业用A4纸打印出來，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5FI前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师
2、评分。一、填空题1.己知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是一15.2.设给定图G（如右由图所示），则图G的点割集是{f}.3.设G是一个图，结点集合为仏边集合为E,则G的结点等于边数的两倍.4.无向图G存在欧拉回路，当且仅当G连通且・5.设G=是具有比个结点的简单图，若在G屮每一对结点度数Z和大于等于—n-1,则在G中存在一条汉密尔顿路.6.若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S,在G中删除S屮的所有结点得到的连通分支数为W,则S屮结点数⑶与卬满足的关系式为W（G・V1）<1vj•7.设完全图
3、K”有〃个结点（/1>2）,m条边，当n为奇数时,K”中存在欧拉冋路.8.结点数卩与边数£满足关系的无向连通图就是树.9.设图G是有6个结点的连通图，结点的总度数为18,则可从G中删去4条边后使之变成树.10.设正则5叉树的树叶数为17,贝I」分支数为i=5二、判断说明题（判断下列各题，并说明理由・）1.如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路••（1）不正确，缺了一个条件，图G应该是连通图，可以找出一个反例，比如图G是一个有孤立结点的图。1.如下图所示的图G存在一条欧拉回路.(2)不止确，图中有奇数度结点，所以不存在是欧拉回路。1.如下图所示的图G不是欧
4、拉图而是汉密尔顿图.解：正确因为图屮结点a,b,d,f的度数都为奇数，所以不是欧拉图。如果我们沿着(a,d,g,f,e,b,c,a),这样除起点和终点是a外，我们经过每个点一次仅一次，所以存在一条汉密尔顿回路，是汉密尔顿图2.设G是一个有7个结点16条边的连通图，则G为平面图.解：(1)错误假设图G是连通的平面图，根据定理，结点数v,边数为e,应满足e小于等于3v-6,但现在16小于等于3*7-6,显示不成立。所以假设错误。3.设G是一个连通平面图，且有6个结点11条边，则G有7个面.(2)正确根据欧拉定理，有v・e+「2,边数v=ll,结点数e=6,代入公式求出面数「7三、计
5、算题1.G=,V={V1，叱，V3,内，吟},E={(V],V3),(V2,V3),(v2,v4)^(V3,V4)，(>3»5)，(v4,v5)},(1)给出G的图形表示；(3)求出每个结点的度数;解：(I)(2)写岀其邻接矩阵；(4)画出其补图的图形.(2)邻接矩阵为厂00100、001101101101101(00110丿(3)力结点度数为1,”2结点度数为2,内结点度数为3,山结点度数为2,比结点度数为2(4)补图图形为2.图G=,其中V={a,b,c,d,e},E={(a,b),(a,c),(a,e)9(b,d),(b,e),(c,e),(c,d),
6、(d,e)},对应边的权值依次为2、1、2、3、6、1、4及5,试(1)画出G的图形；(2)写出G的邻接矩阵；(3)求出G权最小的生成树及其权值.(1)G的图形如下：1aco4/i歹ebd^5(2)写出G的邻接矩阵广2001220036100420340526250丿(3)G权最小的牛成树及其权值2.已知带权图G如右图所示.⑴求图G的最小牛成树；(2)计算该牛成树的权值.解：(1)最小生成树为⑵该生成树的权值为(1+2+34-5+7)=183.设有一组权为2,3,5,7,17,31,试画岀相应的最优二叉树，计算该最优二叉树的权.权为2*5+3*5+5*4+7*3+17*2+3
7、1=131四、证明题1.设G是一个//阶无向简单图，兀是大于等于3的奇数•证明图G与它的补图乙中的奇数度顶点个数相等.证明：设G=,G=•则E'是由拜阶无向完全图的边删去E所得到的.所以对于任意结点^eV,比在G和乙中的度数之和等于u在K”中的度数.由于斤是大于等于3的奇数，从而K”的每个结点都是偶数度的（n-1Q2）度），于是若wgV在G中是奇数度结点，则它在乙中也是奇数度结点.故图G与它的补图乙中的奇数度结点个数相等.2.设连通图6有£个奇数度的结点，证明在图G中至少要
