离散数学试卷二试题与答案(2)

⑧?x(S(x)?Q(x) ３、１0分

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个结点的简单图，它的边数

m?'m?'12(n?1)(n?2)?2?(n?1),可得

12四、

，这与G1=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分

(n?2)(n?3)?1