《2014年电大离散数学形成性考核作业5答案(图论部分)》由会员分享，可在线阅读，更多相关《2014年电大离散数学形成性考核作业5答案(图论部分)（6页珍藏版）》请在金锄头文库上搜索。
1、 形成性考核作业 1电大离散数学作业 5离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共 3 次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。要求：将此作业用 A4 纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010 年 12 月 5 日前完成并上交任课教师（不收电子稿）。并在 05 任务界面下方点击“保存”和“交卷”按钮，以便
2、教师评分。一、填空题1已知图 G 中有 1 个 1 度结点，2 个 2 度结点， 3 个 3 度结点，4 个 4 度结点，则 G 的边数是 15 2设给定图 G(如右由图所示)，则图 G 的点割集是f 3设 G 是一个图，结点集合为 V，边集合为 E，则G 的结点 度数之和 等于边数的两倍4无向图 G 存在欧拉回路，当且仅当 G 连通且 等于出度 5设 G=是具有 n 个结点的简单图，若在 G 中每一对结点度数之和大于等于 n-1 ，则在 G 中存在一条汉密尔顿路6若图 G=中具有一条汉密尔顿回路，则对于结点集 V 的每个非空子集 S，在 G 中删除S 中的所有结点得到的连通分支数为 W，则
3、S 中结点数|S| 与 W 满足的关系式为 W(G-V1) V1 7设完全图 K 有 n 个结点(n2)，m 条边，当 n 为奇数 时，K 中存在欧拉回路n8结点数 v 与边数 e 满足 e=v-1 关系的无向连通图就是树9设图 G 是有 6 个结点的连通图，结点的总度数为 18，则可从 G 中删去4 条边后使之变成树10设正则 5 叉树的树叶数为 17，则分支数为 i = 5 二、判断说明题（判断下列各题，并说明理由）1如果图 G 是无向图，且其结点度数均为偶数，则图 G 存在一条欧拉回路(1) 不正确，缺了一个条件，图 G 应该是连通图，可以找出一个反例，比如图 G 是一个有孤立结点的图。
4、2如下图所示的图 G 存在一条欧拉回路姓 名： 学 号： 得 分： 教师签名： 形成性考核作业 2(2) 不正确，图中有奇数度结点，所以不存在是欧拉回路。3如下图所示的图 G 不是欧拉图而是汉密尔顿图 解：正确因为图中结点 a，b，d， f 的度数都为奇数，所以不是欧拉图。如果我们沿着(a,d,g,f,e,b,c,a)，这样除起点和终点是 a 外，我们经过每个点一次仅一次，所以存在一条汉密尔顿回路，是汉密尔顿图4设 G 是一个有 7 个结点 16 条边的连通图，则 G 为平面图解：(1) 错误假设图 G 是连通的平面图，根据定理，结点数 v，边数为 e，应满足 e 小于等于 3v-6，但现在1
5、6 小于等于 3*7-6，显示不成立。所以假设错误。5设 G 是一个连通平面图，且有 6 个结点 11 条边，则 G 有 7 个面(2) 正确根据欧拉定理，有 v-e+r=2，边数 v=11，结点数 e=6，代入公式求出面数 r=7三、计算题1设 G=，V= v 1，v 2，v 3，v 4，v 5，E = (v1,v3)，( v2,v3)，(v 2,v4)，(v 3,v4)，(v 3,v5)，(v 4,v5) ，试(1) 给出 G 的图形表示； (2) 写出其邻接矩阵；(3) 求出每个结点的度数； (4) 画出其补图的图形解：(1)G v1 v5v2v3 v4 形成性考核作业 3(2) 邻接矩
6、阵为 010010(3) v1 结点度数为 1，v 2 结点度数为 2，v 3 结点度数为 3，v 4 结点度数为 2，v 5 结点度数为 2(4) 补图图形为2图 G=，其中 V= a, b, c, d, e，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c , e), (c, d), (d, e) ，对应边的权值依次为 2、1、2、3、6、1、4 及 5，试（1）画出 G 的图形； （2）写出 G 的邻接矩阵；（3）求出 G 权最小的生成树及其权值（1）G 的图形如下：（2）写出 G 的邻接矩阵 v1 v5v2v3 v4 形成性考核作业 4（3）G
7、 权最小的生成树及其权值3已知带权图 G 如右图所示 (1) 求图 G 的最小生成树； (2)计算该生成树的权值解：(1) 最小生成树为1 2357(2) 该生成树的权值为 (1+2+3+5+7)=184设有一组权为 2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权 形成性考核作业 535251071731173465权为 2*5+3*5+5*4+7*3+17*2+31=131四、证明题1设 G 是一个 n 阶无向简单图，n 是大于等于 3 的奇数证明图 G 与它的补图 中的奇数度顶点个数相等证明：设 ， 则 是由 n 阶无向完全图 的边删去 E 所得到的所以
8、对于,VE,E nK任意结点 ，u 在 G 和 中的度数之和等于 u 在 中的度数由于 n 是大于等于 3 的奇数，从而 的每个结点都是偶数度的（ 度），于是若 在 G 中是奇数度结点，则它在 中nK1 (2)nVG也是奇数度结点故图 G 与它的补图 中的奇数度结点个数相等2设连通图 G 有 k 个奇数度的结点，证明在图 G 中至少要添加 条边才能使其成为欧拉图2k证明：由定理 3.1.2，任何图中度数为奇数的结点必是偶数，可知 k 是偶数又根据定理 4.1.1 的推论，图 G 是欧拉图的充分必要条件是图 G 不含奇数度结点因此只要在每对奇数度结点之间各加一条边，使图 G 的所有结点的度数变为
9、偶数，成为欧拉图故最少要加 条边到图 G 才能使其成为欧拉图2k 形成性考核作业 6请您删除一下内容，O(_)O 谢谢！ 【Chinas 10 must-see animations】The Chinese animation industry has seen considerable growth in the last several years. It went through a golden age in the late 1970s and 1980s when successively brilliant animation work was produced. Here ar
10、e 10 must-see classics from Chinas animation outpouring that are not to be missed. Lets recall these colorful images that brought the country great joy. Calabash Brothers Calabash Brothers (Chinese: 葫芦娃) is a Chinese animation TV series produced by Shanghai Animation Film Studio. In the 1980s the se
11、ries was one of the most popular animations in China. It was released at a point when the Chinese animation industry was in a relatively downed state compared to the rest of the international community. Still, the series was translated into 7 different languages. The episodes were produced with a va
12、st amount of paper-cut animations. Black Cat Detective Black Cat Detective (Chinese: 黑猫警长 ) is a Chinese animation television series produced by the Shanghai Animation Film Studio. It is sometimes known as Mr. Black. The series was originally aired from 1984 to 1987. In June 2006, a rebroadcasting o
13、f the original series was announced. Critics bemoan the series violence, and lack of suitability for childrens education. Proponents of the show claim that it is merely for entertainment. Effendi Effendi, meaning sir and teacher in Turkish, is the respectful name for people who own wisdom and knowle
14、dge. The heros real name was Nasreddin. He was wise and witty and, more importantly, he had the courage to resist the exploitation of noblemen. He was also full of compassion and tried his best to help poor people. Adventure of Shuke and Beita【舒克与贝塔】 Adventure of Shuke and Beita (Chinese: 舒克和贝塔) is
15、a classic animation by Zheng Yuanjie, who is known as King of Fairy Tales in China. Shuke and Beita are two mice who dont want to steal food like other mice. Shuke became a pilot and Beita became a tank driver, and the pair met accidentally and became good friends. Then they befriended a boy named Pipilu. With the help of PiPilu, they co-founded an airline named Shuke Beita Airlines to help other animals. Alt
