离散数学B答案

1、班级： 学号： 姓名： 装 订 线 杭州师范大学钱江学院2014 2015 学年第二学期期末试卷_ 班 离散数学 （B）卷 命题教师_田正平_题目一二三四五总分分值2020202020100得分一、 判断题（对的打Ú，错的打´；每空2分，共20分）得分1、 “若鸟会飞，则地球比太阳小。” 是假命题。（´ ）2、 。（ Ú ）3、 （ Ú ）4、 有限偏序集必定存在极大元。（ Ú ）5、 反对称关系一定不是对称关系。（ ´ ）6、 设集合上的关系的关系矩阵是，则关系是偏序关系。（ Ú ）7、 偶图G的顶点个数是奇数，

2、则G不是哈密顿图。（ Ú ）8、 在图G中若所有的顶点度数都是偶数，则G是欧拉图。（ ´ ）9、若图G不是平面图则图G一定含有一个子图它是或。（ ´ ） 10、没有基本回路且有n1条边的n阶图是树。（ Ú ）二、填空题（每空4分，共20分）得分1、将命题：“明天我去北京或上海出差。”符号化。 解：设命题P：明天我去北京出差；Q：明天我去上海出差。则命题：“明天我去北京或上海出差。”可以符号化为： 2、集合X上的等价关系R。 解：集合X上的等价关系R是指关系R是集合X上的自反，对称和传递关系。 3、 基本通路。 解：基本通路是一条没有顶点重复的通路。4、

3、轮图的色数5、简单图的联通分支数，则。三、选择题（每题4分，共20分） 得分1、下面蕴含永真式中，错误的是（ D ）（A） (B)(C) (D) 2、设集合上的关系是整除关系，则关系（ D ） （A）有最大元，有最小元 (B)有最大元，无最小元 (C) 无最大元，有最小元 (D) 无最大元，无最小元3、图G的邻接矩阵，则图G（ C ）（A）有欧拉通路，有哈密顿回路 (B)有欧拉回路，无哈密顿通路 (C) 无欧拉通路，无哈密顿回路 (D) 无欧拉回路，有哈密顿通路 4、设是实部不为零的复数数集，下面关系中是等价关系的是（ C ）（A） (B) (C) (D) 5、 和谓词公式等值的是（ B ）

4、（A） (B) (C ) (D) 四、计算题（每题4分，共20分）得分1、 化简命题公式。解： 2、集合上的关系，求关系的传递闭包。解： 所以： 3、在复数集上定义关系，给出这个等价类的几何说明。 解： 所以等价类是复平面上平行于实轴的直线。4、 图的邻接矩阵，求从顶点到顶点长度为3的不同通路的个数。 解： 所以顶点到顶点长度为3的不同通路的个数是6。 5、设集合上的关系是整除关系, 写出偏序关系的极大元、极小元。 解：偏序关系的极大元是18,20；极小元是2,3,5五、证明题（每题10分，共20分）得分1、 图G的最小度数。证明：图G有基本回路。证明：因为G至少有k条边，所以有基本通路存在。由定理知基本通路的长度不大于n-1。设P是所有基本通路中长度最长的一条，v分别是基本通路的终点。因为，从顶点v出发至少还有一条边v, u，顶点u必定在基本回路中出现，否则的话我们得到一条新的基本通路P+v,u,它比基本通路P还要长，这和P是所有基本通路中长度最长的一条这一事实相矛盾。所以G中必有回路存在。从而图G有基本回路。 2、 证明：有限偏序集必有极小元存在。 证明：任意取 ，如果不是极小元，那么存在，使得；如果不是极小