2012离散数学II2试卷A答案

第 1 页 共 4 页 中国民航学院 2012 2013 学年第 1 学期 离散数学 期末试卷 A 课程编号 03401519 试卷类型 考试形式 闭卷 考试日期 2012 年 12 月 28 日 15 30 17 30 南 3 203 211 题号一二三四五六总分 得分 注意事项 1 试卷答在答题纸上 后一页为草稿纸 可以撕下 2 不准携带 任何书籍 资料 纸张等 一 30 分 选择选择 答案写在答题纸上答案写在答题纸上 1 下列运算中 哪种运算关于整数集不能构成半群 1 a b max a b 2 a b b 3 a b 2ab 4 a b a b 答案 4 2 设 I 是整数集 分别是普通加法和乘法 则 I 是 1 域 2 整环和域 3 整环 4 含零因子环 答案 3 3 下面哪个哈斯图表示的偏序关系不能构成格如图 1 1 所示 a a b d b f c c e e d 1 2 a a b c b d e c d e f f 3 4 图 1 1 班级 姓名 准考证号 任课教师 考场教室 装 订 线 姓名 班级 姓名 准考证号 任课教师 考场教室 装 订 线 姓名 第 2 页 共 4 页 2 答案 2 4 给定无向图 G V E 如图 1 2 所示 则其割点为 a a1 1 a a6 6 a a8 8 a a7 7 a a5 5 a a4 4 a a3 3 a a2 2 图 1 2 1 a1 2 a5 3 a4 4 a6 答案 3 5 图 1 3 中哪一个图可一笔画出 1 2 3 4 图 1 3 答案 1 6 完全图 K4的所有非同构的生成子图中有几个是 3 条边的 1 1 2 3 3 4 4 2 答案 2 二 20 分 填空填空 答案写在答题纸上答案写在答题纸上 1 设 G 是非零实数乘法群 f G G 是同态映射 F x 1 x 则 f G ker f 答案 G 1 2 有限群的阶数为 时 它无非平凡子群 根据 答案 素数 拉格朗日定理 3 在任何图 G V E 中 结点 v 的度数为 图 G 的最大度 G 图 G 的最小度 G 答案 结点 u 关连的边数 max deg v v V min deg v v V 第 3 页 共 4 页 3 4 G 是有向图 当且仅当 G 中有一条至少通过每个结点的回路 G 为 图 当 R 仅当 G 中有一条通过每个结点的路时 G 为 图 答案 强连通 单侧连通 三 简答题 30 分 1 10 分 一个群能否同构于它的一个真子群 为什么 解 一个群能同构于它的一个真子群 例如 是群 若 令 E 偶数 则是的真子群 设 f I E f k 2k 则与同构 即 2 10 分 设 a b c d 是格的任意四个元 证明 a b a c a b c 证明 a a b a a c a a b a c b c b a b b c c a c b c a b a c 于是有 a b c a b a c 由对偶原理得 a b c a b a c 即 a b a c a b c 3 10 分 有四个村庄的地下各有一个防空洞甲 乙 丙 丁 相邻两个防空洞之 间有地道相通 并且每个防空洞各有一条地道与地面相通 如图 4 23 所示 图中 表示地道 能否从某一个防空洞开始 每个地道走一次且只走一次后回到该防空 洞 甲甲 丁丁 丙丙 乙乙 图 3 1 解 依题意若对四个防空洞及地面用结点表示 地道用边表示 得无向图 G 如图 4 24 所示则该题转为判定 G 中是否有偶拉回路 由图形知有四个结点的度数为奇数 故无解 甲甲 地地 丙丙 丁丁 乙乙 图 3 1 第 4 页 共 4 页 4 四 证明 20 分 1 10 分 设 U 是群中取定的元 在 G 中定义 对任 a b G a b a u 1 b 其中 u 1 是 u 在 G 中的逆元 证明 是群 证明 任 a b G a b a u 1 b G 封闭 a b c a a 1 b c a a 1 b c a u 1 b u 1 c a u 1 b u 1 c a u 1 b c a b c 可结合 对任 a G u a u u 1 a a u u 为么元 对任 a G 存在 a u a 1 u 使 a a a a u G 中元素有逆元 由 一 所证 G 是群 2 10 分 给定图 G 如图 3 1 所示 1 给出 G 的邻接矩阵 2 求各结点的出 入度 3 求从结点 C 出发长度为 3 的所有回路 a a d d c c c c b b 图 4 1 解 1 G 的邻接矩阵 A G 0 0 1 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1