离散数学网络课程形成性考核第4次形考任务资料讲解文档格式.docx
《离散数学网络课程形成性考核第4次形考任务资料讲解文档格式.docx》由会员分享,可在线阅读,更多相关《离散数学网络课程形成性考核第4次形考任务资料讲解文档格式.docx(7页珍藏版)》请在冰点文库上搜索。
![离散数学网络课程形成性考核第4次形考任务资料讲解文档格式.docx](https://file1.bingdoc.com/fileroot1/2023-5/8/b0f32c25-a375-4e93-a6f8-70d6458e4c6c/b0f32c25-a375-4e93-a6f8-70d6458e4c6c1.gif)
要求:
学生提交作业有以下三种方式可供选择:
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=<
V,E>
是具有n个结点的简单图,若在G中每一对结点度数之和
大于等于n-1,则在G中存在一条汉密尔顿路.
6.若图G=<
V,E>
中具有一条汉密尔顿回路,则对于结点集V的每个非空
子集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=<
,V={v1,v2,v3,v4,v5},E={(v1,v3),(v2,v3),(v2,v4),(v3,v4),
(v3,v5),(v4,v5)},试
(1)给出G的图形表示;
(2)写出其邻接矩阵;
(3)求出每个结点的度数;
(4)画出其补图的图形.
(1)
v2
(2)邻接矩阵为
00100
00110
11011
01101
(3)v1结点度数为1,v2结点度数为2,v3结点度数为3,v4结点度数为2,v5结点度数为2
(4)补图图形为
v4
v3
2.图G=<
V,E>
,其中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的邻接矩阵
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