本试卷满分90分
(计算机科学与技术学院0９级各专业)
--
一、填空（本题满分１0分,每空各1分)
1.设A,B为集合,则(A\\B)?B?A成立的充分必要条件是什么？(B?A) ２.设X?{1,2,?,n},Y?{1,2},则从X到Y的满射的个数为多少?（2n?2 ) ３．在集合A?{2,3,4,8,9,10,11}上定义的整除关系“|”是A上的偏序关系， 则( 无 ）
4．设A?{a,b,c}，给出A上的一个二元关系,使其同时不满足自反性、反自 反性、对称性、反对称和传递性的二元关系。(R?{(a,a),(b,c),(c,b),(a,c)}） ５．设?为一个有限字母表,?上所有字(包括空字）之集记为??，则??是 否是可数集? （ 是 )
６.含5个顶点、3条边的不同构的无向图个数为多少？ （ ４ ） 7.若G是一个(p,p)连通图，则G至少有多少个生成树? （ 3 ） 8. 如图所示图G,回答下列问题：
(１）图G是否是偶图? ( 不是 )
(2）图G是否是欧拉图? ( 不是 ） (3)
图最
大
元
是
什
么
?
G的色数为多少？
( 4 )
二、简答下列各题（本题满分40分）
1．设A,B,C,D为任意集合，判断下列等式是否成立?若成立给出证明，若不 成立举出反例。(6分)
(1)(A?B)?(C?D)?(A?C)?(B?D)； （2）(AB)?(CD)?(A?C)(B?D)。 解:（1）不成立。例如A?D??,B?c?{a}即可。 （2）成立。?(x,y)?(AB)?(C(x,y)?(A?C)(B?D),从而(AB)?(C(x,y)?(AB)?(CD)，有x?AB,y?CD)?(A?C)(B?D)。
D，即
x?A,x?B,y?C,y?D。所以(x,y)?A?C,(x,y)?B?D,因此
反之,?(x,y)?(A?C)(B?D)，有x?A,x?B,y?C,y?D。即
D)，从而(A?C)(B?D)?(AB)?(C--
D)。
--
因此，(AB)?(CD)＝(A?C)(B?D)。
2. 设G是无向图,判断下列命题是否成立？若成立给出证明，若不成立举出 反例。（6分）
（1）若图G是连通图，则G的补图GC也是连通图。 (2)若图G是不连通图，则G的补图GC是连通图。 解：(1）GC不一定是连通图。 (2）GC一定连通图。
因为G不连通，故G至少有两个分支,一个是G1,另外一些支构成的子图是G2。 对于Gc中任意两个顶点u和v:
（１）若u?V1,v?V2,则u与v不在G中邻接。由补图的定义可知:u与v必在Gc
中邻接;
（2)若u,v?V1(或V2),取w?V2(或V2),则u与w，w与v在G都不邻接，故u 与w，w与v在Gc必邻接,于是uwv就是Gc中的一条路。
综上可知,对Gc中任两个顶点u和v之间都有路连接，故Gc是连通的。 3.设集合A?{a,b,c,d,e},A上的关系定义如下：(6分）
R?{(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),
(b,e),(c,c),(c,e),(d,d),(d,e),(e,e)}。 则
（1)写出R的关系矩阵; (2)验证(A,R)是偏序集； （３)画出Hasse图。 解：（１)R所对应的关系矩阵为MR为:
e ?111??011MR??001??000?000?(2）由关系矩阵可知：
11??01?01?
?11?01??d b a c
对角线上的所有元素全为1,故R是自反的;rij?rji?1，故R是反对称的;
R2对应的关系矩阵MR2为:MR2?1??0??0??0?0?1111??1101?0101??MR。
?0011?0001??因此R是传递的。
综上可知：故R是A上的偏序关系，从而(A,R)是偏序集。
--
--
（3)(A,R)对应的Hasse图如图所示。 4．设A是有限集合,f:A?A。则(３分)
（1)若f是单射，则f必是满射吗？反之如何？ （2)若A是无限集合，结论又如何？
解：(１)f是单射，则f必是满射；反之也成立； （2）若A是无限集合,结论不成立。 举例:令N={1，２，3，…｝,则
(１）设s:N?N，?n?N,S(n)?n?1。显然,S是单射，但不是满射。 (2）设t:N?N,?n?N,t(1)?1,t(n)?n?1,n?2。显然,T是满射，
但不是单射。
5．（4分）
（１）根据你的理解给出关系的传递闭包的定义；
(２）设A?{a,b,c,d},A上的关系R?{(a,b),(b,c),(c,a)}，求关系R的传递闭包R?。 解：（1)设R是集合A上的二元关系，则A上包含R的所有传递关系的交称为
关系R的传递闭包。
（２)R??{(a,a),(b,b),(c,c),(a,b),(a,c),(b,a),(b,c),(c,a),(c,b)}
６.由６个顶点，１2条边构成的平面连通图G中,每个面由几条边围成?说明 理由。（４分)
解:每个面由3条边围成。
在图G中，p?6,q?12,根据欧拉公式p?q?f?2，得f?8。
因为简单平面连通图的每个面至少由3条边围成，所以假设存在某个面由大于 ３条边围成，则有:3f?2q,即24?24，矛盾。
故每个面至多由3条面围成,于是G中每个面由3条边围成的。
7．设G?(V,E)是至少有一个顶点不是孤立点的图。若?v?V,degv为偶数，则G 中是否必有圈?说明理由。(4分) 解: G中必有圈。
令P是G中的一条最长的路,P:v1v2vn,则由degv1?2知，必有某个顶点u与vi邻接。由于P是最长路，所以u必是v3,v4,,vn中的某个vi,i?3。于是，v1v2viv1是G的一个回路。
8.设T是一个有n0个叶子的二元树，出度为２的顶点为n2,则n0与n2有何关系？ 说明理由。（４分）
解:n0与n2的关系为：n0?n2?1
--
哈工大年集合论与图论试卷
