内容发布更新时间 : 2024/6/29 9:02:49星期一 下面是文章的全部内容请认真阅读。

哈工大 2007 年 秋季学期

集合论与图论 试题A 题号 分数 一 二 三 四 总分 班号 姓名 本试卷满分90分

(06级计算机、信息安全专业、实验学院)

一、判断对错(本题满分10分,每小题各1分) ( 正确画“√”,错误画“×”)

1.对每个集合A,{A}?2A。 (×) 2.对集合P,Q,若P?Q?Q,P?Q??,则P??。 (√) 3.设f:X?Y,A?X,若f(x)?f(A),则x?A。 (×) 4.设f:X?Y,B?Y,则有f(f?1(B))?B。 (×)

5.若R是集合X上的等价关系,则R2也是集合X上的等价关系。 (√) 6.若f:X?Y且f是满射,则只要X是可数的,那么Y至多可数的。(√) 7.设G是有10个顶点的无向图,对于G中任意两个不邻接的顶点u和v, 均有degu?degv?9,则G是哈密顿图。 (×) 8.设A?(aij)是p个顶点的无向图G的邻接矩阵,则对于G的顶点vi, 有degvi??aij成立。 (√)

j?1p9.设G是一个(p,q)图,若q?p?1,则?(G)?[2p/q]。 (×) 10.图G和G1同构当且仅当G和G1的顶点和边分别存在一一对应关系。(×)

第 1 页 （共 6 页）

试 题： 班号： 姓名：

二.填空(本题40分,每空各2分)

1.设S?{?,{?}},则2S? {?,{?},{{?}},{?,{?}}} 。

2.设A,B是任意集合,若A\\B?B,则A与B关系为 A?B?? 。 3.设X?{a,b,c},Y?{0,1},Z?{2,3};f:X?Y,f(a)?f(b)?0,f(c)?1, g:Y?Z,g(0)?2,g(1)?3,则g?f(a)，g?f(c)分别为 2,3 。

4.设X和Y是集合且X?m,Y?n,若m?n,则从X到Y的单射的 个数为 Cnmm! 。

5.设X?{1,2,?,n},B?{1,2},则从X到Y的满射的个数为 2n?2 。 6.设X?{1,2,3,4},R?{(1,2),(2,2),(3,4)},S?{(2,3),(3,1),(4,2)},则 R?(S?R)? {(1,4),(2,4),(3,2)} 。

?12345??12345??12345?7.设?1???32514??,?2???43215??,则?1?2???23541?? 。

??????8.设X?{a,b,c,d},R?{(a,b),(b,c),(c,a)},则

R??{(a,a),(b,b),(c,c),(a,b),(a,c),(b,c),(b,a),(c,a),(c,b)} 。 9.设X为集合且X?n,则X上不同的自反或对称的二元关系的个数 为 2n2?n?2n2?n2?2n2?n2 。

10.设X?{a,b,c,d},A?{{a,b},{c},{d}}是X的一个划分,则由A确定的

X上的等价关系为 {(a,a),(b,b),(a,b),(b,a),(c,c),(d,d)} 。 11.S?{1,2,?,10},在偏序关系“整除”下的极大元为 6,7,8,9,10 。 12.给出一个初等函数f(x),使得它是从(0,1)到实数集合R的一一对应,

这个函数为 ctg?x或-ctg?x或tg(?x??/2) 。 13.设G是(p,p)连通图,则G的生成树的个数至多为 p 。

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

14.含5个顶点、3条边的不同构的无向图个数为 4 。

15.设无向图G有12条边,有6个3度顶点,其余顶点度数均小于3,则G中

顶点数至少为 9 。 16.由6个顶点,12条边构成的平面连通图G中,每个面由 3 条边围成。 17.若Kp为平面图,则p的取值为 ?4 。

18.包含完全图Kp作为子图的无向图的顶点色数至少为 p 。

19.有向图的可达矩阵R?(rij)中,若rij?rji?1,则顶点vi与vj之间是 互达 。 20.高为h的r(r?2)元正则树至多有 rh 片树叶。

三、证明和计算(本题40分,每小题各5分)

1.设A,B,C是三个任意集合,证明：A?(B\\C)?(A?B)\\(A?C)。

证：设 (x,y)?A?(B\\C),则x?A,y?B\\C,从而x?A,y?B,y?C。 于是(x,y)?A?B,(x,y)?A?C,因此(x,y)?(A?B)\\(A?C),即

A?(B\\C)?(A?B)\\(A?C)。

反之,设(x,y)?(A?B)\\(A?C),有(x,y)?(A?B),(x,y)?(A?C),从而

x?A,y?B,y?C,故x?A且y?B\\C。于是(x,y)?A?(B\\C), 即(A?B)\\(A?C)?A?(B\\C)。

因此,A?(B\\C)?(A?B)\\(A?C)。

2.设N?{0,1,2,?},f,g:N?N,?n?N,f?n??n?1,g?n??max?0,n?1?。证明： (1)f是单射而不是满射;(2)g是满射而不是单射;(3)gf?IN,但fg?IN; 证：(1)若f?n??f?m? ,则n?1?m?1,从而n?m,故f为单射;但0不存在

原象,故f不是满射。

(2) ?n?N,g?n?1??n,n?0,故g是满射;但g?0??g?1?,故g不是单射。 (3) gf?x??g?f?x???max?0,f?x??1??max?0,x??x?IN?x?,故fg?IN。

但fg?0??f?g?0???1?IN(0),故fg?IN。

第 3 页 （共 6 页）