哈工大2010年集合论与图论试卷

哈工大 2010 年 春季学期

哈工大2010年集合论与图论试卷

哈工大2010年集合论与图论试卷

第 1 页 (共 6 页) (计算机科学与技术学院 09级各专业)

一、填空 (本题满分 10分,每空各 1分 )

哈工大2010年集合论与图论试卷

1.设 B A , 为集合,则 A B B A = ) \(成立的充分必要条件是什么?(A B ⊆)

2.设 }2, 1{},, , 2, 1{==Y n X ,则从 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 是一个 ) , (p p 连通图,则 G 至少有多少个生成树 ? ( 3 )

8. 如图所示图 G ,回答下列问题:

(1)图 G 是否是偶图? ( 不是 )

(2)图 G 是否是欧拉图? ( 不是 )

(3)图 G 的色数为多少? ( 4 )

二、简答下列各题(本题满分 40分)

1. 设 D C B A , , , 为任意集合,判断下列等式是否成立?若成立给出证明,若不 成立举出反例。(6分)

(1) ) () () () (D B C A D C B A ⨯⨯=⨯ ;

(2) () () () () A B C D A C B D ⨯=⨯⨯ 。

解:(1)不成立。例如 }{, a c B D A ====φ即可。

(2)成立。 (, ) x y ∀∈() () 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 ⨯⨯ 。 反之, (, ) x y ∀∈() () A C B D ⨯⨯ ,有 , , , x A x B y C y D ∈∈∈∈。即

相关推荐
相关主题
热门推荐