离散数学网络课程形成性考核第4次形考任务资料讲解.docx
- 文档编号:5549661
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:7
- 大小:41.99KB
离散数学网络课程形成性考核第4次形考任务资料讲解.docx
《离散数学网络课程形成性考核第4次形考任务资料讲解.docx》由会员分享,可在线阅读,更多相关《离散数学网络课程形成性考核第4次形考任务资料讲解.docx(7页珍藏版)》请在冰点文库上搜索。
离散数学网络课程形成性考核第4次形考任务资料讲解
姓名:
离散数学作业4学号:
得分:
教师签名:
离散数学图论部分形成性考核书面作业
本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、
数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练
习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄
弱知识点,重点复习,争取尽快掌握.本次形考书面作业是第二次作业,大家要
认真及时地完成图论部分的综合练习作业.
要求:
学生提交作业有以下三种方式可供选择:
1.可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有
解答过程,完成作业后交给辅导教师批阅.
2.在线提交word文档
3.自备答题纸张,将答题过程手工书写,并拍照上传.
1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结
点,则G的边数是15.
2.设给定图G(如右由图所示),则图G的点割集是
{f},{c,e}.
3.设G是一个图,结点集合为V,边集合为E,则
G的结点度数之和等于边数的两倍.
4.无向图G存在欧拉回路,当且仅当G连通且等于出度.
5.设G=
大于等于n-1,则在G中存在一条汉密尔顿路.
6.若图G=
子集S,在G中删除S中的所有结点得到的连通分支数为W,则S中结点数|S|
与W满足的关系式为W(G-V1)V1.
7.设完全图Kn有n个结点(n2),m条边,当n为奇数时,Kn中存在
欧拉回路.
8.结点数v与边数e满足e=v-1关系的无向连通图就是树.
9.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去
4条边后使之变成树.
10.设正则5叉树的树叶数为17,则分支数为i=5.
二、判断说明题(判断下列各题,并说明理由.)
1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路.
解:
不正确,缺了一个条件,图G应该是连通图,可以找出一个反例,比
如图G是一个有孤立结点的图。
2.如下图所示的图G存在一条欧拉回路.
解:
不正确,图中有奇数度结点,所以不存在是欧拉回路。
3.如下图所示的图G不是欧拉图而是汉密尔顿图.
G
解:
正确
因为图中结点a,b,d,f的度数都为奇数,所以不是欧拉图。
如果我们沿着(a,d,g,f,e,b,c,a),这样除起点和终点是a外,我们经过每个点
一次仅一次,所以存在一条汉密尔顿回路,是汉密尔顿图。
4.设G是一个有7个结点16条边的连通图,则G为平面图.
解:
错误
假设图G是连通的平面图,根据定理,结点数v,边数为e,应满足e小于
等于3v-6,但现在16小于等于3*7-6,显然不成立。
所以假设错误。
5.设G是一个连通平面图,且有6个结点11条边,则G有7个面.
解:
正确
根据欧拉定理,有v-e+r=2,边数v=11,结点数e=6,代入公式求出面
数r=7。
三、计算题
1.设G=
(v3,v5),(v4,v5)},试
(1)给出G的图形表示;
(2)写出其邻接矩阵;
(3)求出每个结点的度数;(4)画出其补图的图形.
解:
(1)
v2
(2)邻接矩阵为
00100
00110
11011
01101
00110
(3)v1结点度数为1,v2结点度数为2,v3结点度数为3,v4结点度数为2,v5结点度数为2
(4)补图图形为
v4
v3
2.图G=
(1)画出G的图形;
(2)写出G的邻接矩阵;
(3)求出G权最小的生成树及其权值.
解:
(1)G的图形如下:
2)写出G的邻接矩阵
3)G权最小的生成树及其权值
3.已知带权图G如右图所示.
(1)求图G的最小生成树;
(2)计算该生成树的权值.
(2)该生成树的权值为(1+2+3+5+7)=18
4.设有一组权为2,3,5,7,17,31,试画出相应的最优二叉树,计算该最优
二叉树的权.
权为2*5+3*5+5*4+7*3+17*2+31=131
四、证明题
1.设G是一个n阶无向简单图,n是大于等于3的奇数.证明图G与它的
补图G中的奇数度顶点个数相等.
证明:
设GV,E,GV,E.则E是由n阶无向完全图Kn的边删去E
所得到的.所以对于任意结点uV,u在G和G中的度数之和等于u在Kn中
的度数.由于n是大于等于3的奇数,从而Kn的每个结点都是偶数度的
(n1
(2)度),于是若uV在G中是奇数度结点,则它在G中也是奇数度
结点.故图G与它的补图G中的奇数度结点个数相等.
2.设连通图G有k个奇数度的结点,证明在图G中至少要添加k条边才能
2使其成为欧拉图.
证明:
由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k是偶数.
又根据定理4.1.1的推论,图G是欧拉图的充分必要条件是图G不含奇数度结
点.因此只要在每对奇数度结点之间各加一条边,使图G的所有结点的度数变
为偶数,成为欧拉图.
故最少要加k条边到图G才能使其成为欧拉图.
2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 网络 课程 形成 考核 次形考 任务 资料 讲解