《离散数学》期末考试卷04-05(2)

《《离散数学》期末考试卷04-05(2)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（A卷）一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题干后的括号内。每题2分，共20分）1在自然数集上，下列哪种运算是可结合的？（）A.B.C.D.2下列代数系统<，*>中，哪个是群？（）A.，*是模7加法B.（有理数集合），*是一般乘法C.（整数集合），*是一般减法D.，*是模11乘法3若<，*>是<，*>的真子群，且，，则有（）。A.整除B.整除C.整除且整除D.不整除且不整除4下面哪个集合关于指定的运算构成环？（）

2、A.，关于数的加法和乘法B.阶实数矩阵，关于矩阵的加法和乘法C.，关于数的加法和乘法D.，关于矩阵的加法和乘法5在代数系统中，整环和域的关系为（）。A.域一定是整环B.域不一定是整环C.整环一定是域D.域一定不是整环6是自然数集，是小于等于关系，则是（）。A.有界格B.有补格C.分配格D.有补分配格7图1-1给出的哈斯图表示的格中哪个元素无补元？（）abcdefgA.B.C.D.图1-18给定下列序列，可构成无向简单图的结点度数序列的是（）。A.（1，1，2，2，3）B.（1，3，4，4，5）C

3、.（0，1，3，3，3）D.（1，1，2，2，2）9欧拉回路是（）。A.路径B.简单回路C.既是基本回路也是简单回路D.既非基本回路也非简单回路10哈密尔顿回路是（）。A.路径B.简单回路C.既是基本回路也是简单回路D.既非基本回路也非简单回路二、填空题（以下每个下划线为一空，请按要求填入合适的内容。每空2分，共30分）abca①a②babcc③c④1设是非空有限集，代数系统中，对运算的单位元是＿＿＿＿，零元是＿＿＿＿，对运算的单位元是＿＿＿＿。表2-12在运算表2-1中空白处填入适当符号，使成

4、为群。①＿＿＿＿，②＿＿＿＿，③＿＿＿＿，④＿＿＿＿。3设，是群的子群，其中，是模12加法，则有＿＿＿＿个真子群，的左陪集＿＿＿＿，＿＿＿＿。4设是一个布尔代数，如果在上定义二元运算为：，则是一个＿＿＿＿。5任何一个具有个元素的有限布尔代数都是＿＿＿＿。6若连通平面图有4个结点，3个面，则有＿＿＿条边。7一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，它有＿＿＿＿个度数为1的结点。8无向图是由（）棵数组成的森林，至少要添加＿＿＿＿条边才能使成为一棵树。三、求解题（20分）1试写出中

5、每个子群及其相应的左陪集。（6分）274412313652若一个有向图是欧拉图，它是否一定是强连通的？若一个有向图是强连通的，它是否一定是欧拉图？说明理由。（6分）3有向图如图3-1所示。（1）求的邻接矩阵；（2分）（2）中到长度为4的路径有几条？（2分）（3）中到自身长度为3的回路有几条？（2分）（4）是哪类连通图？（2分）四、证明题（30分）1设是一群，。定义：，。证明也是一群。（10分）2证明：（1）证明在格中成立：。（5分）（2）证明布尔恒等式：。（5分）3证明：（1）在6个结点12条边

6、的连通平面简单图中，每个面由3条边围成。（5分）（2）证明当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。（5分）安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（A卷）参考答案一、单项选择1．B;2.D;3.A;4.C;5.A;6.C;7.B;8.D;9.B;10.C.二、填空题1，，；2，，，；35，，；4交换群；5同构；65；79；8。三、求解题1解：子群有：，，。的左陪集为：，，，，，的左陪集为：，，的左陪集为：，2答：（1）一个有向欧拉图一定是强连通图。因为

7、是欧拉图，存在欧拉回路，中的每个结点至少在中出现一次。因而中任意两点，都在中，相互可达，故是强连通的。（2）一个强连通图不一定是有向欧拉图。因为强连通图中每个结点的入度不一定等于其出度。3解：（1）（2）由中可知，到长度为4的路径有条（56748，，，）。（3）由中可知，到自身长度为3的回路有1条（）。（4）是单向连通图。四、证明题1证明：显然是上的二元运算（即满足封闭性），要证是群，需证结合律成立，同时有单位元，每个元素有逆元。，有运算是可结合的。其次，是的单位元。事实上，，有；最后证明，，是

8、在中的逆元。事实上，由以上证明，是群。2证明：（1）（公式(13)分配不等式）又因为，，所以。（2）因为，，所以有，（吸收律）即等式成立。3证明：（1）因图中结点数和边数分别为，，根据欧拉公式，得。又，而简单连通平面图的每个面至少由3条边围成，所以在6个结点12条边的连通平面简单图中，每个面由3条边围成。（2）设图为简单连通平面图，有个面。（反证法）若，由欧拉公式知，而每个面至少由3条边围成，有，则，且是整数，所以；又对任结点，，有，故，且是整数，所以。这样就有，与矛盾，所以结论正确。