离散数学试卷B答案

离散数学试卷B答案

一、回答下列问题（每小题5分，共25分）1.设A,B为两个集合，则A?B?？

答：A?B?(A?B)?(B?A)
或A?B?(A?B)?(A?B)………5′2.正则图与完全图有什么异同？

答：对于无向简单图G=(n,m),
如果G中每一个结点均与其余n–1个结点邻接，这样的图称为完全图。 ……….1′在G中，如果每个结点次数都是d,称图G为d次正则
图。 ……….1′

………1′而
………1′而d不

也不是非自反的？

答：设R是集合A上的关系， ………1′若对任意x?A，有(x,x)?R（或xRx），则称R是自反
的。 ………1′若对任意x?A，有(x,x)?R（或），则称R是非自反
的。 ………1′若存在x?A，使(x,x)?R（或xRx），又存在y?A，使(y,y)?R（或），则称R既不是自反的也不是非自反

的。 ………2′ 二、计算（每小题10分，共20分）
1.设A?{1,2,3,4}，求出?(A)，"?"是?(A)上的关系。

B?{{1},{2},{2,3},{3,4},{1,3,4},{1,2,3,4}}，试求B的最大元素，最小元素；极大元素，极小元素。

解：???????,???1,2??,3??,4??,1,2??,1,3??,1,4??,2,3??,2,4??,3,4??,1,2,3??,1,2,4

??,2,3,4??,1,3,4??,1,2,3,4??

………5′B中最大元素是{1,2,3,4}，………1′

………1′B中………1′B中极小元

2′?(P?Q)?(?Q?Q)?(P??P)?(?Q??P) …

n(n?1)n证明在个结点的无向完全图有条边。2
证明:设一个图为?n,m?无向完全图
完全图中每个结点次数为n?1, ……2′则n个结点次数的和为:

2m??deg?vi??n?n?1? ……2′

i?1n

m?n?n?1? ……1′2
（证法二：从n个结点中任选两个连成一条边，即从n中任选2个作2C组合数n?n(n?1)。 ……5′）2

3
四、（本题10分）
G?{2m3nm,n?Z}，证明G对于数字乘法成群。证明:
(1)运算封闭,?x,y?G,x?y?G ……2′

(2)结合律,?m1,m2,m3,n1,n2,n3?Z,

?2m13n1?2m23n2??2m33n3?2m1?m2?m33n1?n2?n3?2m13n1??2m23n

2?2m33n3?

(3)单位元素e?1,?m,n?Z,有?2?m3?n?G

2m3n?1?1?2m3n?2m3n
(4)逆元??m,?n?Z,有2?m3?n?G

2m3n?2?m3?n?2?m3?n?2m3n?e?1
所以逆元存在,且为2?m3?n。

五.（本题10分）
证明：如果R是拟序，则R?1也是拟序。证明：设R是A上的一个关系

因R是拟序，?x,y,z?A
当?x,y??R,?y,z??R，则必有?x,z??R于是，?y,x??R?1，?z,y??R?1,?z,x??R即R?1是传递的. 5分若?x,x??R,那么?x,x??R?1 即R?1是非自反的.

?R?1也是拟序关系. 5分 4……2′3′.…………

六、（本题5分）
设A=?0,1?，B=（,]，证明 A?B
证明：作A与B的1?1对应：

??x???x?

所以，A?B。

七.（本题10分）
在每个区域至少由5条边围成的简单连通平面图G=（n，m）中，证明m??n?2?。（n≥5）
证明：

设图G有r个区域，则围城这个区域所用的边数为5r个， 1分因为每条边在这些区域中最多出现两次 1分
所有围城这些区域的边之和5r?2m, 2分
再由欧拉定理有

n?m?r?2 ? r?2?n?m		3 分	1 分
5?2?n?m??2m 1142141253
.	2 分

?m?5?n?2?3
八、（本题10分）
设

??14

?23314, ??1235 ??213244?
计算??, ??1, ??1??1。

12???解：14

?1?234, ?314?33???124, 2分2

???1??1??11243342?,