离散数学(B)答案2015.doc

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

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

2、一个子图它是或。（´）10、没有基本回路且有n—1条边的n阶图是树。（Ú）二、填空题（每空4分，共20分）得分1、将命题：“明天我去北京或上海出差。”符号化。解：设命题P：明天我去北京出差；Q：明天我去上海出差。则命题：“明天我去北京或上海出差。”可以符号化为：2、集合X上的等价关系R。解：集合X上的等价关系R是指关系R是集合X上的自反，对称和传递关系。3、基本通路。解：基本通路是一条没有顶点重复的通路。4、轮图的色数5、简单图的联通分支数，则。三、选择题（每题4分，共20分）得分1、下面蕴含永真式中，错误的是（D）（A）(B)(C)(D)2、设集合上的关系是整除关系，则关系（D）（

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

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是所有基本通路

5、中长度最长的一条这一事实相矛盾。所以G中必有回路存在。从而图G有基本回路。2、证明：有限偏序集必有极小元存在。证明：任意取，如果不是极小元，那么存在，使得；如果不是极小元，那么存在，使得；因为X是有限集合，且上述过程中得到的元素互不相等，所以这个过程不能无限重复。假设重复了k次后终止，这时就是有限偏序集的极小元。