离散数学图论部分形成性考核书面作业

形成性考核作业 1 离散数学作业离散数学作业 5 离散数学图论部分形成性考核书面作业离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共 3 次 内容主要分别是集合论部分 图论部 分 数理逻辑部分的综合练习 基本上是按照考试的题型 除单项选择题外 安排练习题目 目的是通过综合性书面作业 使同学自己检验学习成果 找出 掌握的薄弱知识点 重点复习 争取尽快掌握 本次形考书面作业是第二次作 业 大家要认真及时地完成图论部分的综合练习作业 要求 要求 将此作业用 A4 纸打印出来 手工书写答题 字迹工整 解答题要 有解答过程 要求 2010 年 12 月 5 日前完成并上交任课教师 不收电子稿 并在 05 任务界面下方点击 保存 和 交卷 按钮 以便教师评分 一 填空题一 填空题 1 已知图 G 中有 1 个 1 度结点 2 个 2 度结点 3 个 3 度结点 4 个 4 度 结点 则 G 的边数是 15 2 设给定图 G 如右由图所示 则图 G 的点割集是 f 3 设 G 是一个图 结点集合为 V 边集合为 E 则 G 的结点 度数之和 等于边数的两倍 4 无向图 G 存在欧拉回路 当且仅当 G 连通且 等于出度 5 设 G 是具有 n 个结点的简单图 若在 G 中每一对结点度数之 和大于等于 n 1 则在 G 中存在一条汉密尔顿路 6 若图 G 中具有一条汉密尔顿回路 则对于结点集 V 的每个非空 子集 S 在 G 中删除 S 中的所有结点得到的连通分支数为 W 则 S 中结点数 S 与 W 满足的关系式为 W G V1 V1 7 设完全图 K 有 n 个结点 n 2 m 条边 当 n 为奇数 时 K n 中存在欧拉回路 n 8 结点数 v 与边数 e 满足 e v 1 关系的无向连通图就是 树 9 设图 G 是有 6 个结点的连通图 结点的总度数为 18 则可从 G 中删去 4 条边后使之变成树 10 设正则 5 叉树的树叶数为 17 则分支数为 i 5 姓姓 名 名 学学 号 号 得得 分 分 教师签名 教师签名 形成性考核作业 2 二 判断说明题二 判断说明题 判断下列各题 并说明理由 1 如果图 G 是无向图 且其结点度数均为偶数 则图 G 存在一条欧拉回 路 1 不正确 缺了一个条件 图 G 应该是连通图 可以找出一个反例 比 如图 G 是一个有孤立结点的图 2 如下图所示的图 G 存在一条欧拉回路 2 不正确 图中有奇数度结点 所以不存在是欧拉回路 3 如下图所示的图 G 不是欧拉图而是汉密尔顿图 解 正确 因为图中结点 a b d f 的度数都为奇数 所以不是欧拉图 如果我们沿着 a d g f e b c a 这样除起点和终点是 a 外 我们经过每个点 一次仅一次 所以存在一条汉密尔顿回路 是汉密尔顿图 4 设 G 是一个有 7 个结点 16 条边的连通图 则 G 为平面图 解 1 错误 假设图 G 是连通的平面图 根据定理 结点数 v 边数为 e 应满足 e 小于 等于 3v 6 但现在 16 小于等于 3 7 6 显示不成立 所以假设错误 5 设 G 是一个连通平面图 且有 6 个结点 11 条边 则 G 有 7 个面 2 正确 根据欧拉定理 有 v e r 2 边数 v 11 结点数 e 6 代入公式求出面数 r 7 三 计算题三 计算题 1 设 G V v1 v2 v3 v4 v5 E v1 v3 v2 v3 v2 v4 G 形成性考核作业 3 v3 v4 v3 v5 v4 v5 试 1 给出 G 的图形表示 2 写出其邻接矩阵 3 求出每个结点的度数 4 画出其补图的图形 解 1 2 邻接矩阵为 01100 10110 11011 01100 00100 3 v1结点度数为 1 v2结点度数为 2 v3结点度数为 3 v4结点度数为 2 v5结点度数为 2 4 补图图形为 2 图 G 其中 V a b c d e E a b a c a e b d b e c e c d d e 对应边的权值依次为 2 1 2 3 6 1 4 及 5 试 1 画出 G 的图形 2 写出 G 的邻接矩阵 3 求出 G 权最小的生成树及其权值 1 G 的图形如下 v1 v5 v2 v3 v4 v1 v5 v2 v3 v4 形成性考核作业 4 2 写出 G 的邻接矩阵 3 G 权最小的生成树及其权值 3 已知带权图 G 如右图所示 1 求图 G 的最小生成树 2 计算该生成树的权值 解 1 最小生成树为 形成性考核作业 5 12 3 5 7 2 该生成树的权值为 1 2 3 5 7 18 4 设有一组权为 2 3 5 7 17 31 试画出相应的最优二叉树 计算该最优 二叉树的权 3 5 2 5 1 0 7 17 31 1 7 3 4 6 5 形成性考核作业 6 权为 2 5 3 5 5 4 7 3 17 2 31 131 四 四 证明证明题题 1 设 G 是一个 n 阶无向简单图 n 是大于等于 3 的奇数 证明图 G 与它 的补图中的奇数度顶点个数相等 G 证明 设 则是由 n 阶无向完全图的边删去 E GV E GV E E n K 所得到的 所以对于任意结点 u 在 G 和中的度数之和等于 u 在中uV G n K 的度数 由于 n 是大于等于 3 的奇数 从而的每个结点都是偶数度的 n K 度 于是若在 G 中是奇数度结点 则它在中也是奇数度结1 2 n uV G 点 故图 G 与它的补图中的奇数度结点个数相等 G 2 设连通图 G 有 k 个奇数度的结点 证明在图 G 中至少要添加条边才 2 k 能使其成为欧拉图 证明证明 由定理 3 1 2 任何图中度数为奇数的结点必是偶数