?0?0??1??0??00100?0110??1011?
?1101?0110??（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2
（4）补图如图十三：
图十三 4．解：（1）G的图形表示如图十四：
图十四 （2）邻接矩阵：
?0?1??1??0??11101?0011??0011?
?1101?1110??（3）粗线表示最小的生成树，如图十五
如图十五
21
最小的生成树的权为1+1+2+3=7：
5．解：（1）最优二叉树如图十六所示：
方法（Huffman）：从2,3,5,7,11,13,17 ,19,23,29,31中选2,3为最低层结点，并 从权数中删去，再添上他们的和数，即 5,5,7,11,13,17,19,23,29,31；
再从5,5,7,11,13,17,19,23,29,31中选 5,5为倒数第2层结点，并从上述数列中 删去，再添上他们的和数，即7,10,11,13, 17,19,23,29,31；
然后，从7,10,11,13,17,19,23,29,31中 上述数列中删去，再添上他们的和数，即 17,17,24,19,23,29,31； ??
65 ? 160
?
? 95
42 ? ? 34 ? ? 53
31 ? 17 ? ? ? 24 ? ? 17 23 29 19
? 10 ? ? ? 7 11 13 5 ? ?
5
? ? 2 3
选7,10和11,13为倒数第3层结点，并从 如图十六
（2）权值为：2?6+3?6+5?5+7?4+11?4+13?4+17?3+19?3+23?3+29?3+31?2 =12+18+25+28+44+52+51+57+69+87+62=505
6．解：最优二叉树如图十七
3 ? 12 ? 7 ? ? ? 4 2
? 5
? 3
? ? 1 2 如图十七 它的权为：1?3+2?3+2?2+3?2+4?2=27
五、证明题
1．证明：用反证法．设G中的两个奇数度结点分别为u和v．假设u和v不连通，即它们之间无任何通路，则G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点．这与定理3.1.2的推论矛盾．因而u和v一定是连通的．
2．证明：设G??V,E?，G??V,E??．则E?是由n阶无向完全图Kn的边删去E所得到的．所以对于任意结点u?V，u在G和G中的度数之和等于u在Kn中的度数．由于n是大于等于2的奇数，从而Kn的每个结点都是偶数度的（n?1 (?2)度），于是若u?V在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点
22
个数相等．
3．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．
又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图．
故最少要加
k条边到图G才能使其成为欧拉图． 2离散数学集合论部分综合练习
本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。
一、单项选择题
1．若集合A={a，b}，B={ a，b，{ a，b }}，则（ ）． A．A?B，且A?B B．A?B，但A?B C．A?B，但A?B D．A?B，且A?B
2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )．
A．{a，{ a }}?A B．{ a }?A C．{2}?A D．??A
3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}?A B．{2}?A
C．{a}?A D．??A
4．若集合A={a，b，{ 1，2 }}，B={ 1，2}，则（ ）． A．B ? A，且B?A B．B? A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )．
A．{{1}, {a}} B．{?,{1}, {a}}
C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（ ）．
A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={
A．自反的 B．对称的 C．传递且对称的 D．反自反且传递的
8．设集合A = {1，2，3，4，5，6 }上的二元关系R ={?a , b??a , b?A , 且a +b = 8}，则R具有的性质为（ ）．
A．自反的 B．对称的
23
C．对称和传递的 D．反自反和传递的
9．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（ ）个．
A．0 B．2 C．1 D．3 10．设集合A={1 , 2 , 3 , 4}上的二元关系
R = {?1 , 1?，?2 , 2?，?2 , 3?，?4 , 4?}，
S = {?1 , 1?，?2 , 2?，?2 , 3?，?3 , 2?，?4 , 4?}，
则S是R的（ ）闭包．
A．自反 B．传递 C．对称 D．以上都不对 11．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系 的哈斯图如图一所示，若A的子集B = {3 , 4 , 5}， 则元素3为B的（ ）．
A．下界 B．最大下界 C．最小上界 D．以上答案都不对
2 4 图一 1 3 5
12．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 ( )．
A．8、2、8、2 B．无、2、无、2 C．6、2、6、2 D．8、1、6、1
13．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={,
二、填空题
1．设集合A有n个元素，那么A的幂集合P(A)的元素个数为 ． 2．设集合A＝{a，b}，那么集合A的幂集是 ． 应该填写：{?,{a,b},{a},{b }}
3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，
R?{?x,y?x?A且y?B且x,y?A?B}
则R的有序对集合为 ．
4．设集合A={0, 1, 2}，B={0, 2, 4},R是A到B的二元关系，
R?{?x,y?x?A且y?B且x,y?A?B}
则R的关系矩阵MR＝
． 5．设集合A={a,b,c}，A上的二元关系
R={,
则(R?S)1= ．
－
6．设集合A=｛a,b,c｝，A上的二元关系R={,
24
具有的性质是 ．
7．若A={1,2}，R={
9．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为 ．
三、判断说明题（判断下列各题，并说明理由．）
1．设A、B、C为任意的三个集合，如果A∪B=A∪C，判断结论B=C 是否成立？并说明理由．
2．如果R1和R2是A上的自反关系，判断 结论：“R11、R1∪R2、R1?R2是自反的” 是否
-
成立？并说明理由．
3． 若偏序集的哈斯图如图一所示，
则集合A的最大元为a，最小元不存在．
4．若偏序集的哈斯图如图二所示， 则集合A的最大元为a，最小元不存在．
图一
5．设N、R分别为自然数集与实数集，f：N →R，f (x)=x+6，则f是单射．
四、计算题
1．设集合A＝{a, b, c}，B={b, d, e}，求
（1）B?A； （2）A?B； （3）A－B； （4）B?A．
图二
2．设A={{a, b}, 1, 2}，B={ a, b, {1}, 1}，试计算
（1）（A?B） （2）（A∪B） （3）（A∪B）?（A∩B）． 3．设集合A={{1},{2},1,2}，B={1,2,{1,2}}，试计算
（1）（A?B）； （2）（A∩B）； （3）A×B．
4．设A={0，1，2，3，4}，R={
5．设A={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}，R是A上的整除关系，B={2, 4, 6}． （1）写出关系R的表示式； （2）画出关系R的哈斯图； （3）求出集合B的最大元、最小元．
6．设集合A＝{a, b, c, d}上的二元关系R的关系图 如图三所示．
（1）写出R的表达式； （2）写出R的关系矩阵；
（3）求出R2．
7．设集合A={1，2，3，4}，R={
25
a b 图三
d c