离散数学习历年真题

⑤Q(a). ⑥S(a) ⑦S(a) Q(a) ⑧ x(S(x) Q(x) ３、１0分

T③④I T①I T⑤⑥I EG⑦

11分

证明 ： b1,b2 B,(b1 b2) f满射 a1,a2 A

使f(a1) b1,f(a2) b2,且f(a1) f(a2),由于f是函数, a1 a2 又g(b1) {x|(x A) (f(x) b1)},g(b2) {x|(x A) (f(x) b2)} a1 g(b1),a2 g(b2)但a1 g(b2),a2 g(b1) g(b1) g(b2)由b1,b2任意性知,g为单射。

4、8分

证明：设G中两奇数度结点分别为u 和v，若 u，v不连通，则G至少有两个连通分支G1、G2 ，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u，v一定连通。

5、8分

证明： 证G中任何两结点之和不小于n。

反证法：若存在两结点u，v 不相邻且d(u) d(v) n 1,令V1 {u,v}，则G-V1是具有n-2个结点的简单图，它的边数

为简单图的题设矛盾，因而G中任何两个相邻的结点度数和不少于n。

所以G为Hamilton图.

计算 14%

1、 7分

解：子群有<{[0]},+6>；<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z6},+6> {[0]}的左陪集：{[0]}，{[1]}；{[2]}，{[3]}；{[4]}，{[5]} {[0]，[3]}的左陪集：{[0]，[3]}；{[1]，[4]}；{[2]，[5]} {[0]，[2]，[4]}的左陪集：{[0]，[2]，[4]}；{[1]，[3]，[5]} Z6的左陪集：Z6 。

2、 7分

m'

11(n 1)(n 2) 2 (n 1)m' (n 2)(n 3) 122,可得，这与G1=G-V1为n-2个结点

四、

试卷三试题与答案