2008-2009第一学期期末考试离散数学试卷答案B
一. 选择题
1.C 2.A 3.D 4.A
二. 填空题：
5. 不是 6. 奇数 7. 5 8. (?P??Q)?(P?Q) 9. ?P 10.?P 11.0 三. 计算题：
12.n(n-1)
13. A(1)?P(1)?Q(1)?(1?2?1?0)?T
A(2)?P(2)?Q(2)?(2?2?2?0)?T
因此A(x)在所给的客体域下真值为T 14．（1）n阶无向完全图有
n(n?1), n阶有向完全图有n(n?1). 2 （2）共有n?m条边
（3）共有nk/2条边
15.设有x片树叶，则顶点总数为2+1+3+x，边的数目为5+ x,顶点度数之和为 2*2+3*1+4*3+x*1=19+x
由握手定理有： 19+x=2(5+x) 解得： x=9
?1?116. (1)关系矩阵为：??0??1 （2）关系图为：
110000101?0?? 0??1?
（3）关系F是自反的，对称的。
四．
17、有幺元为0，零元为1，0和1是等幂元。 18、可以构成一个格。运算表如下： + a b a b · a b a b a a a b b b a b
19、由已知，证明对任意的a，b，都有a*b= b*a
20. a) For any two people a and b at this party, a and b either shake hands or they do
not. Therefore, we can represent this party as a simple graph G = (V, E), where V is the set of people attending the party, and edges E connecting people a and b if and only if a and b shake hands. Then the degree of a vertex a indicates with how many other people the person a shakes hands, since the person is not assumed to shake their own hand (so there are no loops). According to the handshaking theorem, the sum across all party guests of the number of people they shake hands with is then equal to twice the number of handshakes that take place:
Since e, the number of edges, is an integer, 2e is an even number, and therefore the sum across all party guests of the number of people they shake hands with is an even number.
b) If we name the vertices a, b, c, d, and e, we obtain the following directed multigraph:
c) K3 has the following seven nonisomorphic subgraphs:
All other subgraphs of K3 are isomorphic to one of these seven graphs.
21.
A?B?C?{(0,1,0),(0,1,1),(0,1,2),(0,2,0),(0,2,1),(0,2,2),(1,1,0),
(1,1,1),(1,1,2),(1,2,0),(1,2,1),(1,2,2)}五. 22.正确（从同构的角度说明理由）
23.错误(举反例) 24.错误(举反例)