《离散数学》期终试题
南京大学计算机系 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’个顶点(0 G中边数的上限为： 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
