解：正确
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 ? ? v5
? ? v4 v3
(2) 邻接矩阵为
?0??0?1??0?0?0100??0110?1011?
?1101?0110??
(3) v1结点度数为1，v2结点度数为2，v3结点度数为3，v4结点度数为2，v5结点度数为2
(4) 补图图形为
v1 ? v2 ? ? v3
? v4
? v5
2．图G=
（1）画出G的图形； （2）写出G的邻接矩阵； （3）求出G权最小的生成树及其权值．
（1）G的图形如下：
（2）写出G的邻接矩阵
（3）G权最小的生成树及其权值
3．已知带权图G如右图所示．
(1) 求图G的最小生成树； (2)计算该生成树的权值．
解：(1) 最小生成树为
1
7
5 2
3
(2) 该生成树的权值为(1+2+3+5+7)=18
4．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优
二叉树的权．
63
31
1
17
1
7
5
5
2 3
权为 2*5+3*5+5*4+7*3+17*2+31=131
四、证明题
1．设G是一个n阶无向简单图，n是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等．
证明：设G??V,E?，G??V,E??．则E?是由n阶无向完全图Kn的边删去E所得到的．所以对于任意结点u?V，u在G和G中的度数之和等于u在Kn中的度数．由于n是大于等于3的奇数，从而Kn的每个结点都是偶数度的（n?1 (?2)度），于是若u?V在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点个数相等．
2．设连通图G有k个奇数度的结点，证明在图G中至少要添加使其成为欧拉图．
k条边才能2证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数． 又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．
故最少要加
k条边到图G才能使其成为欧拉图． 2离散数学作业7
姓 名： 学 号： 得 分： 教师签名： 离散数学数理逻辑部分形成性考核书面作业
本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。
要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。
一、填空题
1．命题公式P?(Q?P)的真值是 1或T ．
2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 则命题“如
果他生病或出差了，我就同意他不参加学习”符号化的结果为 （P?Q）?R ．
3．含有三个命题变项P，Q，R的命题公式P?Q的主析取范式是
(P?Q?R)?(P?Q??R) ．
4．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．” 可符号化为 ?x(P(x) ?Q(x)) ．
5．设个体域D＝{a, b},那么谓词公式?xA(x)??yB(y)消去量词后的等值式为 (A(a) ?A(b)) ?((B(a) ?B(b)) ．