资源描述：
《电大离散数学任务05答案()》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、名号分名签师姓学得教离散数学作业5离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书而作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。木次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。要求：将此作业用A4纸打印岀来，手工书写答题，字迹工整，解答题耍有解答过程，要求木学期第15周末前完成并上交任课教师（不收电了稿）。并在05任
2、务界而下方点击“保存”和“交卷”按钮，以便教师评分。一、填空题1.已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是・1.设给定图G(如右曲图所示)，则图G的点割集是2.设G是一个图，结点集合为U,边集合为E,则G的结点等于边数的两倍.3.无向图G存在欧拉回路，当且仅当G连通且有零个或2个奇数度数的结点.4.设G=中具有一条汉密尔顿冋路，则对于结点集V的毎个非空子集S,在G
3、小删除S小的所有结点得到的连通分支数为W,则S屮结点数ISI与W满足的关系式为W(G・S)小于等于ISI.6.设完全图K”有〃个结点(n>2),m条边，当n是奇数口大于等于3时，K”中存在欧拉回路.7.结点数u与边数幺满足关系的无向连通图就是树.8.设图G是冇6个结点的连通图，结点的总度数为18,则可从G屮删去4条边后使Z变成树.1.设止则5叉树的树叶数为17,则分支数为，二4二、判断说明题（判断下列各题，并说明理由•）1・如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路…答：对。因为结点度数均为偶数，因此
4、必是连通图，根据定理4.1.1,G存在一条欧拉回路。2.如卜•图所示的图G存在一条欧拉回路.答:对。图G符合定理4.1.12.如下图所示的图G不是欧拉图而是汉密尔顿图.图G2.设G是一个有7个结点16条边的连通图，则G为平面图.答:不对。因为G(v,e)如果是平面图，必须有e小于等于3v・616不能小于等于3*7-6,因此G不是平面图。2.设G是一个连通平面图，且有6个结点11条边，则G有7个面.答：对。因为6-11+7=2符合欧拉定理v-e+「=2o三、计算题1・设G=,V={V],V2,V4,v5},E={
5、（V1,V3）,（V2,V3）,（V2,V4），（吹4），（V3,V5），（V4,V5）}，试（1）给出G的图形表示；（2）写出其邻接矩阵；（4）画出其补图的图形.（3）求出每个结点的度数；答：（1）:(2)邻接矩阵为:r00100^00110A(G)=1101101101<00110^(3)deg(vl)=l,deg(v2)=2,deg(v3)=4,deg(v4)=3,deg(v5)=2.(4)图G的补图为V42.图G=,其中V={a,b,c,d,e,E={(a,b),(a,c),(a,e(b,d),(b
6、,e),(c,£),(c,rf),(d,£)},对应边的权值依次为2、1、2、3、6、1、4及5,试(1)i田i出G的图形；(2)写出G的邻接矩阵；(3)求出G权最小的主成树及其权值.A(G)=「01101001I11101]011011101110丿(3)最小生成树:权W(G)二1+1+2+3=72.已知带权图G如右图所示.⑴求图G的最小生成树；(2)让算该生成树的权值.解答：(1):最小生成树(2)权W(G)=5+1+2+3+7=182.设有一组权为2,3,5,7,17,31,试画出相应的最优二叉树，计算该最优二叉树
7、的权.解答:最优二叉树31权W(T)=2*5+3客5+5*4+7*3+17*2+31*1=131四、证明题1.设G是一个斤阶无向简单图，斤是大于等于3的奇数•证明图G与它的补图乙中的奇数度顶点个数和等.证明：因为"是奇数，即〃阶完全图每个顶点度数为偶数.那么，若G中顶点-的度数为奇数时，在补图乙中"的度数一定也是奇数，所以G与X中的奇数度顶点个数相等.2.设连通图G有£个奇数度的结点，证明在图G屮至少要添加土条边才能2使其成为欧拉图.证明：由定理3.1.2,任何图中度数为奇数的结点必是偶数，可知k是偶数.乂根据定理4.1
8、.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点.因此只要在每对奇数度结点Z间各加一条边，使图G的所冇结点的度数变为偶数，成为欧拉图.故最少要加土条边到图G才能使其成为欧拉图.2
