《离散数学作业5答案.docx》由会员分享，可在线阅读，更多相关《离散数学作业5答案.docx（7页珍藏版）》请在三一文库上搜索。
1、最新资料推荐2014离散数学作业5答案形成性考核作业离散数学作业5姓名：翟伟铮学号: 1337001258063得分：教师签名：离散数学图论部分形成性考核书 面作业本课程形成性考核书面作业共3次，内容主要分别是集合论 部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的 题型（除单项选择题外）安排练习题目，目的是通过综合性书面作 业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习， 争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部 分的综合练习作业。要求：将此作业用A4纸打印出来，手工书写答题，字迹工整， 解答题要有解答过程，要求本学期第15周末前完成并上交
2、任课教 师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师 评分。一、填空题1.已知图G中有1个1度结点，2个2度结点, 3个3度结点，4个4度结点，则G的边数是f G的结 点.度数之和等于边数的两倍.等于出度. 15.2.设给定 图G（如右由图所示），则图G的点割集是3.设G是一个图，结点 集合为V,边集合为E,则4.无向图G存在欧拉回路，当且仅当G 连通且大于等于n-1 ,则在G中存在一条汉密尔顿路.5.设G=<V, E>是具有n个结点的简单图，若在G中每一对结点度 数之和6.若图G=E>中具有一条汉密尔顿回路，则对于 结点集V的每个非空子集S,在
3、G中删除S中的所有结点得到的 连通分支数为W,则S中结点数|S|与W满足的关系式为回 路.8.结点数v与边数e满足4 e=v-l关系的无向连通图就是 树.9.设图G是有6个结点的连通图，结点的总度数为18,则 可从G中删去条边后使之变成树.5 . 10.设正则5叉树的树 叶数为17,则分支数为i二二、判断说明题(判断下列各题，并说 明理由.)1.如果图G是无向图，且其结点度数均为偶数，则 图G存在一条欧拉回路.1W?|S|. 7.设完全图K n有n个结 点(n?2), m条边，当n为奇数时，K n中存在欧拉7 / 7形成性考核作业错。缺了一个条件，图G应该是连通图。如反例，图G是一个有孤立结点
4、的图。2 .如下图所示的图G存在一条欧拉回路.错。图中有奇数度结点，所以不存在欧拉回路。3 .如下图所示的图G不是欧拉图而是汉密尔顿图.G对。因为图中结点a、b、d、f的度数都为奇数，所以不是欧拉图。如果沿着(a,d,g,f,e,b,c,a),这样除起点和终点是a外，经过 每个点一次且仅一次，所以存在一条汉密尔顿回路，是汉密尔顿图。2形成性考核作业设G是一个有7个结点16条边的连通 图，则G为平面图.错。假设图G是连通的平面图，根据定理，结点数为v,边数为e, 应满足e?3v-6,但现在16?3*7-6,显然不成立，所以假设错误。5.设G是一个连通平面图，且有6个结点11条边，则G有7 个面.
5、对。根据欧拉定理，有v-e+r=2,结点数v=H,边数一6,代入公式 求出面数r=7o三、计算题 1. 设 G=E>, V= vl, v2, v3, v4, v5, E= (vl, v3),(v2, v3),(v2, v4),(v3, v4),(v3, v5),(v4,v5),试(1)给出G的图形表示；(2)写出其邻接矩阵；(3) 求出每个结点的度数；(4)画出其补图的图形.vl ?0 0 1 0 0? ? ? ? ?0 0 1 1 0? (1) v2 (2) ? 1 1 0 1 1 ? ? ? v5 ? ? ?0 1 1 0 1? ?0 0 1 1 0? ? ? ? ? v4 v3 (
6、3) vl, v2, v3, v4, v5 结点 的度数依次为1, 2, 4, 3, 2ovl (4) ? v2 ? ? v52.图 G=<V, E ?= a, b, c, d, e, E= (a, b), (a, c), (a, e), (b, d), (b, e), ?>,其中 V v4 v 3 (c, e), (c, d), (d, e) ,对应边的权值依次为 2、1、2、3、6、1、4及5,试3形成性考核作业 (1)画出G的图形；(2)写出G的邻接 矩阵；(3)求出G权最小的生成树及其权值.a ?0 1 1 0 1? ? ? ? 2 1 ?1 0 0 1 1? (1) (2
7、)A?10011?2b?c6?0 1 1 0 1? 4 ?1 1 1 1 0? 3 1 ? ? ? ? 5 e d (3) 2 b ? 3 d?权值?e1 a ?1 ?cW(T) =1+1+2+3=73.已知带权图G如右图所示.(1)求图 G的最小生成树；(1) (2)计算该生成树的权值.1 7 523(2)权值 (1+2+3+5+7)=184,设有一组权为 2, 3, 5, 7, 17, 31,试画出相应 的最优二叉树，计算该最优二叉树的权.4形成性考核作业6 5341710557 17 312权为四、证 明题 32*5+3*5+5*4+7*3+17*2+31=1311.设 G 是一个 n
8、阶无向简单 图，n是大于等于3的奇数.证明图G与它的补图G中的奇数度 顶点个数相等.证明：设G ? V , E ? , G ? V , E? ? .则E ? 是由n阶无向完全图K n的边删去E所得到的.所以对于任意结 点u ? V , u在G和G中的度数之和等于u在K n中的度 数.由于n是大于等于3的奇数，从而K n的每个结点都是偶 数度的(n ? 1 (? 2)度)，于是若u ? V在G中是奇数度结点, 则它在G中也是奇数度结点.故图G与它的补图G中的奇数度结 点个数相等.5形成性考核作业*2,设连通图G有k个奇数度的结点，证明 在图G中至少要添加使其成为欧拉图.k条边才能2证明：由定 理3. 1.2,任何图中度数为奇数的结点必是偶数，可知k是偶数.又 根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不 含奇数度结点.因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图.故最少要加k条边到 图G才能使其成为欧拉图.26