哈工大计算机学院集合论2009年试题

集合论与图论试题 题号 分数 一 二 三 四 五 哈工大 2009 年 秋季学期

学号 总分 姓名 本试卷满分90分-参考答案

（计算机科学与技术学院08级）

一、填空（本题满分20分，每空各1分）

1．设A,B为集合，若(A\\B)?B?(A?B)\\B，则B等于什么？ （B?? ） 2．设f:X?Y,A?X，则f?1(f(A))与A有何关系？ (f?1(f(A))?A ) 3．给定集合S??1，2，3，4，5?，找出S上的等价的关系R，此关系R能产生划分

2?，5??。 （{(1,1),(2,2),(1,2),(2,1),(3,3),(4,4),(5,5),(4,5),(5,4)}） ?3?，?4，??1，4．设R,I,N分别表示实数，整数，自然数集（包括0），定义映射f1,f2,f3， 试确定它们的性质（单射、满射、双射）。

（1）f1:R?R,f1(x)?2x； （f1 是单射 ） （2）f2:I?N,f2(x)?x ； （f2 是满射 ） （3）f3:R?R,f3(x)?x?2。 （f3 是双射 ） 5．在集合A?{1,2,?,11,12}上定义的整除关系“|” 是A上的偏序关系，则 极大元有几个？ （ 6个 ） 6．设X是一个集合，X＝n，求X上对称的二元关系有多少？（27．设R是集合X上的一个二元关系，则

（1）R是传递的充分必要条件是什么？ （R2?R ） （2）R是对称的充分必要条件是什么？ （R?R?1 ） 8．设G是有p个顶点的K?正则偶图，则p至少是多少？ （p?2K ）

第 1 页 （共 7 页）

n2?n2 ）

试 题： 班号： 姓名：

9．有n个药箱，若每两个药箱里有一种相同的药，而每种药恰好放在两个药 箱中，则

（1）每个药箱里有多少种药？ （ n?1 ） （2）n个药箱里共有多少种药？ （ n(n?1)/2） 10. 设G是无向图，有12条边，6个3度顶点，其余顶点的度数均小于3， 则G至少有多少个顶点？ （ 9 ） 11．设T是有p(p?3)个顶点的无向树且T的最大度为?(T)，则

（1）?(T)的范围为多少？ （2??(T)?p?1） （2）若?(T)?2，则T中最长路的长度为多少？ （ p?1 ） 12．设G是有8个顶点的极大平面图，则G的面数f为多少？ （ 12 ） 13．设G是(p,q)图，若q?p?1，则G的顶点连通度k(G)为多少？（ 0 ） 14．设T为任一棵正则二元树，q为边数，t(t?2)为树叶数，则q等于什么？

（q?2(t?1) ）

15．设p,q为正整数，则p,q为何值时Kp,q为欧拉图？ （p,q为偶数）

二、简答下列各题（本题满分10分）

1．设A,B,C是三个任意集合，且(A?B)?C?A?(B?C)，则A与C应 满足什么关系？说明理由。（3分） 解：C?A。

两边同并上A有：A?((A?B)?C)?A?[A?(B?C)]?A，

[A?(A?B)]?C?A?C?A；即C?A。

2．设R为X上的二元关系，若R??且R是反自反的和传递的，则R是

第 2 页 （共 7 页） 试 题： 班号： 姓名：

反对称的吗？说明理由。（3分）

证：若R不是反对称的，则?x,y?X,使得(x,y),(y,x)?R,由R的传递性有：

(x,x)?R，与R是反自反的矛盾。于是R是反对称的二元关系。

3．设N?{1,2,3,?}，试构造两个映射f和g：N?N，使得f?g?IN， 但g?f?IN。（4分）

解：fg?IN但gf?IN，故f是满射，但f不是单射。于是令：

f:N?N,f(1)?1,f(n)?n?1,n?2，g:N?N,?n?N,g(n)?n?1，则

fg?IN但gf?IN。

三、简答下列各题（本题满分15分）

1．何谓强连通有向图？何谓有向图的强支？（2分）

