离散试卷及答案
??p?q??p??????p?q??p????p??q??p??p?p??q??q???p??q???p?q????主合取范式??0，1?安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（A卷）参考答案
一、单项选择
1 在自然数集N上，下列哪种运算是可结合的？（ ）
A. a*b?a?b B. a*b?max{a,b} C. a*b?a
3??2，?2b D. a*b?a?b(mod3)
2 下列代数系统
A. SC. S，*是一般乘法 ?{0,1,3,5}，*是模7加法 B. S?Q（有理数集合）
，*是一般减法 D. S?{1,3,4,5,9}，*是模11乘法 ?Z（整数集合）
3 若
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}，关于数的加法和乘法
b e c f d g ????ab??a,b?Z?D. ???，关于矩阵的加法和乘法 ?ba???????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）
第 6 页 共 12 页
离散试卷及答案
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},?)成为群。 a b ①＿＿＿＿，②＿＿＿＿，③＿＿＿＿，④＿＿＿＿。 ? c a ① a ② 3 设H?{0,4,8}，?H,?12?是群?N12,?12?的子群，其中
b a b c c ③ c ④ N12?{0,1,2,???,11}，?12是模12加法，则?N12,?12?有＿＿＿＿
个真子群，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是强连通的，它是否一定是欧拉图？说明理由。3 有向图G如图3-1所示。 e1 （1）求G的邻接矩阵
A； （2分）
（2）G中vv1 1到v4长度为4的路径有几条？ （2分） eve4 4 3 ee2 6 e7 （3）G中v1到自身长度为3的回路有几条？ （2分） v2 e5 v3
（4）G是哪类连通图？ （2分）
图3-1
四、证明题（30分）
1 设?G,*?是一群，x?G。定义：a?b?a*x*b，?a,b?G。证明?G,??也是一群。 2 证明：（1）证明在格中成立：(a*b)?(c*d)?(a?c)*(b?d)。 （5分）
（2）证明布尔恒等式：(a*c)?(a?*b)?(b*c)?(a*c)?(a?*b)。 （5分）
第 7 页 共 12 页
6分） （离散试卷及答案
3 证明：（1）在6个结点12条边的连通平面简单图中，每个面由3条边围成。 （5分）
（2）证明当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。
安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（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； 5 同构； 三、求解题
1 解：子群有：?{0},?6
6 5；
3 5，{3,7,11}，{4,8,0}； 4 交换群； 7 9；
8 k?1。
?，?{0,3},?6?，?{0,2,4},?6?。
?{0},?6?的左陪集为：{0}，{1}，{2}，{3}，{4}，{5} ?{0,3},?6?的左陪集为：{0,3}，{1,4}，{2,5}
?{0,2,4},?6?的左陪集为：{0,2,4}，{1,3,5}
2 答：（1）一个有向欧拉图一定是强连通图。因为G是欧拉图，存在欧拉回路C，G中的每个结点至少在C中出现一次。因而G中任意两点u，v都在C中，相互可达，故G是强连通的。（2）一个强连通图不一定是有向欧拉图。因为强连通图中每个结点的入度不一定等于其出度。 3 解：
?1?0（1）A???0??0（2）由
210??1?0010?2? A??001??0??010??0231??1?0001?3? A??010??0??001??0243??1?0010?4? A??001??0??010??0264?001??
010??001?4?4可知，v1到v4长度为4的路径有条（e1e1e4e6，e4e6e7e6，e1e2e5e6，e1e3e5e6）。 A4中a143?1可知，v1到自身长度为3的回路有1条（e1e1e1）。 A3中a11（3）由
（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,??中的逆元。事实上，
第 8 页 共 12 页
离散试卷及答案
a?(x?1*a?1*x?1)?a*x*x?1*a?1*x?1?x?1 (x?1*a?1*x?1)?a?x?1*a?1*x?1*x*a?x?1
由以上证明，?G,??是群。
2 证明：（1）(a*b)?(c*d)?((a*b)?c)*((a*b)?d) （公式(13)分配不等式） 又因为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）因图中结点数和边数分别为
in?6，
m?12，根据欧拉公式
n?m?k?2，得
k?8。又
?deg(v)?2m?24，而简单连通平面图的每个面至少由3条边围成，所以在6个结点12条边的连通平面简单图中，每个
面由3条边围成。
（2）设(n,m)图为简单连通平面图，有k个面。（反证法） 若m?7，由欧拉公式知n?k数，所以k有n?k?m?2?9，而每个面至少由3条边围成，有3k?2m，则k?，deg(v)?3，有3n?2m，故n?214m?，且k是整33?4；又对任结点v?V214m?，且n是整数，所以n?4。这样就33?4?4?8，与n?k?9矛盾，所以结论正确。
安徽大学2007— 2008学年第 2 学期 《离散数学（下）》考试试卷（A卷）
一、单项选择题（每小题2分，共20分）
1. 下列集合关于数的加法和乘法运算不能构成环的是（ ）
A.自然数集合； B.整数集合； C.有理数集合； D.实数集合。 2. 设I为整数集合，则下列集合关于数的加法运算不能构成独异点的是（ ）
A.I； B.{2k|k?I}； C.{2k?1|k?I}； D.{3m?5n|m,n?I}。
3. 设N6?{0,1,?,5}，?6为模6加法，则下列元素是?N6,?6?的生成元的是（ ）
A.2； B.3； C.4； D.5。
第 9 页 共 12 页
离散试卷及答案
4. 设?F,?,??是整环，则?F,?,??不一定是（ ）
A.可交换环； B.无零因子环； C.含么环； D.域。 5. 格不一定具有（ ）
A.交换律； B.结合律； C.分配律； D.吸收律。 6. 设S?{1,2,4,8}，?和?分别表示求最小公倍数和最大公约数运算，则?S,?,??是（ ）
A.有补格； B.分配格； C.有补分配格； D.布尔代数。
7. 一个含4个结点的无向图中有3个结点的度数分别为1,2,3，则第4个结点的度数不可能是（ ）
A.0； B.1； C.2； D.4。
8. 设连通的简单平面图G中有10条边和5个面，则G的结点数为（ ）
A.6； B.7； C.8； D.9。
9. 设无向树T中有1个结点度数为2，2个结点度数为3，3个结点度数为4，则T中的树叶数为（ ）
A.10； B.11； C.12； D.13。
10.设G为连通的无向图，若G仅有2个结点的度数是奇数，则G一定具有（ ）
A、欧拉路径； B、欧拉回路； C、哈密尔顿路径； D、哈密尔顿回路。 二、填空题（每小空2分，共20分） 1. 设R为实数集合，S?{x|x?R?0?x?1}，则在代数?S,max>中，
S关于max运算的么元是＿ ＿＿，零元是＿ ＿＿。
2. 设?10为模10加法，则在?{0,1,?,9},?10?中，元素5的阶为 ，6的阶为＿ ＿＿。
3. 设S110?{1,2,5,10,11,22,55,110}，gcd和lcm分别为求最大公约数和最小公倍数运算，
S110,gcd,lcm?中，原子的个数为＿ ＿＿，元素22的补元为＿ ＿＿。
则在布尔代数?4. 在格?L,?,??中，?a,b?L，a?b当且仅当a?b?＿ ＿＿当且仅当a?b?＿ ＿＿。
5. 一个具有n个结点的简单连通无向图的边数至少为＿ ＿＿，至多为＿ ＿＿。 三、解答题（第1小题12分，第2小题8分，共20分） 1. 设图G如图1所示， (1) 求G的邻接矩阵(2) 求A(2)A；
,A(3),A(4)，说明从v1到v4的长为2,3,4的路径各有几条；
第 10 页 共 12 页