2012离散数学II2试卷A答案

第 1 页 共 4 页

－――――― ― ― ― ― ― ― 室―教―场―考― ― ― ― ― ― ― ― ― ―师―教―课―任― ― ― 线 订 ： 号装证―考―准― ― ― ― ― ― ― ― ―：―名―姓― ― ― ― ― ― ― ― ― ―：―级―班 ―

中国民航学院2012－2013 学年第 1学期

《离散数学》期末试卷A

课程编号：03401519 试卷类型： 考试形式：闭卷 考试日期：2012年12月28日(15:30-17:30) 南3-203，211 题号 一 二 三 四 五 六 总分 得分 注意事项：1.试卷答在答题纸上，后一页为草稿纸，可以撕下；2.不准携带任何书籍、资料、纸张等。

一 (30分) 选择 (答案写在答题纸上)

1）下列运算中，哪种运算关于整数集不能构成半群()

(1) a 。b-max (a, b):

(2) a 。b=b;

(3) a。b=2ab; (4) a。b=∣a-b∣ 答案:〔(4)〕 2）设I是整数集，+，·分别是普通加法和乘法，则〈I，+，·〉是

(1)域

(2)整环和域 (3)整环;

(4)含零因子环.

答案〔(3)]

3）下面哪个哈斯图表示的偏序关系不能构成格如图1-1所示()

a a

b d b f c

c e e d (1) (2)

a a

b c b

d e c d e f f (3) (4)

图 1-1

第 2 页 共 4 页

答案:〔(2))

4）给定无向图G=(V,E)如图1-2所示，则其割点为（)

a1a2a4a8a3a6a5a7

图 1-2

(1) a1； (2)a5； (3 )a4； ( 4)a6 ,.答案:[(3)]

5）图1-3中哪一个图可一笔画出()

(1) (2)

(3) (4)

图 1-3

答案:[(1)」

6）完全图K4的所有非同构的生成子图中有几个是3条边的

(1) 1 ;（2）3; :( 3) 4 ;（4）2 答案:〔(2)〕

二(20分)填空(答案写在答题纸上)

1）设(G,*)是非零实数乘法群，f:G→G是同态映射F(x)=1/x，则f(G)=__,ker(f)=__

答案.(G: {1}]

2）有限群的阶数为____时，它无非平凡子群，根据_______

答案〔素数;拉格朗日定理〕

3）在任何图G=(V.E)中。结点v的度数为____________图G的最大度△

(G)=____________________.图G的最小度δ(G) =________________________ 答案.[结点u关连的边数,max{deg(v)︱v∈V};min{deg(v)v∈V))

2

第 3 页 共 4 页

4）G是有向图，当且仅当G中有一条至少通过每个结点的回路.G为

____________________图.当R仅当G中有一条通过每个结点的路时，G为________________________图 答案:〔强连通，单侧连通]

三 简答题(30分)

1) (10分) 一个群能否同构于它的一个真子群?为什么?

解:一个群能同构于它的一个真子群.例如:是群.若 令E={偶数}，则是的真子群，设f：I→E,f(k)=2k, 则与同构，即≌

2) （10分）设a，b，c，d是格的任意四个元，证明：

(a∧b)∨(a∧c)≤ a∧(b∨c)

证明：⑴ ∵ a≤a∨b a≤a∨c ∴a ≤(a∨b)∧(a∨c) ∵ b∧c≤b≤ a∨b b∧c≤c≤ a∨c ∴ b∧c ≤(a∨b)∧(a∨c)

于是有 a∨(b∧c) ≤(a∨b)∧(a∨c)

由对偶原理得 a∧(b∨c)≥ (a∧b)∨(a∧c) 。 即 (a∧b)∨(a∧c)≤ a∧(b∨c) 。

3） (10分) 有四个村庄的地下各有一个防空洞甲，乙，丙，丁，相邻两个防空洞之

间有地道相通，并且每个防空洞各有一条地道与地面相通，如图4-23所示(图中=表示地道)，能否从某一个防空洞开始，每个地道走一次且只走一次后回到该防空洞

甲乙丁丙

图 3-1

解：依题意若对四个防空洞及地面用结点表示，地道用边表示，得无向图G,如图4-24

所示则该题转为判定G中是否有偶拉回路，由图形知有四个结点的度数为奇数，故无解

甲丁地丙乙

图 3-1

.、

3

第 4 页 共 4 页

四 证明 (20分)

1） (10分) 设U是群中取定的元，在G中定义*，对任

a, b∈G, a*b=a。 u-1。b.其中u-1是u在G中的逆元，证明 是群.

证明:①任a,b∈G, a*b=a。u-1·b∈G.封闭; ②

(a*b)*c=(a.a-1.b)*c=a.a-1.b)*c=a.u-1.b.u-1.c=a.u-1.(b.u-1.c)=a.u-1.(b*c)=a*(b*c).

*可结合;

③对任a∈G.u*a=u。u-1。a=a*u u为么元;

④对任a∈G.存在a’=u.a-1.u,.使a’*a=a*a’=

u，G中元素有逆元.

由①一④所证，(G,*)是群.

2）(10分)给定图G如图3-1所示。 (1)给出G的邻接矩阵

(2)求各结点的出、入度，

(3)求从结点C出发长度为3的所有回路

abccd

图 4-1

?0.....0....1....0...0???1....0...1...0.....0??解（1）G的邻接矩阵A（G）=?0.....0.....0....1....1?

??0......0....1..1.....0???0....1.....0.....0....0???（2）各接点的入度和出度 A b c d e

入度 1 1 3 2 1 出度 1 2 2 2 1

（3）从C出发长度为3的回路有2条（c,d,d,c）和(c,e,b,c)

4