离散数学（A）答案2015.doc

《离散数学（A）答案2015.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、班级：学号：姓名：装订线杭州师范大学钱江学院2014—2015学年第二学期期末试卷_班《离散数学》（A）卷命题教师_田正平_题目一二三四五总分分值2020202020100得分一、判断题（对的打Ú，错的打´；每空2分，共20分）得分1、“若鸟不会飞，则地球比太阳大。”是假命题。（　´　）2、。（´　）3、（Ú）4、有限偏序集必定存在最小元。（´　）5、对称关系不一定是反对称关系。（Ú）6、设集合上的关系的关系矩阵是，则关系是等价关系。（´）7、图G是n阶简单图，若对所有的，则在G中有回路。（Ú）8、在哈密顿图G中若顶点u和v不相邻，则必有。（´）9、平面图G是n阶简单连通图，它有

2、e条边，则。（Ú）10、有n—1条边的n阶图是树。（´）二、填空题（每空4分，共20分）得分1、将命题：“每列火车都比某些汽车快。”符号化。设个体域为交通工具。P(x)：x是火车；Q(x)：x是汽车；R(x,y)：x比y快。则“每列火车都比某些汽车快。”可以符号化为：2、全序关系。集合X上的自反，反对称和传递关系称为X上的偏序关系，如果对于X中的任意两个元素都是可以比较的，那么就称为全序关系。3、简单回路。图的一条回路，如果其中所有的边都不相同，那么就称为简单回路。4、超立方图的色数2。5、在简单图中，，则图的联通分支数3。三、选择题（每题4分，共20分）得分1、下面命题公式中，矛盾

3、式是（C）（A）(B)(C)(D)2、设集合上的关系是整除关系，则关系（C）（A）有最大元，有最小元(B)有最大元，无最小元(C)无最大元，有最小元(D)无最大元，无最小元3、图G的邻接矩阵，则图G（C）（A）无欧拉通路，有哈密顿回路(B)有欧拉回路，无哈密顿通路(C)有欧拉通路，无哈密顿回路(D)无欧拉回路，有哈密顿通路4、设是非零实数集，下面关系中是等价关系的是（C）（A）(B)(C)(D)5、和谓词公式等值的是（C）（A）(B)(C)(D)四、计算题（每题4分，共20分）得分1、化简命题公式。解：2、集合上的关系，求关系的传递闭包。解：所以：3、在复数集上定义关系，给出这个等价

4、类的几何说明。解：所以等价类是复平面上平行于实轴的直线。4、图的邻接矩阵，求从顶点到顶点长度为3的不同通路的个数。解：所以顶点到顶点长度为3的不同通路的个数是6。5、设集合上的关系是整除关系,写出偏序关系的极大元、极小元。解：偏序关系的极大元是6和20；极小元是2和3。五、证明题（每题10分，共20分）得分1、图G是简单图，若它的最小度数。证明：图G有长度为k的基本通路。证明：因为G至少有k条边，所以有基本通路存在。由定理知基本通路的长度不大于n-1。设P是所有基本通路中长度最长的一条，u和v分别是基本通路的起点和终点。若P的长度不小于k,则问题已经解决。若P的长度小于k，因为，从顶

5、点v出发至少有k条边，而基本通路P上异于v的点仅有k-1个；在图G中还有另外一个点w和点v相邻接,这样我们得到一条新的基本通路P+{v,w},它比基本通路P还要长，这和P是所有基本通路中长度最长的一条这一事实相矛盾。所以G中最长的基本通路的长度一定不小于k。2、证明：有限全序集必有最大元存在。证明：有限全序集是偏序集，由定理知必有极大元存在，设为a。任意取，因为是全序集，所以和至少有一个成立。由a是极大元知是不可能成立的。这样由可得，即。所以a就是全序集的最大元。