实用标准
C. (c)只是弱连通的 D. (d)只是弱连通的
题目10 答案已保存 满分10.00
标记题目
题干
以下结论正确的是( D ). 选择一项:
A. 无向完全图都是欧拉图
B. 有n个结点n-1条边的无向图都是树 C. 无向完全图都是平面图 D. 树的每条边都是割边
离散数学作业5
离散数学图论部分形成性考核书面作业
本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业。
要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求2010年12月5日前完成并上交任课教师(不收电子稿)。并在05任务界面下方点击“保存”和“交卷”按钮,以便教师评分。
一、填空题
1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是 15 .
2.设给定图G(如右由图所示),则图G的点割集是
?f??e,c?.
3.设G是一个图,结点集合为V,边集合为E,则
G的结点 度数之和 等于边数的两倍.
文案大全
实用标准
4.无向图G存在欧拉回路,当且仅当G连通且 不含奇数度结点 . 5.设G=
6.若图G=
7.设完全图Kn有n个结点(n?2),m条边,当n为奇数时,Kn中存在欧拉回路.
8.结点数v与边数e满足 e= v-1 关系的无向连通图就是树. 9.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去 条边后使之变成树.
10.设正则5叉树的树叶数为17,则分支数为i = 4 .
二、判断说明题(判断下列各题,并说明理由.)
1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路.. 答:错误。应叙述为:“如果图G是无向连通图,且其结点度数均为偶数,则图G存在一条欧拉回路。”
2.如下图所示的图G存在一条欧拉回路.
答:错误。因为图中存在奇数度结点,所以不存在欧拉回路。 3.如下图所示的图G不是欧拉图而是汉密尔顿图.
G
答:正确。因为有4个结点的度数为奇数,所以不是欧拉图;而对于图中任意点集V中的非空子集V1,都有P(G?V1)??V1?。其中P(G?V1)是从图中删除V1结点及其关联的边。
4.设G是一个有7个结点16条边的连通图,则G为平面图. 答:错误。若G是连通平面图,那么若v?3,就有e?3v?6, 而16>3×7-6,所以不满足定理条件,叙述错误。
5.设G是一个连通平面图,且有6个结点11条边,则G有7个面.
文案大全
实用标准
答:正确。因为连通平面图满足欧拉公式。即:v?e?r?2。由此题条件知6-11+7=2成立。
三、计算题
1.设G=
(1) 给出G的图形表示; (2) 写出其邻接矩阵; (3) 求出每个结点的度数; (4) 画出其补图的图形.
答:(1) v1°
v2
° °v3
v4° °v5
?0?0?(2) A(D)??1??0??00100?0110??1011?
?1101?0110??(3) deg(v1)?1、deg(v2)?2、deg(v3)?4、deg(v4)?3、deg(v5)?2 (4) °v1
v2° °v3
v4° °v5
2.图G=
d), (b, e), (c, e), (c, d), (d, e) },对应边的权值依次为2、1、2、3、6、1、4及5,试
(1)画出G的图形; (2)写出G的邻接矩阵; (3)求出G权最小的生成树及其权值. b c 文案大全
实用标准
解:(1) 。 。 2 1 a。 6 4 2 1 3 。 。 e 5 d
文案大全
实用标准
?0?1?(2) A(D)??1??0??11101?0011??0011?
?1101?1110??(3) b。 。c
2 1 a。 1 e。 3 。d
3.已知带权图G如右图所示.
(1) 求图G的最小生成树; (2)计算该生成树的权值.
答:(1)
1 2
7
5 3
(2) 权值为18。
4.设有一组权为2, 3, 5, 7, 17, 31,试画出相应的最优二叉树,计算该最优二叉树的权.
解: 65
17 48
5 12 17 31
2 3 5 7
权值为65。 四、证明题
1.设G是一个n阶无向简单图,n是大于等于3的奇数.证明图G与它的补图G其权值为:7
文案大全
离散数学形考任务1-7试地题目及问题详解完整版
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)