解：设D＝（V,A）是有向图，若?u,v?V，u与v互达，则称D是强连通的有向图；

有向图D的极大强连通子图称为D的一个强支。

2．至少要删除多少条边，才能使Kp(p?2)不连通且其中有一个连通分支恰有k 个顶点(0?k?p)？（3分）

证：要使删除边后的图边数最多，则删除的边最少。则至少应该删除的边数为：

p(p?1)k(k?1)(p?k)(p?k?1)???k(p?k)。 2223．具有奇数顶点的偶图是否是哈密顿图？说明理由。（3分）

证：设G是一个具有奇数顶点的偶图，则G的顶点集V有一个二划分，

即V?{V2,V2}且有|V1|?|V2|。

不妨设|V1|?|V2|，则有W(G?V1)?|V2|?|V1|。 由哈密顿图的必要条件可知：G不是哈密顿图。

4．设D?(V,A)是一个有向图，如图所示。写出有向图D邻接矩阵、可达矩阵

第 3 页 （共 7 页） 试 题： 班号： 姓名：

以及顶点2到4长度为2的有向通道的条数。（3分）

?00000??10000??????11110??10110?解：(1)?10000?；(2) ?10100?；0。

?????10110??00100??00001??00000?????5．设G?(V,E)是一个(p,q)图，每个顶点的度为3。则（4分） （1）若q?3p?6，则G在同构意义下是否唯一？

（2）若p?6，则G在同构的意义下是否唯一？说明理由。 解：（1）p?4,q?6，K4唯一。

（2）p?6，q?9，G不唯一。如图所示。

四、证明下列各题（本题满分25分）

1．设A,B,C,D都是非空集合，若A?B?C?D，证明：A?C，B?D。（5分） 证：因为A,B,C,D非空，所以?x?A,y?B，有(x,y)?A?B?C?D，即

x?C,y?D。因此A?C,B?D。

同理C?A,D?B。由集合相等的定义有：A?C，B?D。

2．设f:X?Y，证明：f是满射??E?2Y,f(f?1(E))?E。（5分）

证明：??y?f(f?1(E))，则?x?f?1(E)，使得f(x)?y，于是，y?f(x)?E，所以

f(f?1(E))?E。

第 4 页 （共 7 页） 试 题： 班号： 姓名：

反过来，?y?E，因为f是满射，故必有x?f?1(E)，使得f(x)?y。又x?f?1(E)， 故y?f(f?1(E))，所以E?f(f?1(E))。 因此f(f?1(E))?E。

?假设f不是满射，则?y0?Y，使得?x?X，f(x)?y。于是令E?{y0}?2Y， 有f(f?1(E))?f(f?1({y0}))?f(?)??，由题意得??E?{y0}，矛盾。 故f一定为满射。

3．证明：全体有理数之集Q是可数集。（5分）

证：因为Q?Q??Q??{0}。显然，Q?~Q?。因此只须证明Q?是可数集即可。 我们知道，每个正有理数均可写成p/q的形式，其中p与q为自然数。于是，

?p?q?N，令Aq?{p?N}，则Aq是可数集，并且Q???Aq。由定理可知，

qq?1Q?是可数集。因此，Q是可数集。

4．设R,S是集合X上的等价关系，且R?S?S?R，则（10分） （1）证明：R?S是X上的等价关系； （2）证明：(R?S)??R?S。

证：（1）由R,S是等价关系得到R?S自反的；

又由(R?S)?1?S?1?R?1?S?R?R?S，故R?S是对称的；

而(R?S)2?(R?S)?(R?S)?R?(S?R)?S?R?(R?S)?S?R2S2?R?S。 从而R?S是传递的，因此，R?S是等价关系。

（2）因为R?S是X上的等价关系，所以R?S是X上的传递关系； 又?(x,y)?R?S，有(x,y)?R或(x,y)?S。 若(x,y)?R，因为(y,y)?S，所以(x,y)?R?S；

第 5 页 （共 7 页）

本文来源：https://www.bwwdw.com/article/rvof.html