湖南大学大二计算机专业离散数学试卷

离散试卷及答案离散试卷及答案第第4页共4页湖南大学20XX-20XX学年第二学期《离散数学》期末考试试卷（A卷）参考答案一、单项选择在自然数集N上，下列哪种运算是可结合的？（ ）a*bab B.a*bmax{a,C.a*ba2b D.a*bab(mod下列代数系<S，*>中，哪个是群？（ ）S}，*是模7加法 B.SQ（有理数集合是一般乘C.SZ（整数集合，是一般减法 D.S,}，*是模11乘法若<H，*>是<G，*>的真子群，且Hn，Gm，则有（ 。n整除m B.m整除nC.n整除m且m整除n D.n不整除m且m不整除n下面哪个集合关于指定的运算构成环？（ ）b32|abZ}，关于数的加法和乘法阶实数矩阵}，关于矩阵的加法和乘法2ca2c

|a,bZ}，关于数的加法和乘法 b da b e gb aabZ，关于矩阵的加法和乘法 f在代数系统中，整环和域的关系为（ 。域一定是整环 域不一定是整环C.整环一定是域 D.域一定不是整环N是自然数集，是小于等于关系，则(N,)是（ 。有界格 有补格 C.分配格 D.有补分配格7图1-1给出的哈斯图表示的格中哪个元素无补元？（ A.a B.c C.e D.f 1-18给定下列序列，可构成无向简单图的结点度数序列的是（ A.（1，1，2，2，3） C.（0，1，3，3，3） 9欧拉回路是（ 。A.路径 简单回路C.既是基本回路也是简单回路 既非基本回路也非简单回10哈密尔顿回路是（ 。A.路径 简单回路C.既是基本回路也是简单回路 既非基本回路也非简单回路二、填空题（230。设S(P(S),,P(S)对运算的单位元是＿＿＿＿P(对运算的单位元是＿＿＿＿。abca①a②2-1({aabca①a②是群N , 的子群，其中12 12babcc③c④是群N , 的子群，其中12 12babcc③c④12N 是模12加法，则N , 有＿＿＿＿12 12 12 12H的左陪集3H＿＿＿＿，4H＿＿＿＿。设A,,,A上定义二元运算为：ab(ab)(ab)，则A,是一个＿＿＿＿。

表2-1任何一个具有2n个元素的有限布尔代数都是＿＿＿＿。若连通平面图G43G有＿＿＿＿条边。2，34，它有＿＿＿＿1无向图G是由k（k2）棵数组成的森林，至少要添加＿＿＿＿条边才能使G三、求解题（20）试写出N, 中每个子群及其相应的左陪集。（6分）6 6若一个有向图G是欧拉图，它是否一定是强连通的？若一个有向G是强连通的它是否一定是欧拉图说明理由。（6分） e有向图G如图3-1所示。 1e求G的邻接矩阵A；（2分） v ve1 4e 4e ee（2）G中v到ve1 4

4（2）

3 2 6 7v e v（3）G中v1

3（2）

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

图3-1四、证明题（30分）1设G,*是一群，xG。定义：aba*x*b，a,bG。证明G也是一群。2）证明在格中成立：(a*b)(c*d)(ac)*(bd)。（5分）（2）证明布尔恒等式：(a*c(a*bb*c)(a*c)a*b。（5）3）在6个结点12条边的连通平面简单图中，每个面由3条边围成。5分）（2）证明当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。湖南大学20XX-20XX学年第二学期《离散数学》期末考试试卷（A卷）参考答案一、单项选择1．B;2.D;3.A;4.C;5.A;6.C;7.B;8.D;9.B;10.C.二、填空题1SS；2cbba； 345同构；三、求解题

65； 79； 8k1。1解：子群有：，，。6 6 6，{2}，{3，{4}，{5}666（）GC，G中的每个结点至少在C中出现一次。因而G中任意两点uv都在C中，相互可达，故G（2）是有向欧拉图。因为强连通图中每个结点的入度不一定等于其出度。解：1

1 0

2 3 1

2 4 3

2 6 40

1 0

0 0 0

0 0 1 0

0 0 0 1（1）A

A2

A3

A4 0 0

0 11 0

0 0 1 0 0 0 0 1

0 0 1 0 1 0

0 1 00 0 1 A4中a414

4v到v1 4

4（eeee114 6

，eeee4 6 7

，eeee1256

，eeee。1356A3中a311

1v1

31（eee。111（4）G四、证明题1证明：显然是G上的二元运算（即满足封闭性，要证G是群，需证结合律成立，同时有单位元，每个元素有逆元。abcG，有(ab)c(a*x*b)*x*ca*x*(b*x*c)a(bc)运算是可结合的。其次，x1是G的单位元。事实上，aG，有ax1a*x*x1a；x1ax1*x*aa最后证明，aG，x1*a1*x1是a在G中的逆元。事实上，a(x1*a1*x1)a*x*x1*a1*x1x1(x1*a1*x1)ax1*a1*x1*x*ax1由以上证明，G是群。2证明）(a*b)(c*d)((a*b)c)*((a*b)d) （公(13分配不等式又因为a*ba，a*bb，所以(a*b)(c*d)(ac)*(bd)。（2）因为aa1，1*b*c(b*c，所以有，(a*c)(a*b)(b*c)(a*c)(a*b)((aa*(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）因图中结点数和边数分别为n6，m12，根据欧拉公式nmk2，得k8。又 deg(v2m243612i简单图中，每个面由3条边围成。（2）设(nm)图为简单连通平面图，有k（反证法）若m7，由欧拉公式知nkm29，而每个面至少