离散数学(刘任任版)第5章答案.ppt

离散数学习题集 第五章图与子图 2 设G p q 是简单二分图求证 3 设G p q 是简单图 求证 q p p 1 2 在什么情况下 q p p 1 2 证明 因是简单图 所以G中任意两颗点之间最多只有一条边 故 当G为完全图时 有q p p 1 2 4 试画出四个顶点的所有非同构的简单图 共有11个 即 5 证明图5 14中的两个图是同构的 图5 15中的两个图不是同构的 试问 图5 16中的两个图是否同构 a g f h e b d c j i 1 令 2 如下图 若 a 与 b 同构 则对任何双射 必有 于是推得但d b d v 故 a 与 b 不同构 b e d a c w x v y u 3 下面两个图是同构 令 f g a b c d e 6 设G p q 是简单二分图 且 求证 G 且于是 E G p p 1 4 显然 E G 是整数 于是P或P 1是4的倍数 因此 或 或 7 构造一个简单图G 使得 如下图 令 则有 8 求证 对任何图G p q 有 而 因此即 9 设G p q 是简单图 p 2 求证 G中至少有两个顶点的度数相等 证明 假设G p q 中任何顶点的度均不相等 则p个顶点的度分别为0 1 2 p 1 1 设 则中存在孤立点 2 设 则中无顶点v满足 此与 1 矛盾 总之 0和p 1不能同时出现 由抽屉原理知 必有 使 10 求证 在图G p p 1 中 至少有一个顶点v 满足d v 3 证明 若对任意 均有 则有即 也即 从而 矛盾 故存在 使 11 求证 在任何有n n 2 个人的人群中 至少有两个人在其中恰有相同个数的朋友 证明 作一个n阶简单图 n个顶点分别表示n个人 两个人是朋友当且仅当表示这两个人的顶点邻接 这样 问题就转化成中至少有两个顶点的度数相等 此结论题9已证 12 求证 每一个p阶简单图G 都与Kp的子图同构 证明 因任何一个P阶简单图G Kp 又 故结论成立 13 求证 任何完全图的每个点导出子图仍是完全图 证明 由点导出子图的定义及完全图的结构即知结论成立 14 求证 二分图的每个顶点数不小于2的子图仍是二分图 证明 设 且 令 显然 且 因此 15 设G p q 是简单图 整数n满足1 n p 1 求证 若p 4 且G的所有n个顶点的导出子图均有相同的边数 则或 证明 若和均不成立 则存在使得u与v邻接 而w与x不邻接 于是取n 2 则与边数不相同 矛盾 故或 16 1 设G p q 是连通图 求证 G至少有p 1条边 证明 对p用归纳法a p 1时 显然成立 b 假设对于小于p的自然数 结论成立 c 在p阶连通图中任取一个顶点v 设G v共有k个分支 且每个分支有Pi个顶点 Pi P 于是由归纳假设可知G Vi 至少有Pi 1条边 从而G v至少有 P 1 k条边 故G至少有P 1条边 16 2 设G p q 是连通图 求证 若q p 1 则G中必含回路 证明 设 若G不含回路 则必有满足 于是仍连通且无回路 而恰有条边 如此下去 连通无回路且恰含条边 一个顶点 此时是一个平凡图 从而即 此与矛盾 故G必含回路 16 3 设G p q 是连通图 求证 若q p 1 则G至少有两个悬挂点 证明 设 若对任何 均有 则 即 此与矛盾 故G中至少有一个悬挂点 又若G中最多只有一个悬挂点 则即 从而得出 矛盾 故G中至少有两个悬挂点 17 求证 若边e在图G的一条闭链中 则e必在G的一条回路中 证明 设 G中含e的闭链为 若E不是回路 则必有 因为回路定义是 没有重复点 从E中去掉 得到仍为闭链 如此下去 就可得到含的回路 18 求证 对于图G p q 若 则G中必含回路 证明 G中无悬挂点 任取 设v1与v0邻接 如此下去 可得G中的一条链又因G是有限图 由此可得一条闭链 由第 题的证明过程可知 故此链上必有回路 19 设G p q 是简单图 且 求证 G是连通图 证明 若G不连通 则可将V G 划分成V1 V2 使得V1中的顶点与V2中的顶点不邻接 令 于是 且 即矛盾 故连通 另解 考虑 则有 因为p p 1 2是完全图的边数 即不连通 于是 G连通 20 对于p 1 作一个的非连通图 证明 令 作如下 故G不连通 21 1 证明 若 p q 是简单图 且 则G连通 证明 1 设 若G不连通 则G的顶点可划分成两个集合 使得V1与V2中的顶点互不邻接 不妨设 则 由G是简单图知 因为 从而矛盾 故G必连通 21 2 当p为偶数时 作一个非连通的k 正则简单图 其中 取p 6 则 作非连通图G如下 22 证明 若e E G 则 证明 因G的任意一条边e最多联结G e的两个分支 故 23 证明 对图G中任意三个顶点u v和w d u v d v w d u w 证明 若d u v d v w d u w 则与距离的概念不符 因为距离的定义是 连接两点之间的最短路径的长度 故结论成立 24 设G是简单连通的非完全图 求证 G中存在三个顶点u v和w 使uv vw E G 但uwE G 证明 反证法 若不然 即对任意的 只要 就有 也即且 1 今任取 由G连通知 存在 通路 于是由 1 可知 且且 且从而推得简单图G中任何两个顶点均邻接 即G是一个完全图 此与题设矛盾 25 证明 若G是简单图 且 则G中有一条长度至少是的回路 证明 不妨设连通 否则可对其分支进行讨论 于是 即G中至少有个顶点 设是G中的一条极长通路 则v1不与P以外的任何顶点邻接 如果存在就与P是极长通路矛盾 又因 所以存在P上的个顶点均与v1邻接 于是有回路 显然 26 求图5 17的关联矩阵和邻接矩阵 邻接矩阵为 27 设G是简单图 M G 和A G 分别是G的关联矩阵和邻接矩阵 1 求证 M G 中每列各元素之和为2 2 A G 的各列元素之和是什么 1 证明 因每条边恰与两个端点u v关联 2 若上无环 则所在列 行 各元素之和为 否则所在列 行 各元素之和为 28 设G是二分图 求证 可以将G的顶点作适当排列 使得G的邻接矩阵M G 形如其中 A21是A12的转置 证明 因为G是二分图 所以G中无环 设 令则其中 且 29 设G是一个图 1 如何从得到和 2 如何从得到 解 1 对每个 将中所在列的元素全置为0 则得 2 对每个 将中所在行的元素全置为0 则得到 3 对每个 将中所在行与列的元素全置为0 则得到 30 在图5 18中 找出从U1到各个顶点的最短通路长度 并给出从U1到U11的最短通路 迭代WD 2 D 3 D 4 D 5 D 6 D 7 D 8 D 9 D 10 D 11 初始 1 2811 1 4 428102 1 4 2 2 8 3103 1 4 2 5 58 6105124 1 4 2 5 8 88610 12145 1 4 2 5 8 6 67 1012146 1 4 2 5 8 6 3 3 912147 1 4 2 5 8 6 3 7 7 1210148 10 1011 149 9 9 13 最后得D 2 2 D 3 7