（1）该关系具有反自反性、对称性、反对称性和传递性。 （2）该关系具有自反性、对称性、反对称性和传递性 5．（6 分） A ， B ， C ， D 是四个任意非空集合。 f 是 A 到 B 的满射， g 是 C 到 D 的
满射，且 A C B D
，定义映射 h( x)
f (x) 当x A ，试证明 h 为 A C 到
9．（6 分） G (V , E) 是一个简单连通平面图，且 |V | 7,| E | 15 。试证明它的每个面
都是由 3 条边组成。
第 1页
共 2页
10．（8 分） T (V , E) 是一棵树。试证明
（1） T 为二部图；
（2）若该棵树仅有 3 片树叶，则至少有一个顶点度数大于等于 3。
11．（6 分） T (V , E) 是一棵树， {V1,V2} 是 T 作为偶图顶点集的二分类， |V1 | V2 |，
课程名称： 离散数学
学 分： 3
考试方式： 闭卷
考试时间： 120 分钟
组卷年月： 2011 年 11 月 26 日 组卷教师：
学生姓名：
学 号：
（学生考试试卷）
试卷编号： A 满分分值： 100
审定教师：
1．（8 分）已知集合 A {{ 1}, { }}, B {{ a}} ，试求（ 1） 2 A （2） B 2 A
2．（ 6 分）已知 X , Y, Z 为三个任意的集合，试证明若 ( X Y ) ( X Z ) ，则
X YZ 3．（6 分）已知 R 是 A 上自反和对称的二元关系，试证明： t( R) 是 A 上的等价关系。
4．（8 分）已知集合 A {1,2,3,4,5} ，分别写出满足如下性质的二元关系：
则 V2 中至少有一片树叶。 12．（8 分） Q 是有理数集， Q*
Q { 0} ， x, y Q* , x y 4 xy 。证明 (Q* , ) 是群。
13．（6 分）有限群 G 的每个元素都有有限阶 , 且其阶数不超过群 G 的阶数 |G | 。
14．（6 分） ( H ,*) ， (K ,*) 是群 (G,*) 的正规子群，证明 ( H K ,*) 也是 (G ,*) 的正规子
群。
15．（6 分）设图 G (V , E) 有 n 个顶点， 2n 条边，且存在一个度数为 3 的结点，证明：
G 中至少有一个结点的度数 5。
第 2页
共 2页
g (x) 当x C
B D 满射。
6．（6 分）已知 A { x R |0 x 1} ， B { x R | 0 x 1} ，试证明 | A | | B | 。
7．（6 分） （1）画一个 11 个顶点欧拉图但非哈密尔顿图，它是简单无向图，有偶数条边；
（2）画一个 11 个顶点哈密尔顿图但非欧拉图，它是简单无向图，有奇数条边。 8．（8 分）有 60 个人围坐一圆桌，边开会边交流网球技术。已知这 60 个人中，每个 人至少与其余 30 个人打过球，试问是否有一种坐法，使每个人左、右两人都和他打 过球？试用图论的语言证明之。