武汉大学2015–2016学年第一学期期末考试《离散数学》试题(A卷).PDFVIP

武汉大学2015 – 2016 学年第一学期期末考试 数学与统计学院 信息与计算科学、数学与应用数学等专业 《离散数学》试题(A 卷) 注意事项: (1) 本试卷共 12 道试题, 满分 100 分, 考试时间 120 分钟. (2) 请将答案全部写在武汉大学试卷纸上, 写在其他位置无效. 一、集合论 (本题满分 25 分) { } 1. (9 分) 设 是自然数集, 定义 上的二元关系 ⟨ ⟩ 是偶数 . (1) 证明 是一个等价关系; (2) 求商集. 2. (10 分) 设 , 上的二元关系 和 定义如下: {⟨ ⟩ ⟨ ⟩ ⟨ ⟩ ⟨ ⟩} {⟨ ⟩ ⟨ ⟩ ⟨ ⟩ ⟨ ⟩} 其中 是 上的恒等关系. (1) 试分别指出 和 所具有的性质 (即是否具有自反性, 反自反性, 对称性, 反对称性 和传递性); (2) 试求出 , , ◦ , 和 (传递闭包). 3. (6 分) 从 , , , , 这 个数中任意挑出 个数. 用抽屉原理证明: 在这 个数 中, 一定有: (1) 个数互质; (2) 个数的差为 . 二、代数结构 (本题满分 25 分) 4. (9 分) 设 , 其中 , 运算 是普通乘法. 证明 ⟨ ⟩ 是循环群. 5. (9 分) 设 ⟨ ⟩ 是代数系统, 是集合, 试判断 是否为半群、独异点、群? 为 什么? 并求 中的任意元素 的 次幂 ( ). 6. (7 分) 列举你所知道的各种类型的格, 并画图表示它们之间的关系. 三、图论 (本题满分 25 分) 7. (8 分) 设有, , , , , , 七个人, 已知 会讲英语; 会讲英语、汉语; 会讲英、俄语; 会讲日、汉语; 会讲德语、俄语; 会讲法语、日语; 会讲法语、德语. 试用图论方法 安排圆桌座位, 使每人都能与其身边的人交谈. 第 1 页 8. (8 分) 设有6 个村庄 , , 欲修建道路使村村可通. 现已有修建方案如下带权 无向图所示, 其中边表示道路, 边上的数字表示修建该道路所需费用, 问应选择修建哪些道 路可使得任意两个村庄之间是可达的且总的修建费用最低? 要求写出求解过程, 画出符合 要求的费用最低的道路网络图, 并计算其费用.