离散数学期末试卷

一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题干后的括号内。每题2分，共20分）

1 在自然数集N上，下列哪种运算是可结合的？（ ）

A. a*bab B. a*bmax{a,b} C. a*ba2b D. a*bab(mod3) 2 下列代数系统中，哪个是群？（ ）

A. S{0,1,3,5}，*是模7加法 B. SQ（有理数集合），*是一般乘法

C. SZ（整数集合），*是一般减法 D. S{1,3,4,5,9}，*是模11乘法 3 若是的真子群，且Hn，Gm，则有（ ）。 A. n整除m B. m整除n

C. n整除m且 m整除n D. n不整除m且 m不整除n 4 下面哪个集合关于指定的运算构成环？（ ）

A. {ab32|a,bZ}，关于数的加法和乘法 B.{n阶实数矩阵}，关于矩阵的加法和乘法

a C. {ab2|a,bZ}，关于数的加法和乘法

aD. bba,bZ，关于矩阵的加法和乘法 ab e c f d g 5 在代数系统中，整环和域的关系为（ ）。

A. 域一定是整环 B.域不一定是整环 C. 整环一定是域 D. 域一定不是整环 6 N是自然数集，是小于等于关系，则(N,)是（ ）。 A. 有界格 B.有补格 C. 分配格 D. 有补分配格 7 图1-1给出的哈斯图表示的格中哪个元素无补元？（ ）

A. a B. c C. e D. f 图1-1 8 给定下列序列，可构成无向简单图的结点度数序列的是（ ）。

A.（1，1，2，2，3） B.（1，3，4，4，5） C.（0，1，3，3，3） D.（1，1，2，2，2） 9 欧拉回路是（ ）。

A.路径 B.简单回路

C.既是基本回路也是简单回路 D.既非基本回路也非简单回路

10 哈密尔顿回路是（ ）。

A.路径 B.简单回路

C.既是基本回路也是简单回路 D.既非基本回路也非简单回路

二、填空题（以下每个下划线为一空，请按要求填入合适的内容。每空2分，共30分）。

1 设S是非空有限集，代数系统(P(S),,）中，P(S)对运算的单位元是＿＿＿

＿，零元是＿＿＿＿，P(S)对运算的单位元是＿＿＿＿。

2 在运算表2-1中空白处填入适当符号，使({a,b,c},)成为群。 ①＿＿＿＿，②＿＿＿＿，③＿＿＿＿，④＿＿＿＿。 3 设H{0,4,8}，H,12是群N12,12的子群，其中

N12{0,1,2,,11}，12是模12加法，则N12,12有＿＿＿＿

a b c  a ① a ② b a b c c ③ c ④ 个真子群，H的左陪集3H＿＿＿＿，4H＿＿＿＿。 4设A,,,是一个布尔代数，如果在A上定义二元运算为：

ab(ab)(ab)，则A,是一个＿＿＿＿。

表2-1

5 任何一个具有2n个元素的有限布尔代数都是＿＿＿＿。

6 若连通平面图G有4个结点，3个面，则G有＿＿＿＿条边。

7 一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，它有＿＿＿＿个度数为1的结点。 8 无向图G是由k（k2）棵数组成的森林，至少要添加＿＿＿＿条边才能使G成为一棵树。

三、求解题（20分）

1 试写出N6,6中每个子群及其相应的左陪集。 （6分）

2 若一个有向图G是欧拉图，它是否一定是强连通的？若一个有向图G是强连通的，它是否一定是欧拉图？说明理由。 （6分） 3 有向图G如图3-1所示。

（1）求G的邻接矩阵A； （2分）

（2）G中v1到v4长度为4的路径有几条？ （2分） （3）G中v1到自身长度为3的回路有几条？ （2分）

（4）G是哪类连通图？ （2分）

四、证明题（30分）

e1 v1 e4 e3 v2 v4

e6 e7

e2 e5 图v3-1 3

1 设G,*是一群，xG。定义：aba*x*b，a,bG。证明G,也是一群。 （10分）

2 证明：

（1）证明在格中成立：(a*b)(c*d)(ac)*(bd)。 （5分） （2）证明布尔恒等式：(a*c)(a*b)(b*c)(a*c)(a*b)。 （5分）

3 证明：

（1）在6个结点12条边的连通平面简单图中，每个面由3条边围成。 （5分） （2）证明当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。 （5分）

《离散数学》期末考试试卷（A卷）参

一、单项选择

1．B; 2.D; 3.A; 4.C; 5.A; 6.C; 7.B; 8.D; 9.B; 10.C. 二、填空题

1 ，S，S； 2 c，b，b，a； 3 5，{3,7,11}，{4,8,0}； 5 同构； 三、求解题 1 解：

子群有：{0},6，{0,3},6，{0,2,4},6。

{0},6的左陪集为：{0}，{1}，{2}，{3}，{4}，{5} {0,3},64 交换群； 8 k1。

6 5； 7 9；

的左陪集为：{0,3}，{1,4}，{2,5} 的左陪集为：{0,2,4}，{1,3,5}

{0,2,4},62 答：（1）一个有向欧拉图一定是强连通图。因为G是欧拉图，存在欧拉回路C，G中的每个结点至少在C中出现一次。因而G中任意两点u，v都在C中，相

互可达，故G是强连通的。（2）一个强连通图不一定是有向欧拉图。因为强连通图中每个结点的入度不一定等于其出度。 3 解：

10（1）A00103A00200020001101410101002 A10003100 A41000200020006010301011 0141 0144可知，v1到v4长度为4的路径有条（e1e1e4e6，e4e6e7e6，（2）由A4中a14e1e2e5e6，e1e3e5e6）。

31可知，v1到自身长度为3的回路有1条（e1e1e1）（3）由A3中a11。

（4）G是单向连通图。

四、证明题

1 证明：显然是G上的二元运算（即满足封闭性），要证G是群，需证结合律成立，同时有单位元，每个元素有逆元。 a,b,cG，有

(ab)c(a*x*b)*x*ca*x*(b*x*c)a(bc) 运算是可结合的。

其次，x1是G,的单位元。事实上，aG，有

ax1a*x*x1a；x1ax1*x*aa

最后证明，aG，x1*a1*x1是a在G,中的逆元。事实上，

a(x(x11*a11*x11)a*x*x11*a1*x1x1

*a*x)ax*a1*x1*x*ax1 由以上证明，G,是群。 2 证明：

（1）(a*b)(c*d)((a*b)c)*((a*b)d) （公式(13)分配不等式）

v1

4 6

5

8

又因为a*ba，a*bb，所以(a*b)(c*d)(ac)*(bd)。 （2）因为aa1，1*(b*c)(b*c)，所以有，

(a*c)(a*b)(b*c)(a*c)(a*b)((aa)*(b*c)) (a*c)(a*b)((a*b*c)(a*b*c))

((a*c)(a*c*b))((a*b)(a*b*c)) （吸收律） (a*c)(a*b)

即等式成立。 3 证明：

（1）因图中结点数和边数分别为n6，m12，根据欧拉公式nmk2，得k8。又deg(vi)2m24，而简单连通平面图的每个面至少由3条边围成，所以在6个结点12条边的连通平面简单图中，每个面由3条边围成。 （2）设(n,m)图为简单连通平面图，有k个面。（反证法）

若m7，由欧拉公式知nkm29，而每个面至少由3条边围成，有

3k2m，则k23m143，且k是整数，所以k4；又对任结点vV，

23m143deg(v)3，有3n2m，故n，且n是整数，所以n4。这样就有

nk448，与nk9矛盾，所以结论正确。