2006离散数学a(答案)

2006 年下半年 离散数学 闭卷 70 学时 任课班级 114051 4 111051 2 任课教师 孙明1 离散数学 离散数学 A 卷 卷 闭卷 闭卷 70 学时学时 一 一 填空选择题填空选择题 每空 1 分 共 26 分 1 给定命题公式如下 该公式的成真赋值为 A 成假赋值为 rqp B 公式的类型为 C 供选择的答案 A 无 全体赋值 010 100 101 111 010 010 100100 101101 110110 111111 B 无 全体赋值 000 000 001001 011011 000 010 110 C 重言式 矛盾式 可满足式可满足式 2 在公式中 的辖域是 P z Q x z yxRyyxQyPx x 的辖域是 R x z y 3 设 Z x x Z X 0 1 2 3是 Z 的 3 个划分 1 x x Z 2 S1 S2 S1为素数集 S2 Z S1 3 Z 1 3 个划分块中最多的是 A 最少的是 B 2 划分 1对应的是Z 上的 C 2对应的是Z 上的 D 3对应的是 Z 上的 E 供选择的答案 A B 1 2 3 C D E 整除关系 全域关系 包含关系 小于等于关系 恒等关系 含有两个等价类的等价关系 以上关系都不是 4 设 f R R g R R g x x 2 则 f g x 为 32 3 2 x x xf x g f x 为 g 12 1 2 2 x x xf x 30 32 2 x x xf x f R R 是 A f 1 B g 1 C 供选择的答案 A 单射不满射 满射不单射 不单射也不满射不单射也不满射 双射 B C 不是反函数 是反函数 2006 年下半年 离散数学 闭卷 70 学时 任课班级 114051 4 111051 2 任课教师 孙明2 5 设 G 0 1 2 3 若 为模 4 乘法 则构成 A 若 为模 4 加法 则是 B 阶群 且是 C G 中的 2 阶元是 D 4 阶元是 E 供选择的答案 A 群 半群半群 不是群 B 有限有限 无限 C Klein 四元群 置换群 循环群循环群 D E 0 1 和 3 2 6 设 A 是代数系统 二元运算 和 对于 A 是封闭的 如果对于 A 中任意的元素 a b c 满足交换律交换律 结合律结合律和和 吸收律吸收律 则称 A 是格 7 6 个顶点 11 条边的所以可能的非同构的连通的简单的非平面图有 4 4 个 其中有 2 2 个含子图 K3 3 有 2 2 个含与 K5同胚子图 二 二 计算题 每题 5 分 任选 6 题 共 30 分 1 计算幂集 P A 022 23 xRxxA xx 答 答 P A 1 1 2 1 1 1 2 1 2 1 1 2 P A 1 1 2 1 1 1 2 1 2 1 1 2 2 设 S 1 2 3 4 R 是 S 上的二元关系 其关系矩阵为 求 R 的关系表达式 dom R ran R R R 中有几个有序对 R 1的关系图中有几个环 答 答 关系表达示 关系表达示 dom dom R 1 2 3 4 ranR 1 2 3 4 ran R 1 4 R 1 4 7 7 1 1 3 S Q Q Q 为有理数集 为 S 上的二元运算 任意 S 有 运算在 S 上具有哪些主要性质 运算有无单位元 零元 如果有请指出 并求 S 中所有可逆元素的 逆元 答 答 运算不是可交换的 可结合的 在运算不是可交换的 可结合的 在 a 0 且且 b Q 或者或者 1 0 时满时满 足幂等律 足幂等律 1 0 为为 运算的单位元 对任意运算的单位元 对任意 a b Q Q 只要 只要 a0 都存在逆元都存在逆元 不存在零元 不存在零元 1000 0001 1000 1001 R 2006 年下半年 离散数学 闭卷 70 学时 任课班级 114051 4 111051 2 任课教师 孙明3 4 有向图 D 如图 1 1 所示 求 D 中长度为 4 的通路总数是多少 并指出其中有多少条是回路 其 图 1 1 答 答 A2 A3 A4 1100 1000 0100 0120 A 2100 1100 1000 1200 3200 2100 1100 3100 从从 A4可看出 可看出 D 中长度为中长度为 4 的通路有的通路有 23 条 其中条 其中 7 条为回路 条为回路 5300 3200 2100 4300 5 当 n 和 m 为何值时 完全二部图 Kn m是 欧拉图 哈密顿图 平面图 非平面图 答 答 n n 和和 m m 都是正偶数 都是正偶数 n m n m 且且 n 2n 2 n 2 n 3 n 3 m 3m 3 6 设无向树 T 由 7 片树叶 其余顶点的度数均为 3 求 T 中 3 度顶点数 能画出几棵具有此种度数的非同构的无向树 答 答 T T 中有中有 5 5 个个 3 3 度顶点 设度顶点 设 T T 中有中有 x x 个个 3 3 度顶点 则度顶点 则 T T 中的顶点数中的顶点数 n 7 x n 7 x 边边 数数 m n 1 6 x m n 1 6 x 由握手定理的方程由握手定理的方程 2m 12 2x 3x 7 2m 12 2x 3x 7 解出解出 x 5 Tx 5 T 的度数列为的度数列为 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 有两棵非同构的树 有两棵非同构的树 7 在图 1 2 所示的无向图 G 中 黑线边所示的子图为 G 的一棵生成树 T 求 G 的对应于 T 的基本回路系统 对应生成树的弦分别为对应生成树的弦分别为 e6 e7 e8 e10 e11 设它们对应的基本回路分别为设它们对应的基本回路分别为C C1 1 C C2 2 C C3 3 C C4 4 C C5 5 从对应的弦开始 按逆时 从对应的弦开始 按逆时 针 也可都按顺时针 的顺序写出它们 分别为针 也可都按顺时针 的顺序写出它们 分别为 C C1 1 e e6 6e e4 4e e5 5 C C2 2 e e7 7e e2 2e e1 1 C C3 3 e e8 8e e9 9e e2 2e e1 1 C C4 4 e e1010e e3 3e e5 5e e2 2 C C5 5 e e1111e e3 3e e5 5e e2 2e e9 9 此图的圈秩为此图的圈秩为 5 5 基本回路系统为 基本回路系统为 C C1 1 C C2 2 C C3 3 C C4 4 C C5 5 2006 年下半年 离散数学 闭卷 70 学时 任课班级 114051 4 111051 2 任课教师 孙明4 三 三 证明题 每题 6 分 任选 4 题 共 24 分 1 设 H1和 H2是群的两个互不包含的子群 证明 G 中存在一个元 素 它既不属于 H1 也不属于 H2 证明 因为证明 因为 H1H2 所以存在所以存在 a H1 且且 aH2 又因为 又因为 H2H1 所以存在 所以存在 b H2 且且 bH1 显然 显然 a b G 因为 因为 a H1 是是的的 子群 可推出子群 可推出 b H1 这与这与 bH1矛盾 同理可证 矛盾 同理可证 a bH2 2 证明欧拉图中必没有割边 证明 主要利用证明 主要利用 无向图中 奇度顶点的个数为偶数无向图中 奇度顶点的个数为偶数 这一结论用反证法 这一结论用反证法 设欧拉图中含有割边 由于欧拉图中每一个顶点的度数为偶数 所以割边的两设欧拉图中含有割边 由于欧拉图中每一个顶点的度数为偶数 所以割边的两 个端点也是偶数度顶点 删去割边后 构成两个连通分支 每个连通分支都含个端点也是偶数度顶点 删去割边后 构成两个连通分支 每个连通分支都含 有割边的一个端点 此时每一个连通分支中仅有一个奇数度顶点 这与已知矛有割边的一个端点 此时每一个连通分支中仅有一个奇数度顶点 这与已知矛 盾 所以 欧拉图中没有割边 盾 所以 欧拉图中没有割边 3 设是格 任取 a L 令 S x x L x a 证明是 L 的子格 证明 对于任意的证明 对于任意的 x y S 必有 必有 xa 和和 ya 所以所以 x ya x y ya 故 故 x y S x y S y S 因此因此 S 是是 L 的子格 的子格 4 设 G 是 6 阶无向简单图 证明 G 或它的补图中存在 3 个顶点彼此相邻 证明 设证明 设 6 个顶点的简单图为个顶点的简单图为 G 考察考察 G 中的任意一个顶点中的任意一个顶点 a 那么 另 那么 另 外外 5 个顶点中的任何一个顶点 要么在图个顶点中的任何一个顶点 要么在图 G 中与中与 a 邻接 要么在图邻接 要么在图 G 中与中与 a 邻接 这样 就把邻接 这样 就把 5 个结点分成两类 将会必有一类至少含有三个顶点 不妨个结点分成两类 将会必有一类至少含有三个顶点 不妨 假设其中的假设其中的 3 个顶点为个顶点为 b c d 该图必是图 该图必是图 G 的子图 这里图的子图 这里图 G 可能是可能是 G 或者是或者是 G 如果边 如果边 b c c d b d 中有一条边在中有一条边在 G 择优择优 3 个顶点邻接 如果边个顶点邻接 如果边 b c c d b d 都不在都不在 G 中 那么必在中 那么必在 G 的补图 或是图的补图 或是图 G 或者是或者是 G 中 因 中 因 此 必有此 必有 3 个顶点邻接 个顶点邻接 5 设 n 阶 m 条边的平面图是自对偶图 证明 m 2n 2 证明 设证明 设 G 图是图是 G 的对偶图 所以的对偶图 所以 G 必为连通的平面图 且必为连通的平面图 且 n r m m r n 于是于是 n n r 由欧拉公式可知 由欧拉公式可知 n m r 2 n m n 得得 m 2n 2 6 验证K5和K3 3都是极小非平面图 答 画图举例 答 画图举例 四 应用题 每题 10 分 共 20 分 1 在自然推理系统 F 中 证明下面推理 每个喜欢步行的人都不喜欢骑自行车 每个人或者喜欢骑自行车或者 喜欢乘汽车 有的人不喜欢乘汽车 所以有的人不喜欢步行 个体域为人类集 合 解 设解 设 P x x 喜欢步行 喜欢步行 Q x x 喜欢乘汽车 喜欢乘汽车 R x x 喜欢骑自行喜欢骑自行 车 本题符号化为车 本题符号化为 前题 前题 x P x R x x R x Q x x Q x 2006 年下半年 离散数学 闭卷 70 学时 任课班级 114051 4 111051 2 任课教师 孙明5 结论 结论 x P x x Q x 前提引入前提引入 x R x Q x 前提引入前提引入 Q c EI 规则规则 R c Q c UI 规则规则 x P x R x 前提引入前提引入 P c R c UI 规则规则 R c 析取三段论析取三段论 P c 拒取式拒取式 x P x EG 规则规则 2 今有 n 个人 已知他们中的任何二人和起来认识其余的 n 2 个人 证明 当 n 3 时 这 n 个人能排成一列 使得中间的任何人都认识两旁的人 而两旁 的人认识左边 或右边 的人 而当 n 4 时 这 n 个人能排成一个圆圈 使得 每个人都认识两旁的人 解 设解 设 n n 个人分别为个人分别为 V V1 1 V V2 2 V V3 3 Vn V V Vn V V1 1 V V2 2 V V3 3 Vn Vn 为顶点集 若为顶点集 若 V Vi i与与 V Vj j认识 就在代表它们的顶点间连一条无向边 得边集认识 就在代表它们的顶点间连一条无向边 得边集 E E 于是的无向简 于是的无向简 单图单图 G G 对于任意 对于任意 V Vi i V Vj j V V 假设 假设 V Vi i与与 V Vj j不相邻 则对任意不相邻 则对任意 V Vk k V V ki kjki kj 必与 必与 V Vi i或或 V Vj j相邻 否则与已知条件矛盾 不妨假设 相邻 否则与已知条件矛盾 不妨假设 V VK K 与与 V Vi i相邻 与相邻 与 V Vj j不相邻 那么不相邻 那么 V Vk k与与 V Vi i所代表的两个人都不认识所代表的两个人都不认识 V Vj j所代表的人 所代表的人 这与已知矛盾 所以这与已知矛盾 所以 V VK K与与 V Vi i相邻 也与相邻 也与 V Vj