离散数学习题解答-(9)

0 第七章第七章 图图 7 17 1 图的基本知识图的基本知识 定义定义 8 8 设图 G 1 G e 表示对 G 作删除边删除边 e 的运算 G e 其中 E E e E 2 G v 表示对 G 作删除顶点删除顶点 v 的运算 G v 其中 V V v E E e e 以 v 为端点 E 3 边 e 切割切割运算 设 G 中 e u v 对 G 作边 e 切割得 G 其 中 V V v E E e e1 e2 4 顶点 v 贯通贯通运算 设 G 中顶点 v 恰为边 e1 e2 的端点 且 e1 u v e2 w v 对 G 作顶点 v 贯通得 G 其中 V V v E E e1 e2 e 切割与贯通是互逆的 两者常被称为同胚同胚运算 定义定义 8 9 设 G1 G2 为两个图 称 G1 与 G2 同构同构 isomorphic 如果存在双射 f V1 V2 双射 g E1 E2 使得对每一边 e E1 1 e u v 或 当且仅当 2 g e f u f v 或 当限于讨论简单图时 可以用顶点的偶对表示边 即当 e u v 时 边 e 用 u v 来 表示 这时两图同构的条件可以简化为 u v E1 当且仅当 f u f v E2 习题解答习题解答 练习练习 7 1 1 想一想 一只昆虫是否可能从立方体的一个顶点出发 沿着棱爬行 它爬行过每条 梭一次且仅一次 并且最终回到原地 为什么 解解 不可能 可将立方体的一个顶点看作图的一个顶点 把立方体的棱看作图的边 那 么该图的四个顶点都是三度的 因此不可能从一个顶点出发 遍历所有的边一次且仅 一次 并且最终回到原顶点 2 请设想一张图 它的 64 个顶点表示国际象棋棋盘的 64 个方格 顶点间的边表示 在这两个顶点表示的方格之间可以进行 马步 的行走 试指出其顶点有哪几类 依其度分类 每类各有多少个顶点 解解 其顶点有 5 类 二度顶点合计 4 个 三度顶点合计 8 个 四度顶点 合计 20 个 六度顶 点 合计 16 个顶点 八度顶点 合计 16 个顶点 23444432 34666643 46888864 46888864 46888864 46888864 34666643 1 23444432 3 l 证明 n 个顶点的简单图中不会有多于条边 2 1 nn 2 n 个顶点的有向完全图中恰有条边 2 n 证证 l n 个顶点的简单完全图的边数总和为 2 1 12 2 1 nn nn 2 n 个顶点的有向完全图的边数总和为 2 nnnnnnn 4 证明 在任何 n n 2 个顶点的简单图 G 中 至少有两个顶点具有相同的度 证证 如果 G 有两个孤立顶点 那么它们便是具有相同的度的两个顶点 如果 G 恰有一个孤立顶点 那么我们可对有 n 1 个顶点但没有孤立顶点的 G 它由 G 删除孤立顶点后得到 作下列讨论 不妨设 G 没有孤立顶点 那么 G 的 n 个顶点的度数应是 1 2 3 n 1 这 n 1 种 可能之一 因此必定有两个顶点具有相同的度 5 图 8 10 是一个迷宫 其中数字表示通道 和死胡同 包括目标 请用一个图来表示 这个迷宫 用结点表示通道 和死胡同 包括目标 用边表示它们之间的可直接到达关系 2 图 8 10 解解 6 在晚会上有 n 个人 他们各自与自己相识的人握一次手 已知每人与别人握手的次 数都是奇数 问 n 是奇数还是偶数 为什么 解解 n 是偶数 用 n 个顶点表示 n 个人 顶点间的一条边表示一次握手 可构成一个无向 图 若 n 是奇数 那么该图的顶点度数之和为奇数 奇数个奇数的和 这是不可能的 因 此 n 是偶数 7 n 个城市间有 m 条相互连接的直达公路 证明 当时 人们便能 2 2 1 nn m 通过这些公路在任何两个城市间旅行 证证 用 n 个顶点表示 n 个城市 顶点间的边表示直达公路 据题意需证这 n 个城市的公 路网络所构成的图 G 是连通的 反设 G 不连通 那么可设 G 由两个不相关的子图 没有任 何边关联分别在两个子图中的顶点 G1 G2 组成 分别有 n1 n2个顶点 从而 n n1 n2 n1 1 n2 1 由于各子图的边数不超过 见练习 8 l 之 3 因此 G 的边数 m 满足 2 1 ii nn 1 1 2 1 1 2 1 2211 1 nnnnnnm k i ii 1 1 1 1 2 1 21 nnnn 2 1 2 1 2 1 2 1 21 nn nnn 2 1 18 317 4 5 20 21 16 15 6 19 22 14 713 8 9 10 11 12 3 与已知矛盾 故图 G 是连通的 2 2 1 nn m 本题是定理 8 8 的特例 当然也可以应用这一定理和它的证明方法来解题 8 1 证明 序列 7 6 5 4 3 3 2 6 5 5 4 3 2 2 以及 6 6 5 4 3 3 1 都不是简单图的度序列 2 若自然数序列 d1 d2 dn 满足 d1 d2 dn 那么当它为一简单图的度序列时 必有 a 为偶数 n i i d 1 b 对任一 k 1 k n k k 1 k i i d 1 n ki i dk 1 min 证证 1 由于 7 个顶点的简单图中不可能有 7 度的顶点 因此序列 7 6 5 4 3 3 2 不是简单图的度序列 序列 6 5 5 4 3 2 2 中有三个奇数 因此它不是简单图 的度序列 序列 6 6 5 4 3 3 1 中有两个 6 若它是简单图的度序列 那么应有 两个顶点是 6 度顶点 于是它们都要与其它所有顶点邻接 该图就不会有一度的顶点 与序 列中末尾的 1 冲突 故 6 6 5 4 3 3 1 也不是简单图的度序列 证证 2 为偶数是显然的 n i i d 1 考虑图中的 k 个顶点 k 1 2 n 这 k 个顶点的生成子图的度数总和 k k 1 而 其余 n k 个顶点 vk 1 vk 2 vn 可使 v1 v2 vk增加的度数不会超过 n ki i dk 1 min 因此我们有 k k 1 k i i d 1 n ki i dk 1 min 9 画出图 8 11 中图的补图及它的一个生成子图 图 8 11 解解 补图 生成子图 4 10 一个简单图 如果同构于它的补 则该图称为自补图自补图 1 给出一个 4 个顶点的自补图 2 给出一个 5 个顶点的自补图 3 是否有 3 个顶点或 6 个顶点的自补图 4 证明一个自补图一定有 4k 或 4k 1 个顶点 k 为正整数 解解 1 4 个顶点的自补图 2 5 个顶点的自补图 3 没有 4 证证 设 G 为自补图 有 n 个顶点 我们已知 n 个顶点的完全图有 条边 2 1 nn 因此 G 应恰有条边 故或者 n 是 4 的整数倍 或者 n 1 是 4 的整数倍 即图 G 一 4 1 nn 定有 4k 或 4k 1 个顶点 k 为正整数 11 l 证明图 8 12 中 a 与 b 同构 a b 图 8 12 2 给出所有不同构的 4 个结点的简单图的图示 l 证证 在图 a 图 b 间建立双射 h vABDIJCEGHF h v 可逐一验证 不赘 u v E a 当且仅当 h u h v E b 2 所有不同构的 4 个结点的简单图的图示有如下 11 个 A D C B E F G H I J 5 7 27 2 路径 回路及连通性路径 回路及连通性 习题解答习题解答 练习练习 7 2 1 证明定理 8 5 证证 设 n 个顶点的图 G 中 有从 v 到 v 的闭路径 表示为 v v1 v2 vk v 如果 v v1 v2 vk中没有相同顶点 因而不多于 n 个 那么它便是一条从 v 到 v 的长度不 大于 n 的回路 如果 v v1 v2 vk中有相同顶点 vi vj 例如 v v1 vi vj vj 1 vk v 那么删除 vi到 vj的闭路径 得到 v v1 vi vj 1 vk v 仍然为从 v 到 v 的闭路径 如此不断删除闭路径内相同顶点构成的闭路径 最终必可得到一条从 v 到 v 的长度不 大 于 n 的回路 2 证明 在简单无向图 G 中 从结点 u 到结点 v 如果既有奇数长度的通路又有偶数 长 度的通路 那么 G 中必有一奇数长度的回路 证证 设 G 中 从结点 u 到结点 v 的奇数长度的通路为 O 偶数长度的通路为 E 对 O 和 E 的除结点 u 和 v 的相交结点的数目归纳 k k 0 那么 O 和 E 恰好构成 G 的奇数长度的回路 设奇数长度的通路与偶数长度的通路的相交结点的数目少于 k 时 命题成立 设图 G 中 从结点 u 到结点 v 的奇数长度的通路与偶数长度的通路有 k 个相交结点 如图所示 考虑结点 u 到结点 k 如果从结点 u 到结点 k 既有奇数长度的通路又有偶数长度的通路 那么据归纳假设 其中有一奇数长度的回路 因而 G 中必有一奇数长度的回路 如果从结 点 u 到结点 k 的两条通路均为偶数长度 或均为奇数长度 那么结点 k 到结点 v 必然既有奇 数长度的通路又有偶数长度的通路 因而构成一奇数长度的回路 u 1 2 k v 6 3 证明 若简单无向图 G 是不连通的 那么 G 必定是连通的 证证 设简单无向图 G 是不连通的 那么 G 由两个不相关的子图 没有任何边关联分别 在 两个子图中的顶点 G1 G2 组成 分别有顶点 u1 u2 uk和 v1 v2 vl 由于边 ui vj 均不在 G 中 i 1 2 k j 1 2 l 因此 ui vj 全部在 G 中 从而 G 是连通的 4 有向图可用于表示关系 图 8 18 表示的二元关系是传递的吗 说说如何由有向图判 定关系的传递性 求图 8 18 表示的二元关系的传递闭包 说说构作有向图传递闭包的方法 图 8 18 解解 图 8 18 表示的二元关系不是传递的 有向图表示的关系是传递的 当且仅当对图中 任意两个结点 u v 如果有从 u 到 v 的路径 则必有从 u 到 v 的边 图 8 18 表示的二元关系的传递闭包如图 8 18 b 所示 构作有向图传递闭包的方法是 对图中任意两个结点 u v 如果有从 u 到 v 的路径 则添加从 u 到 v 的边 5 给出图 8 19 中有向图的强分图 单向分图和弱分图 作出它的凝聚图 图 8 19 解解 图 8 19 中有向图的强分图有 v1 v2 v3 v4 v5 v6 v7 v8 v9 图 8 19 中有向图的单向分图有 v1 v2 v3 v4 v5 v6 v1 v2 v7 v10 v4 v3 v8 v9 v5 v6 a b c a b c 7 v7 v8 v9 v10 图 8 19 的凝聚图 6 有 7 人 a b c d e f g 分别精通下列语言 问他们 7 人是否可以自由交谈 必要时借助他人作翻译 a 精通英语 b 精通汉语和英语 c 精通英语 俄语和意大利语 d 精通日语和英语 e 精通德语和意大利语 f 精通法语 日语和俄语 g 精通法语和德语 解解 下图中 7 个顶点表示 7 个人 关联两个顶点的边表示两个人同时精通某一种语言 由于该图是连通的 因此他们 7 人是可以自由交谈 必要时借助他人作翻译 7 证明 一个有向图是单向连通的 当且仅当它有一条经过每一结点的路径 证证 充分性是显然的 必要性 设有向图 G 是单向连通的 P 是 G 中的一条路径 起点为 u1 终点为 uk 如下 延长这一路径 考虑路径外的任意顶点 w 若 1 有顶点 w 到 u1的路径 则我们如愿 2 有顶点 uk到 w 的路径 则我们如愿 否则 由于有向图是单向连通的 3 有顶点 w 到 uk的路径 和顶点 uk 1到 w 的路径 则我们如愿 否则 由于有向图 是单向连通的 4 有顶点 w 到 uk的路径 和顶点 uk 2到 w 的路径 则我们如愿 否则 v1 v2 v3 v4 v5 v7 v8 v9 v10 v6 a b d c e g f uk 1 u1 uk w 8 5 如此等等 有顶点 w 到 uk的路径 和顶点 u1到 w 的路径 则我们如愿 如上不断延长这一路径 直至产生一条经过每一结点的路径 8 称 d u v 为图 G 中结点 u v 间的距离 否则间最短路径长度 不可达到当 当 vu vu vu vud 0 d 称为图 G 的直径 如果 d max d u v u v V 试求图 8 20 中图的直径 G G G 并指出一个点割集和一个边割集 图 8 20 解解 d 3 G 3 G 3 G 3 9 顶点 v 是简单连通图 G 的割点 当且仅当 G 中存在两个顶点 v1 v2 使 v1 到 v2 的通路都经过顶点 v 试证明之 证证充分性是显然的 必要性 设顶点 v 是简单连通图 G 的割点 如果不存在两个顶点 v1 v2 使 v1 到 v2 的通路都经过顶点 v 那么对任意两个顶点 v1 v2 都有一条通路不经过顶点 v 因而删除 顶点 v 不能使 G 不连通 与 v 是简单连通图 G 的割点矛盾 故 G 中必存在两个顶点 v1 v2 使 v1 到 v2 的通路都经过顶点 v 10 边 e 是简单连通图 G 的割边 当且仅当 e 不在 G 的任一回路上 试证明之 证证 设 e 是简单连通图 G 的割边 其端点为 u v 删除边 e 后 u v 应在两个不同的连 通分支中 若 e 在 G 的一条回路上 那么删除边 e 后 u v 应仍在一条通路上 矛盾 故 e 不在 G 的任一回路上 反之 设 e 不在 G 的任一回路上 而 e 不是简单连通图 G 的割边 那么 G e 仍是连 通的 故还有 u 到 v 的一条通路 从而这条通路连同边 e 构成 G 中的一条回路 矛盾 因 w u1 uk 2 uk 1 uk w u1 uk 2 uk 1 uk 9 此边 e 是简单连通图 G 的割边 11 试用有向图描述下列问题的解 某人 m 带一条狗 d 一只猫 c 和一只兔子 r 过河 m 每次游过河时只能带一只动物 而 没人管理时 狗与兔子不能共处 猫和兔子也不能共处 问 m 怎样把三个动物带过河去 提示 用结点代表状态 状态用序偶来表示 这里 S1 S2 分别是左岸和右 岸的人及动物集合 例如初始状态为 解解 描述上述问题的有向图如下 12 有向图可以刻划一个系统的状态转换 例如用图 8 21 中的有向图可以描述识别 010 10 序列的状态转换系统 其中 S 为初始状态 在此读入序列 然后依序列中符号转入 后续状态 读到 0 进入 S1 读到 1 进入 S2 如此等等 S4 表示读完序列 010 10 应进入的 最后状态 S5 表示读完一个非 010 10 序列应进入的最后状态 试自行构作识别序列 01 10 10 的有向图刻划的状态转换系统 上文中 w 表示空字或重复任意多次 w 所得的字 图 8 21 解解 识别序列 01 10 10 的有向图刻划的状态转换系统如下 0 S 0 S1 1 S2 1 S3 0 S4 1 0 1 S5 S3 0 1 S S1 S2 S4 S5 0 1 1 0 1 0 1 S6 10 7 3 欧拉图与哈密顿图为一 习题解答习题解答 练习练习 7 3 1 试作出四个图的图示 使第一个既为欧拉图又为哈密顿图 第二个是欧拉图而非哈 密顿图 第三个是哈密顿图却非欧拉图 第四个既非欧拉图也非哈密顿图 解解 a 既为欧拉图又为哈密顿图 b 是欧拉图而非哈密顿图 c 是哈密顿图却 非欧拉图 d 既非欧拉图也非哈密顿图 2 像第一题要求的那样对欧拉路径和哈密顿通路作出四个图 解解 a 既有欧拉路径又有哈密顿通路 b 有欧拉路径而无哈密顿通路 c 有哈 密顿通路却无欧拉路径 d 既无欧拉路径也无哈密顿通路 3 问 n 为何种数值时 Kn既是欧拉图又是哈密顿图 问 k 为何值时 k 正则图既是欧 拉图又是哈密顿图 解解 n 为奇数时 Kn既是欧拉图又是哈密顿图 k 为大于或等于 n 2 的偶数时 k 正则图 既是欧拉图又是哈密顿图 4 证明 恰有两个奇数度顶点 u v 的无向图 G 是连通的 当且仅当在 G 上添加边 u v 后所得的图 G 是连通的 证证 必要性是显然的 设 G 是恰有两个奇数度顶点 u v 的无向图 G 添加边 u v 后所得 且是连通的 那么 图 G 是一个欧拉图 每一个顶点都是偶数度的连通图 因此 G 中删除边 u v 后所得 的图 G 仍是连通的 5 参阅练习 8 1 第 2 题 问马可否从某处出发完成所有可能的跳步一次且仅一次后回 到原地 解解 练习 8 1 第 2 题中的图不是欧拉图 它有三个 3 度的顶点 因此马不可能从某处出发 完成所有可能的跳步一次且仅一次后回到原地 a b c d a b c d 11 6 参阅练习 8 1 第 2 题 问马可否从某处出发跳遍棋盘的所有方格一次且仅一次后回 到原地 解解 马可以从某处出发跳遍棋盘的所有方格一次且仅一次后回到原地 具体跳步如下图 所示 幻方中数字 n 表示第 n 个跳步的起点 下图则表示跳步的图示 5011246314372635 2362511225341538 1049642140133627 612295233283916 48760120415429 59445853321742 64725744193055 35854631564318 幻方 7 试计算 Kn n 3 中不同的哈密顿回路共有多少条 解解 不同的哈密顿回路共有条 可以用依次选取每一条边来生成哈密顿回路 2 1 n 因为组成回路的第一条边的选择可能是 n 种 组成回路的第二条边的选择可能是 n 1 种 组成回路的第 n 1 条边的选择可能是 2 种 组成回路的第 n 条边的选择可能是 1 种 而每一哈密顿回路由此生成两次 因此不同的哈密顿回路共有条 2 1 n 8 十一个学生在一张圆桌旁共进晚餐 要求在每次晚餐上每个学生的邻座都与其它各 次晚餐的邻座不同 问这样共进晚餐能安排多少次 解解 每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不同的安排方式有种 2 1 n 根据定理 8 15 12 9 判别图 8 31 中各图是否为哈密顿图 若不是 请说明理由 并回答它是否有哈密顿 通路 图 8 31 解解 a b 是为哈密顿图 c 不是哈密顿图 也没有哈密顿通路 在图 c 中增加顶 点 k 并对其顶点做二着色 构成图 d 如下 图 d 不是哈密顿图 也没有哈密顿通路 因为图中白色顶点比黑色顶点多两个 故 c 不是哈密顿图 也没有哈密顿通路 否则它的 哈密顿回路或哈密顿通路必定经过顶点 k k 在两个二度顶点之间的边上 从而图 d 也是 哈密顿图 也有哈密顿通路 矛盾 10 证明 对哈密顿图 G 删除 S V 中的所有顶点后 所得图 G 的连 通分支数不大于 S 证证 设 G1 是 G 中的哈密顿回路 显然在 G1 中删除 S V 中的所有顶点后 所得图 G1 的连通分支数 k1 不小于在 G 中删除 S V 中的所有顶点后 所得图 G 的连通分支 数 k 即 k k1 由于 G1 是一条回路 在 G1 中删除 S V 中的所有顶点后 所得图 G1 的连通分支 数 k1 不大于 S 是显然的 即 k1 S 因此 k k1 S 11 设 G 为 n m 图 证明 如果 那么 G 为哈密顿图 提示 运用2 2 1 n Cm 定理 8 14 证证 设 G 中有两个顶点 v1 和 v2 的度数之和不大于 n 1 那么以 v1 和 v2 为端点的 边不多于 n 1 条 而其余顶点之间的边的数目不多于条 故 G 的总边数 m 2 3 2 nn 满足 a b c k d 13 1 1 2 1 2 1 43 2 1 6522 2 1 3 2 2 1 1 2 1 2 2 n C nn nn nnn nnnm 与矛盾 故 G 中任意两个顶点的度数之和大于 n 根据定理 8 14 G 为哈密2 2 1 n Cm 顿图 12 设有 n 个围成一圈跳舞的孩子 每个孩子都至少与其中个是朋友 试证明 总 2 n 可安排得使每个孩子的两边都是他的朋友 证证 设 n 个孩子为 n 个顶点 用边表示顶点间的朋友关系构成一个图 G 由于每个孩子 都至少与其中个是朋友 因此 G 的每一顶点的度数至少是 从而 G 的任何两个顶点的 2 n 2 n 度数之和至少是 根据定理 8 14 G 为哈密顿图 即 G 有哈密顿回路 这表明 总可安n 排 n 个孩子围成一圈跳舞 使每个孩子的两边都是他的朋 7 4 图的矩阵表示 习题解答习题解答 练习练习 7 4 1 对图 8 35 给出的无向图 G 1 计算其关联矩阵 A G 2 计算 A G 的秩 验证定理 8 17 解解 1 其关联矩阵 A G 为 1000 1000 0110 0011 0101 5 4 3 2 1 4321 v v v v v eeee 2 由于子行列式非零 因此 A G 的秩为 3 n k 5 2 100 011 001 v1 e1 v4 e3 e4 v5 v2 e2 v3 图 8 35 14 2 对图 8 36 给出的有向图 G 1 计算它的邻接矩阵 A 及 A2 A3 A4 说出从 v1到 v4的长度为 l 2 3 4 的拟路 径各有多少条 2 计算 A A A A 说出它们中第 2 3 分量及第 4 4 分量的意义 3 计算它的路径矩阵 B 及可达性矩阵 P 并从 P 说出 G 的各强分图 解解 1 它的邻接矩阵 A v1到 v4的长度为 1 的拟路径各有 1 条 01010 10000 00000 01100 0