离散数学作业5答案[1]1

《离散数学作业5答案[1]1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、名号分名签师姓学得教离散数学作业5离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型安排练习题目，目的是通过综合性书而作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。要求：将此作业用A4纸打印出來，手工书写答题，字迹工整，解答题要有解答过程，完成并上交任课教师（不收电了稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。一、单项选择题1.设图G的邻接矩阵为

2、A.5B.600100000111000000110001C・3则G的边数为（DD.42.设图G=vU,E>,则下列结论成立的是（C）.A.deg(V)=21E

3、B.deg(V)=IE

4、C・^deg(v)=2

5、E

6、vgV3.设有向图(a)、(b)、D.^deg(v)=

7、EvgV（c）与（d）如下图所示，则下列结论成立的是（A).何何A.（°）是强连通的B.C.（c）是强连通的D.（b）是强连通的（〃）是强连通的4.给定无向图G如右图所示，下面给出的结点集子集中，不是点割集的为（B）.A.{b,d}B.{d}4题图5.图G如右图所示，以下说法止确的是(C)・

8、A.{(a,c)}是割边B.{(d,c)}是边割集C.{@,c)}是边割集D.{(d,c),(b,c)}是边割集6.无向图G存在欧拉通路，当月•仅当(D).A.G中所有结点的度数全为偶数B.G中至多有两个奇数度结点C.G连通且所有结点的度数全为偶数D.G连通且至多有两个奇数度结点7.若G是一个欧拉图，则G—定是(C).A.平面图B.汉密尔顿图C.连通图D.对偶图A.e—v+2D.e+v+2)•8.设G是连通平面图，有y个结点，e条边,厂个面，则匸(A9.设G是有〃个结点，加条边的连通图，必须删去G的(A)条边，才能确定G的一棵生成树•A.m-n+B.m-

9、nC•m+/7+1D.n-m+10.已知一棵无向树T中有8个结点,4度,3度，2度的分支点各一个，T的树叶数为(B).A.8B.5C.4D.3二、填空题1.已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是.2.设给定图G(如右由图所示)，则图G的点割集是{f,c}.3.设G是一个图，结点集合为U,边集合为E,则G的结点等于边数的两倍.4.设冇向图D为欧拉图，则图D中每个结点的入度等丁•出度5.设G=是具有〃个结点的简单图，若在G中每一对结点度数之和大于等于,则在G中存在一条汉密尔顿路.6.设无向图G=是

10、汉密尔顿图，则V的任意非空子集W，都有—W(G・V1)<

11、Vj.7.设完全图K”有n个结点(心2),加条边，当时，K”中存在欧拉冋路.1.设图G=，其中

12、V

13、=n,E=m.则图G是树当且仅当G是连通的,且m-n-1・1.连通无向图G有6个顶点9条边，从G中删去条边才有可能得到G的一棵生成树T.2.设正则5叉树的树叶数为17,则分支数为/=4.三、判断说明题(判断下列各题，并说明理由・)1.(1)如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路・・(2)图Gi，(如下图所示)是欧拉图.解：(1)错，图G是无向图，当且仅当G是连通的

14、，且所有结点度数均为偶数，这里不能确定G图是否是连通的。(2)对，由欧拉图的定理“无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结点”得到，这里可找到如F—条欧拉回路v4v5v2V6V4V]v2v3V402.图G2(如下图所示)不是欧拉图而是汉密尔顿图.图（h解：对，由欧拉图的定理“无向图G具有一条欧拉路，当且仅当G是连通的，且冇零个或两个奇数度结点”，这里结点a,b,d,f的度数都为奇数；它是汉密尔顿图，因为找到了如下一条汉密尔顿冋路abefgdcao3.(1)设G是一个有7个结点16条边的连通图，则G为平面图.(2)设G是一个连通平面

15、图，且有6个结点11条边，则G有7个面.解：(1)错，没有提到面。⑵对，由欧拉定理得到：结点■边+面=2,即为连通平面图，这里6-11+7=21.卜•图给出的树是否同构的.解：(a)不与(b)、(c)同构,{0(b)>(c)同构。因为由图的同构相关联，得到同构的必要条件：⑴结点数目相同；⑵边数相同；(3)度数相同的结点数口相同。四、计算题1.设G=,V={vi，叱，v4,v5},E={Oim),(V2,v3),(叱必)，(门冲)，仙卩5)，(吹5)}，试(1)给出G的图形表示；(2)写出其邻接矩阵；(2)求出每个结点的度数；(4)I田i出其补图的

16、图形.解：(1)G的图形如下vi0010000(2)G=11010