离散数学第五版答案 VIP专享VIP免费

离散数学第五版答案【篇一：离散数学第五章作业答案】,2,3，试求d的出读列。解：由于??+v=dv(??),故出度列为2,2,1,0.如图5.5下面各无向图中有几个顶点？（1）16条边，每个顶点都有2度顶点（2）21条边，3个4度顶点，其余是3度顶点（3）24条边，各顶点的度数相同的解：设顶点个数为n，则有握手定理知：(1)2?n=2?16??=16(2)3?4+n?3=2?21??=13(3)设顶点的度数为k，则nk=2*4=48且n,k均为正整数，则①n=1,k=48⑥n=8,k=6②n=2,k=24⑦n=12,k=4③n=3,k=16⑧n=16,k=3④n=4,k=12⑨n=24,k=2⑤n=6,k=8⑩n=48,k=15.11k4的生成子图中有几个非同构的自补图解：1个即5.12画出3阶有向完全图所有非同构子图，问其中有几个是生成子图，生成子图中有几个是自补图。解：顶点个数边数123456123生成子图其中生成子图是16个，子补图是画5.14已知n阶无向图g中有m条边，各顶点的度数均为3，又已知2n-3=m，问在同构的意义下，g是唯一的吗？若g为简单图，是否唯一？解：由握手定理知2m=3n，又知2n-3=m则g不是唯一的，即使简单图也不唯一的如5.18有向图d在定义意义下长度为4的通路总数，并指出有多少条是回路，又有到通得d的邻接矩阵为v11??2=0101100010010，1112110201(4)1v2v3??4=1102110故长度为4的通路总数15，回路数为3，v3到v4的通路有??34=25.19求图中b到其余各定点的最短路径和距离解，用dijkstra算法得t1234567acdefg引入b引入c引入a引入f引入e引入g(1,b)?(5,c)(5,c)(5,c)?(4,c)(4,c)?故b到其余各顶点的最短路径和距离为b→a：ba，长度为4b→c：bc，长度为1b→d：bcegd，长度为9b→e：bce，长度为5b→f：bcf，长度为4b→g：bceg，长度为75.20解：（1）画出项目网络图25【篇二：2016离散数学作业5答案】散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。要求：将此作业用a4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。一、填空题1．已知图g中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则g的边数是15．2．设给定图g(如右由图所示)，则图g的点割集是．3．设g是一个图，结点集合为v，边集合为e，则g的结点等于边数的两倍．4．无向图g存在欧拉回路，当且仅当g连通且．5．设g=v，e是具有n个结点的简单图，若在g中每一对结点度数之和大于等于n-1，则在g中存在一条汉密尔顿回路．6．若图g=v,e中具有一条汉密尔顿回路，则对于结点集v的每个非空子集s，在g中删除s中的所有结点得到的连通分支数为w，则s中结点数|s|与w满足的关系式为w?s．7．设完全图kn有n个结点(n?2)，m条边，当n为奇数时，kn中存在欧拉回路．8．结点数v与边数e满足关系的无向连通图就是树．9．设图g是有6个结点的连通图，结点的总度数为18，则可从g中删去10．设正则5叉树的树叶数为17，则分支数为i二、判断说明题（判断下列各题，并说明理由．）1．如果图g是无向图，且其结点度数均为偶数，则图g存在一条欧拉回路．．答：不正确，图g是无向图，当且仅当g是连通，且所有结点度数均为偶数，这里不能确定图g是否是连通的。2．如下图所示的图g存在一条欧拉回路．答：错误。因为图g为中包含度数为奇数的结点3．如下图所示的图g不是欧拉图而是汉密尔顿图．g答：错，既不是欧拉图也不是汉密尔顿图，欧拉图要求所有结点度数均为偶数，这里结点bd各有三个节点；汉密尔顿图要求每一对结点度数之和大于等于总结点数，这里不满足。5．设g是一个连通平面图，且有6个结点11条边，则g有7个面．答：正确。因为连通平面图满足欧拉公式。即：v?e?r?2。由此题条件知6-11+7=2成立。三、计算题1．设g=v，e，v={v1，v2，v3，v4，v5}，e={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，试(1...