离散数学
三、证明 46%
1、 设R是A上一个二元关系，
S { a,b |(a,b A) (对于某一个c A,有 a,c R且 c,b R)}试证
明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分）
2、 用逻辑推理证明：
所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）
3、 若f:A B是从A到B的函数，定义一个函数g:B 2对任意b B有
Ag(b) {x|(x A) (f(x) b)}，证明：若f是A到B的满射，则g是从B到 2
A
的单射。（10分）
4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）
5、 设G是具有n个结点的无向简单图，其边数
Hamilton图（8分）
m
1
(n 1)(n 2) 22，则G是
四、计算 14%
1、 设<Z6,+6>是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，
试求出<Z6,+6>的所有子群及其相应左陪集。（7分）
2、 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）
试卷二答案：
一、 填空 20%（每小题2分）
1、 P Q；P Q2、T 3、B31 B00011111 {a4,a5,a6,a7,a8}4、
R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,
1 1 0 1 0
3>,<5,4>,<5,5>,<5,6>}； 1111
1111 0011
1111 0000 5、R={<1,2>,<1,3>,<2,1>}；
R={<1,1>,<2,2>,<3,3>} 6、a ；否；有 7、Klein四元群；循环群 8、 B 9、