《离散数学》期终试题-计算机系-2002

南京大学计算机系 2002年7月

共10题，每题10分。

1. 设A, B, C为任意集合，证明 1.1 AB=AB  A=B

证明： 对任意x, 若xA, 则xAB=AB, xB, AB; 同理可

得: BA, A=B。  显然。

1.2 (A-B)(A-C)=  A(BC)

证明:  若A是空集，结论成立。

若A非空，任取xA, 假设xBC, 则A-B=A-C=A，与前提矛盾，xBC, A(BC)

 假设(A-B)(A-C), 任取x(A-B)(A-C), 则：xA, 但xB

且xC, x(BC), 这与A(BC)矛盾。(A-B)(A-C)= 。

2. 设RAB, SBC, TBC 2.1 证明(RS)-(RT)  R(S-T)

证明：任给(a,c), 若aA, cC, 且(a,c)(RS)-(RT), 则(a,c)RS, 但

(a,c)RT, 即存在bB, 满足：(a,b)R, (b,c)S, 但(b,c)T, 于是(b,c)S-T, (a,c)R(S-T), (RS)-(RT)  R(S-T)

2.2 举例说明上式反包含关系不成立

证明：寻找反例的线索：如果试图证明R(S-T)(RS)-(RT), (a,b)R,

(b,c)S, 但(b,c)T并不能保证(a,c)RT, 因为可能存在另一个b’B, 满足(a,b’)R, (b’,c)T。

反例：A={a}, B={b,b’}, C={c}, R={(a,b), (a,b’)}, S={(b,c), (b’,c)}, T={(b’c)}, 则(a,c)R(S-T), 但(a,c)(RS)-(RT)。

3. 设A为有穷集合，f为从A到A的映射 3.1 证明f为单射(1-1)  f为满射(onto)

证明：设|A|=n，f(A)={y|存在xA, 使得f(x)=y}

 假设f非满射，则存在xA, x不是f下任何元素的象，即

|f(A)| 假设f非单射，则存在x,yA, 满足xy, 但f(x)=f(y), 则

|f(A)|3.2 举例说明上述结论对无穷集不成立

证明：反例：令A为自然数集，f(x)=2x, 则f是单射，但非满射。

4. 写出(Z8, +8)所有子群，这里Z8={0,1,…,7}, +8为模8加法。

解：({0},+8), ({0,4},+8), ({0,2,4,6},+8), (Z8,+8), 共有4个子群。

5. 设H, K为群G的正规子群，且HK={e}, 其中e是G的单位元素，证明当hH且kK时hk=kh。

证明: 对任意hH, kK, 因为K是正规子群, hkhK=Kh, 即有k’K,

使得hk=k’h, hkh-1=k’K, 而k-1K, hkh-1k-1K。

类似地，因为H是正规子群，且h-1H，kh-1kH=Hk, 即有h’H, 使得kh-1=h’k, kh-1k-1=h’H, hkh-1k-1H。

 hkh-1k-1HK, 由已知，hkh-1k-1=e, 而hkh-1k-1= hk(kh)-1, 于是群元素hk与(kh)-1互为逆元素，由群元素逆元的唯一性可知hk=kh。

6. 设H为G的子群，证明对任何a,bG, Ha=Hb  ba-1H

证明： 对任意的hH, haHa=Hb, 存在h’H, 使得ha=h’b,

ba-1=h’-1hH

 任给xHa, 令x=ha (hH), 则xa-1=hH, 而对任意bG,

xa-1=xb-1ba-1H, 由已知ba-1H, xb-1=h(ba-1)-1H, xHb, HaHb。

任给xHb, 令x=hb (hH), 即xb-1H; 对任意aG, 由已知，ba-1H, 则xb-1(ba-1)H, xa-1H, 即xHa, HbHa。 Ha=Hb。

7. 设G是简单图，e为G的边数，v为G的点数，证明：如果e>(v2-3v+2)/2, 则G连通。

证明：假设G至少有两个连通分支，其中一个含v’个顶点(0G中边数的上限为：

v’(v’-1)/2+(v-v’)(v-v’-1)/2 = (v’-v/2)2 +(v2/4-v/2)

显然，当v’取值1或者(v-1)时，上式达到其最大值(v2-3v+2)/2, e(v2-3v+2)/2, 这与已知条件矛盾。G是连通图。

8. 证明每个3-正则图都有偶数个顶点，并画出两个互不同构的有6个顶点的3-正则图。

证明：图顶点度数总和均为偶数，任给3-正则图G，设其顶点度数和为

2m, 则顶点个数为2m/3, 这必然是整数，m=3k(k为正整数), 顶点个数为2k。

下面是两个3-正则图的例子：

这两个图不同构，右图中有三角形，左图中没有。

9. 设T是任意的无向树(顶点数n>1)，证明T的顶点集可以划分为两个非空且互不相交的子集，满足任意边的两个顶点一定分别在不同子集内。 证明：取T中任意一个顶点v, 构造VT的两个子集V1, V2如下:

V1= {u|T中uv-路的长度为偶数(包括0)} V2={w|T中vw-路的长度为奇数}

由于树中任意两个顶点之间的初级通路是存在且唯一的，上述定义是合理的。显然V1, V2均非空。

假设T中存在边e, 其端点u, w(不失一般性)均在V1中，不失一般性，设vu-路不含e边，则vu-路长度为偶数，且vu-路+e是长度为奇数的vw-路。若这是唯一的vw-路，与假设w在V2中矛盾；若这不是唯一的vw-路，则与树中任意两点之间初级通路的唯一性矛盾。V1, V2即为题目中所要求的子集。

10. 设G是无向简单图，e为G的边数，v为G的点数，证明：若e(v2-3v+6)/2,

则G含有Hamilton回路。 证明：只需证明对G中任意的不相邻顶点u,v, d(u)+d(v)n，其中n是G

的顶点个数。

任取G中的不相邻顶点u,v, 删除u,v(自然也删除了他们所关联的边)，设得到的新图为H, H含v-2个顶点，H中边数的上界是：(v-2)(v-3)/2。

H中边数为e-(d(u)+d(v)),  e-(d(u)+d(v))  (v-2)(v-3)/2, d(u)+d(v)  e-(v-2)(v-3)/2  (v2-3v+6)/2-(v-2)(v-3)/2 = v