哈工大 2010 年 春季学期
集合论与图论 试题
题号
一
二
三
四
总分
分数
第 1 页 （共 6 页）
学号
姓名
本试卷满分 90 分
（计算机科学与技术学院 09 级各专业）
一、填空(本题满分 10 分，每空各 1 分)
1．设
BA,
为集合，则
ABBA =)\(
成立的充分必要条件是什么？（
AB
）
2．设
}2,1{},,,2,1{ == YnX
，则从
X
到
Y
的满射的个数为多少？（
22 −
n
）
3．在集合
}11,10,9,8,4,3,2{=A
上定义的整除关系“|”是
A
上的偏序关系，
则最大元是什么？ （ 无 ）
4．设
{ , , }A a b c=
，给出
A
上的一个二元关系，使其同时不满足自反性、反自
反性、对称性、反对称和传递性的二元关系。（
{( , ),( , ),( , ),( , )}R a a b c c b a c=
）
5．设
为一个有限字母表，
上所有字（包括空字）之集记为
，则
是
否是可数集？ （ 是 ）
6．含 5 个顶点、3 条边的不同构的无向图个数为多少？ （ 4 ）
7．若
G
是一个
),( pp
连通图，则
G
至少有多少个生成树? （ 3 )
8. 如图所示图
G
，回答下列问题：
（1）图
G
是否是偶图？ （ 不是 ）
（2）图
G
是否是欧拉图？ （ 不是 ）
（3）图
G
的色数为多少？ （ 4 ）
二、简答下列各题（本题满分 40 分）
1.设
DCBA ,,,
为任意集合，判断下列等式是否成立？若成立给出证明，若不
成立举出反例。（6分）
（1）
)()()()( DBCADCBA =
；
（2）
( ) ( ) ( ) ( )A B C D A C B D =
。
解：（1）不成立。例如
}{, acBDA ====
即可。
（2）成立。
( , )xy
( ) ( )A B C D
，有
,x A B y C D
，即
, , ,x A x B y C y D
。所以
( , ) ,( , )x y A C x y B D
，因此
( , ) ( ) ( )x y A C B D
，从而
( ) ( )A B C D
( ) ( )A C B D
。
反之，
( , )xy
( ) ( )A C B D
，有
, , ,x A x B y C y D
。即
评论0