离散数学期末考试试题与答案

离散参考试卷

离散数学期末考试2007年元月8日

离散参考试卷

1. (6分) 已知 A={{a},a,b}, B={{b}, a}, 求 A×B, A⊕B, P(A). 分 × ⊕ 解: A×B={({a},{b}), ({a},a), (a, {b}), (a, a), (b, {b}), (b, a)} × A⊕B=(A-B) ∪(B-A)={{a}, b, {b}} ⊕ P(A)={Ø, {a}, a, b, {{a}, a}, {{a},b}, {a,b}, A}.

离散参考试卷

2. (4分) 已知 1,R2是A上的对称关系 R1°R2对称吗 证明或 上的对称关系, 对称吗? 分 已知R 上的对称关系 举反例说明. 举反例说明 一般地, 解: 一般地 R1°R2≠ R1°R2. 反例: 反例 R1={(1,3), (3,1)} 对称 对称! R2={(3,2), (2,3)} 对称! 对称! R1°R2 ={(1,2)} 不对称 不对称!

离散参考试卷

3. (6分) G是一个群 H是G的子群 g1,g2 G, (g1,g2) R 是一个群, 的子群. 分 是一个群 是 的子群 g1g2-1 H. 证明 是G上等价关系 证明R是 上等价关系 上等价关系. 证明: 对于任意的a , 证明 ◆对于任意的 G,∵ a·a-1=e H, , 是自反的。 ∴ (a,a) R,故R是自反的。 , 是自反的 对于任意的a, , ◆对于任意的 ，b G,若(a,b) R, , ∴ a·b-1 H,∴(a·b-1)-1=b·a-1 H, , , 是对称的。 ∴ (b,a) R,故R是对称的。 , 是对称的 对于任意的a,b,c G, R, R, ◆对于任意的a,b,c G,若(a,b) R,(b,c) R, ∴ a·b-1 H且 b·c-1 H, 且 ， ∴ (a·b-1)·(b·c-1)=a·c-1 H, , 是传递的。 ∴ (a,c) R,故R是传递的。 , 是传递的

离散参考试卷

4. (6分) A={1,2,3,5,10,15,30}, x,y A, x y x|y. 分 (1) 画出 画出(A, )的哈斯图 的哈斯图 (2) 判断 判断(A, )是格否 分配格吗 有补格 布尔格吗 是格否?分配格吗 有补格?布尔格吗 是格否 分配格吗?有补格 布尔格吗?

30 10 15

2

5

3

格? 分配格? 分配格 ? 有补格? 有补格 布尔格

1

离散参考试卷

5. 已知 f: A→B, g: B→C, f是单射 是单射,证明 °f 是单射,g是单射 证明g° 是单射 是单射 证明 是单射. 是满射,证明 是满射. 是单射 若g°f是满射 证明 是满射 ° 是满射 证明g是满射证明: 对于任意的x 证明 (1) 对于任意的 1,x2 A, 若g°f (x1)= g°f (x2), ° ° 即有 g(f(x1))= g(f(x2)). 由于g是单射 故有f(x 是单射,故有 由于 是单射 故有 1)=f(x2). 由于f是单射 故有x 是单射,故有 由于 是单射 故有 1=x2. 因而, ° 是单射. 因而 g°f 是单射 (2) 对于任意z C, 存在x A, 使得 对于任意z 存在x g°f (x)=z, ° 即 g(f(x))=z. 故存在 y=f(x) B, 使得 g(y)=z. 是满射. 故 g是满射 是满射

离散参考试卷

6. (4分) 已知 A是可数无限集，B是有限集， 且A∩B=Ø, 是可数无限集， 是有限集 是有限集， 分 已知: 是可数无限集 ， 求证： 求证：|A|=|A∪B| ∪ 证明: 证明 不妨记 A={a1, a2, a3, …,an, …} B={b1, b2, b3, …, bm} 作映射 φ: A→A∪B ∪ φ(ai)=bi (i=1,…,m) φ(ai)=ai-m (i=m+1,m+2,…) 则可以说明φ为 的双射， 则可以说明 为A→A∪B的双

射， ∪ 的双射 故结论得证。 故结论得证。 也是可数无限集， (如果只用一句话说， A∪B也是可数无限集，可以得 分) 如果只用一句话说， ∪ 也是可数无限集 可以得2分

离散参考试卷

7. (5分) 画出 个顶点的自互补图。证明当 个顶点的自互补图。 分 画出5个顶点的自互补图 证明当n=4k 或4k+1时才 时才 若一个图和它的补图同构，说它是自互补图。 有. 若一个图和它的补图同构，说它是自互补图。 解:(1)

(2)因为n个顶点的无向完全图有n(n-1)/2个边，所以 因为n个顶点的无向完全图有n(n-1)/2个边， n(n 个边 自互补图各有n(n 1)/4个边 因此，n=4k或4k+1。 n(n个边， 自互补图各有n(n-1)/4个边，因此，n=4k或4k+1。

离散参考试卷

8. (5分) 证明 G或者 有一个是连通图。 或者G有一个是连通图 分 证明: 或者 有一个是连通图。 证明：因为 不连通 不连通， 可以分为若干连通子图: 证明：因为G不连通，则G可以分为若干连通子图 可以分为若干连通子图 G1=(V1,E1), ,Gn=(Vn,En) ),--( , ), ( , ) 根据G的补图的构造过程知 的补图的构造过程知V1中每个顶点与其它 根据 的补图的构造过程知 中每个顶点与其它 顶点集V2, 中顶点有边相连。 顶点集 ，--- ,Vn中顶点有边相连。 这样， 在 中顶点有边相连 这样， G的补图中，有 的补图中， 的补图中 分别属于两个顶点子集Vi与 中的任意两个顶点 分别属于两个顶点子集 与Vj中的任意两个顶点 之间有边直接相连， 之间有边直接相连， 属于同一个顶点子集Vi的任意两个顶点借助顶点 属于同一个顶点子集 的任意两个顶点借助顶点 子集Vj的任意一个顶点连通 的任意一个顶点连通。 子集 的任意一个顶点连通。 所以，根据连通的定义知： 的补图一定连通 所以，根据连通的定义知：G的补图一定连通 。

离散参考试卷

9. (4分) 一个有奇数条边、偶数个顶点的欧拉图，但不是哈 一个有奇数条边、偶数个顶点的欧拉图， 密尔顿图。 密尔顿图。

离散参考试卷

10 (6分) 画出 4,4,判断 4,4是否平面图 判断K 是否平面图. 分 画出K

否!

离散参考试卷

11. (5分) 证明 多于一个顶点的树，至少有两片树叶。 分 证明: 多于一个顶点的树，至少有两片树叶。

证明： 是一棵树， 中最多只有一片树叶， 证明：设 T=(V,E)是一棵树，若T中最多只有一片树叶， 是一棵树 中最多只有一片树叶 则有

∑d(v) ≥1+2(|V|-1)=2|E|+1,矛盾! 这与结论 ∑ d(v) =2|E| 矛盾 矛盾说明 …… 此处隐藏：2063字，全部文档内容请下载后查看。喜欢就下载吧 ……