5.设G为(n,m)图，则图中结点度数的总和为 。2m
6.设图G有6结点，若各结点的度数分别为：1，4，4，3，5，5，则G共有 条边。 用握手定理 22?2m，m=11
7. 图G为欧拉图的充分必要条件是_____________________. G为无奇度结点的连通图 四、解答题
1. 对下图所示的图G，求 （1）G的邻接矩阵A；
（2）G的结点v1,v3之间长度为3的通路； （3）G的连接矩阵C； （4）G的关联矩阵M。
v1v1?0?v2?1解 （1） A=
v3?1?v4?1v5??0（2） 因为
v2v3v4v51110??0101? ?.1011?0100?1100???3??1 A2=?2??1?2?1322122411121212?????1???3
1?, A=????1?????2????7??????????????,
????????????所以，结点v1,v3之间长度为3的通路共有7条，它们是
v1v3v1v3,v1v2v5v3,v1v2v1v3,v1v4v1v3,v1v3v5v3,v1v3v2v3,v1v3v4v3.
（3）由于图G是连通的，所以
v1v211111v311111v411111v5
1??1?1?. ?1?1??v1?1?v2?1 C=v3?1?v4?1v5??1（4） e1e2e3e4e5e6e7
11
v1?1?v2?1 M=v3?0?v4?0v5??001100101001001000110001010??1?0?. ?0?1??2. 在下面的有向图D中，回答下列问题
（1）写出图D的邻接矩阵A；
（2）写出结点v1到结点v3的长度为3的所有有向通路； （3）写出结点v5到自身的长度为3的所有有向回路；
?0??1解：（1）A??0??0?0??0??02（2）A??0??0?1?0001??0100?0110?
?0001?1010??1010??10??0111??010111? A3??01??1010??10?010101???101??121?121?
?101?121??所以结点v1到结点v3的长度为3的所有有向通路只有一条: v1v5v2v3
（3）结点v5到自身的长度为3的所有有向回路只有一条：v5v2v1v5
3.在下面的无向图G中，回答下列问题
a e
d
b c
（1）写出a,d之间的所有初级通路；
12
（2）写出a,d之间的所有短程，并求d(a,d)； （3）判断无向图G是否为欧拉图并说明理由。 解（1）a,d之间的所有初级通路共有7条，分别为
aed，aecd，aebcd，abed，abcd，abecd，abced （2）a,d之间的长度最短的通路只有1条，即aed，因而它是a,d之间
唯一的短程，d(a,d)?2 （3）由于无向图G中有两个奇度顶点deg(b)?3,deg(c)?3，所以无向图G没有欧
拉回路，因而不是欧拉图。
第四章 数理逻辑
一、判断题 （1）“如果8＋7＞2，则三角形有四条边”是命题． （ 对 ） （2）设P,Q都是命题公式，则P?Q也是命题公式． （ 错 ） （3）命题公式P,Q的真值分别为0，1，则P?Q的真值为0
（以上是在对P,Q所包含的命题变元的某个赋值下）． （ 错 ） （4）设p:他生于1963年,q:他生于1964年，则命题“他生于1963年或1964年”可以符号化为p?q. （ 对 ） （5）设P，Q都是命题公式，则P?Q的充分必要条件为P?Q?1.（ 对 ） （6）逻辑结论是正确结论． （ 错 ） （9）设A,B,C都是命题公式，则
(A?B??C)?(A?C)
也是命题公式． （ 对 ） （10）命题公式P,Q的真值分别为0，1，则P?Q的真值为0
（以上是在对P,Q所包含的命题变元的某个赋值下）． （ 对 ） 二、单项选择题
（1）下面哪个联结词不可交换 （ B ） A. ?； B．?； C.?； D.? .
（2）命题公式(p?(p?q))?q是 （ C ） A. 永假式； B．非永真式的可满足式； C. 永真式； D. 等价式.
（3）记p:他懂法律，q:他犯法，则命题“他只有懂法律，才不会犯法”可符号化为（ B ）. A．p??q B．?q?p
13
C．q??p D．p?q
（4）下列命题中假命题是（ B ）. A．如果雪不是白的，则太阳从西边出来 B．如果雪是白的，则太阳从西边出来 C．如果雪不是白的，则太阳从东边出来 D．只要雪不是白的，太阳就从西边出来
（5）设A，B都是命题公式，则A→B为可满足式是A?B的（ B ）. A．充分而非必要条件 B．必要而非充分条件 C．充分必要条件
D．既非充分又非必要条件 三、填空题
1.设p: 天气很冷，q:老王还是来了，则命题“虽然天气很冷, 但老王还是来了”符号化为 .p?q 2. 记p:他学好“离散数学”，q:他学好“程序设计”，则命题“他只有学好‘离散数学’，才能学好‘程序设计’”可以符号化为______________；命题“他只要学好‘离散数学’，就能学好‘程序设计’”可以符号化为_______________________. 填 q?p,p?q
3.设p:天下雨，q: 我骑自行车上班，则命题“如果天不下雨, 我就骑自行车上班”符号化为 .?p?q
4. 设p,q的真值为0，r,s的真值为1，则命题公式(p?r)?(?q?s)的真值为 .0 5.设p,q的真值为0，r的真值为1，则命题公式p?(q?r)的真值为 .0
14