资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
姓 名: 离散数学作业5
学 号:
离散数学图论部分形成性考核书面作业
本课程形成性考核书面作业共3次, 内容主要分别是集合论部分、 图论部分、 数理逻辑部分的综合练习, 基本上是按照考试的题型( 除单项选择题外) 安排练习题目, 目的是经过综合性书面作业, 使同学自己检验学习成果, 找出掌握的薄弱知识点, 重点复习, 争取尽快掌握。本次形考书面作业是第二次作业, 大家要认真及时地完成图论部分的综合练习作业。
要求: 将此作业用A4纸打印出来, 手工书写答题, 字迹工整, 解答题要有解答过程, 要求 12月5日前完成并上交任课教师( 不收电子稿) 。并在05任务界面下方点击”保存”和”交卷”按钮, 以便教师评分。
一、 填空题
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=
6．若图G=
V1 ．
7．设完全图Kn有n个结点(n时, Kn中存在欧拉回路．
8．结点数v与边数e满足 e=v-1 关系的无向连通图就是树．
2), m条边, 当 n为奇数
资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
9．设图G是有6个结点的连通图, 结点的总度数为18, 则可从G中删去
4 条边后使之变成树．
10．设正则5叉树的树叶数为17, 则分支数为i = 5 ．
二、 判断说明题( 判断下列各题, 并说明理由．)
1．如果图G是无向图, 且其结点度数均为偶数, 则图G存在一条欧拉回路．．
(1) 不正确, 缺了一个条件, 图G应该是连通图, 能够找出一个反例, 比如图G是一个有孤立结点的图。
2．如下图所示的图G存在一条欧拉回路．
(2) 不正确, 图中有奇数度结点, 因此不存在是欧拉回路。
3．如下图所示的图G不是欧拉图而是汉密尔顿图．
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, 但现在16小于等于3*7-6, 显示不成立。因此假设错误。
5．设G是一个连通平面图, 且有6个结点11条边, 则G有7个面．
(2) 正确
根据欧拉定理, 有v-e+r=2, 边数v=11, 结点数e=6, 代入公式求出面数r=7
资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
三、 计算题
1．设G=
(1) 给出G的图形表示; (2) 写出其邻接矩阵; (3) 求出每个结点的度数; (4) 形．
解: (1)
v1
v2
v 5
v3
v 4
(2) 邻接矩阵为
??00100??00110????11011?
??01101???00110??
(3) v1结点度数为1, v2结点度数为2, 数为2, v5结点度数为2
(4) 补图图形为
画出其补图的图3结点度数为3, v4结点度v
电大离散数学作业答案图论部分
