离散数学图论部分综合练习辅导.pdf

1 离散数学离散数学图论部分图论部分综合练习辅导综合练习辅导 本次活动是本学期的第二次活动 2008 11 18 主要是针对第二单元图论的 重点学习内容进行辅导 方式是通过讲解一些典型的综合练习题目 帮助大家进 一步理解和掌握图论的基本概念和方法 图论作为离散数学的一部分 主要介绍图论的基本概念 理论与方法 教学 内容主要有图的基本概念与结论 图的连通性与连通度 图的矩阵表示 最短路 问题 欧拉图与汉密尔顿图 平面图 对偶图与着色 树与生成树 根树及其应 用等 本次综合练习主要是复习这一部分的主要概念与计算方法 与集合论一样 也安排了五种类型 有单项选择题 填空题 判断说明题 计算题 证明题 这 样的安排也是为了让同学们熟悉期末考试的题型 能够较好地完成这一部分主要 内容的学习 下面分别讲解 一 单项选择题一 单项选择题 1 设图 G 的邻接矩阵为 01010 10010 00001 11000 00100 则 G 的边数为 A 5 B 6 C 3 D 4 正确答案 D 上学期的作业中 有的同学选择答案 B 主要是对邻接矩阵的概念理解不到 位 我们复习定义 定义定义3 3 1 设G 是一个简单图 其中V v1 v2 vn 则 n阶方阵 A G aij 称为G的邻接矩阵邻接矩阵 其中各元素 jivv vv a ji ji ij 不相邻或与 相邻与 0 1 而当给定的简单图是无向图时 邻接矩阵为对称的 即当结点vi与vj相邻时 结点vj与vi也相邻 所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j 行第i列处各有一个1 题中给出的邻接矩阵中共有8个1 故有8 2 4条边 2 设图 G 则下列结论成立的是 A deg V 2 E B deg V E C Ev Vv 2 deg D Ev Vv deg 正确答案 C 2 该题主要是检查大家对握手定理掌握的情况 复习握手定理 定理 3 1 1 设 G 是一个图 其结点集合为 V 边集合为 E 则 Vv Ev 2 deg 3 图 G 如右图所示 以下说法正确的是 A a d 是割边 B a d 是边割集 C d e 是边割集 D a d a c 是边割集 正确答案 C 上学期许多同学选择答案 A 主要是对割边 边 割集的概念理解不到位 复习割边 边割集的定义 定义定义 3 2 9 设无向图 G 为连通图 若有边集 E1 E 使图 G 删除了 E1的所有边后 所得的子图是不连通图 而删除了 E1的任何真子集后 所得的 子图是连通图 则称 E1 是 G 的一个边割集边割集 若某个边构成一个边割集 则称该 边为割边割边 或桥桥 如果答案 A 正确 即删除边 a d 后 得到的图是不连通图 但事实上它还 是连通的 因此答案 A 是错误的 4 设 G 是连通平面图 有 v 个结点 e 条边 r 个面 则 r A e v 2 B v e 2 C e v 2 D e v 2 正确答案 A 该题主要是检查大家对平面图的欧拉定理的理解情况 定理4 3 2 欧拉定理 设连通平面图G的结点数为v 边数为e 面数为r 则下列欧拉公式成立 v e r 2 5 无向图 G 存在欧拉通路 当且仅当 A G 中所有结点的度数全为偶数 B G 中至多有两个奇数度结点 C G 连通且所有结点的度数全为偶数 D G 连通且至多有两个奇数度结点 正确答案 D 上学期许多同学选择答案 C 主要是将题中的 欧拉通路 误认为 欧拉回 路 了 其实应该运用定理 4 1 1 进行选择 才是正确的 复习定义和定理 定义4 1 1 给定无孤立结点图G 若存在一条路经过图G的每条边一次且仅 一次 则该路称为欧拉路 若存在一条回路经过图G的每条边一次且仅一次 在该回路称为欧拉回路 定理 4 1 1 无向图 G 具有一条欧拉路 当且仅当 G 是连通的 且有零个 c a b e d f 3 或 2 个奇数度数的结点 推论 一个无向图具有一条欧拉回路 当且仅当该图是连通的 并且它的结 点度数都是偶数 所以 正确答案应该是 D 6 设 G 是有 n 个结点 m 条边的连通图 必须删去 G 的 条边 才能 确定 G 的一棵生成树 A 1mn B mn C 1mn D 1nm 正确答案 A 上学期许多同学选择答案 D 主要是把定理 5 1 1 给出的图 T 为树的等价定 义之一是图 T 连通且 e v 1 中的公式用错了 大家只要把 m 代入公式 e v 1 中 的 e 把 n 代入公式 e v 1 中的 v 可以知道答案 A 是正确 定理5 1 1 给定图T 则以下关于图T为树的定义等价 1 无回路的连通图 2 无回路且e v 1 其中e是边数 v是顶点数 3 连通且e v 1 4 无回路 但增加任一新边 得到且仅得到一个回路 5 连通 但删去任一边后图便不连通 v 2 6 每一对顶点之间有且仅有一条路 v 2 定理 5 1 1 的六个等价定义 大家应该熟记的 最主要的是 无向简单图 G 是棵 树 当且仅当 G 连通且边数比结点数少 1 二 填空题二 填空题 1 已知图 G 中有 1 个 1 度结点 2 个 2 度结点 3 个 3 度结点 4 个 4 度结 点 则 G 的边数是 应该填写 15 主要检查大家对握手定理掌握的情况 定理定理 3 1 1 握手定理 设 G 是一个图 其结点集合为 V 边集合为 E 则 Vv Ev 2 deg 因为图 G 中有 1 个 1 度结点 2 个 2 度结点 3 个 3 度结点 4 个 4 度结点 即 Vv v3044332211 deg 所以边数有152 30 E 问 若无向树 T 中有 8 个结点 4 度 3 度 2 度的分 支点各一个 那么 T 的树叶数为多少 2 设给定图 G 如右图所示 则图 G 的点割集是 应该填写 f c e 上学期许多同学填错答案主要对点割集的概念理解 不正确 c a b e d f 4 定义定义3 2 7 设无向图G 为连通图 若有点集V1 V 使图G删除了V1 的所有结点后 所得的子图是不连通图 而删除了V1的任何真子集后 所得的子 图是连通图 则称V1是G的一个点割集点割集 若某个结点构成一个点割集 则称该结 点为割点割点 上学期许多同学填写的 f c 主要是没有完全理解定义 3 2 7 因为 f 是 f c 的真子集 而删除 f 后 图是不连通的 3 设无向图 G 是汉密尔顿图 则 V 的任意非空子集 V1 都有 V1 应该填写 W G V1 因为具有汉密尔顿回路的图称为汉密尔顿图 而由 定理4 2 1 若图G 中具有一条汉密尔顿回路 则对于结点集V的每 个非空子集S均有W G S S 成立 其中W G S 是 G S 中连通分支数 因此应该填写 W G V1 4 设有向图 D 为欧拉图 则图 D 中每个结点的入度 应该填写 等于出度 如果大家记住 具有欧拉回路的图称为欧拉图欧拉图 和定理定理 4 1 2 一个有向图 具有单向欧拉回路 当且仅当它是连通的 且每个结点的入度等于出度 大家一 定能填写出正确答案的 5 设完全图 Kn有 n 个结点 n 2 m 条边 当 时 Kn中存在欧 拉回路 应该填写 n 为奇数 上学期许多同学填错答案主要对完全图的概念理解不正确 定义定义 3 1 6 简单图 G 中 若每一对结点间都有边相连 则称该图 为完全图完全图 有 n 个结点的无向完全图记为 Kn 由定义可知 完全图 Kn中的任一结点 v 到其它结点都有一条边 共有 n 1 条边 即每个结点的度数是 n 1 当 n 为奇数时 n 1 为偶数 由定理 4 1 1 的推论可知 应该填写 n 为奇数 6 给定一个序列集合 1 01 10 11 001 000 若去掉其中的元素 则该序列集合构成前缀码 应该填写 1 因为在二进制中1是10和11的前缀 而前缀码的定义是 定义5 2 10 给定 一个序列集合 若没有一个序列是另一个序列的前缀 该序列集合称为前缀码前缀码 填写该题答案时大家一定要对前缀码的定义理解非常清楚 问 若把序列集合中的 1 换成 0 应该去掉哪个元素 三三 判断说明题 判断说明题 1 给定两个图 G1 G2 如下图所示 1 试判断它们是否为欧拉图 汉密尔顿图 并说明理由 5 2 若是欧拉图 请写出一条欧拉回路 分析 分析 先复习欧拉图的判别定理和汉密尔顿图的定义 定理 4 1 1 的推论 一个无向图具有一条欧拉回路 当且仅当该图是连通的 并且它的结点度数都是偶数 定义 4 2 1 若存在一条回路经过图G的每个结点一次且仅一次 则该回路 称为汉密尔顿回路 具有汉密尔顿回路的图称为汉密尔顿图 解 解 1 图 G1是欧拉图 因为图 G1中每个结点的度数都是偶数 图G2是汉密尔顿图 因为图 G2存在一条汉密尔顿回路 不惟一 a a b b b e e e f f f g g g d d d c c c a a 问题 请大家想一想 为什么图 G1不是汉密尔顿图 图 G2不是欧拉图 2 图 G1的欧拉回路为 不惟一 v1 v1 v2 v2 v2 v3 v3 v3 v4 v4 v4 v5 v5 v5 v2 v2 v2 v6 v6 v6 v4 v4 v4 v1 v1 上学期的学生在书写欧拉回路时不规范 大家要按照正确的方法写法 2 判别图 G 如右图所示 是不是平面图 并说明理由 分析 平面图的定义是 定义4 3 1 设G 是一个无向图 如果能把G的所有结点与边画在平面上 并且 使得任何两条边除端点外没有其他的交点 则 称G是一个平面图 也称可平面图 显然平面图的边与边只在结点处相交 解解 图 G 是平面图 因为只要把结点 v2与 v6的连线 v2 v6 拽 到结点 v1的外面 把把结点 v3与 v6的连线 v3 v6 拽到结点 v4 v5的外面 就得到一个平 面图 注意 定理4 3 3 设G是一个有v个结点e条边 的连通简单平面图 若v 3 则e 3v 6 会用于判断不是平面图 四 四 计算题计算题 v1 v2 v3 v4 v5 v6 v5 v1 v2 v4 v6 v3 v5 v1 v2 v4 v6 v3 6 1 设图 G V E 其中 V a1 a2 a3 a4 a5 E a1 a2 a2 a4 a3 a1 a4 a5 a5 a2 1 试给出 G 的图形表示 2 求 G 的邻接矩阵 3 判断图 G 是强连通图 单侧连通图还是弱连通图 解解 1 图 G 是有向图 2 邻接矩阵如下 00010 10000 00001 01000 00010 DA 3 图 G 是单侧连通图 也是弱连通图 关于强连通图 单侧连通图还是弱连通图的判断 希望大家掌握图论综合作业单 项选择题中的第 4 题 2 图 G 其中 V a b c d e f E a b a c a e b d b e c e d e d f e f 对应边的权值依次为 5 2 1 2 6 1 9 3 及 8 1 画出 G 的图形 2 写出 G 的邻接矩阵 3 求出 G 权最小的生成树及其权值 解 1 因为 V a b c d e f E a b a c a e b d b e c e d e d f e f 权值依次为 5 2 1 2 6 1 9 3 及 8 所以 G 的图形如右图所示 2 分析 定义3 3 1 设G 是一个简单图 其中V v1 v2 vn 则n阶方阵A G aij 称为G的邻接矩阵 其中 0 1 jivv vv a ji ji ij 不相邻或与 相邻与 邻接矩阵 011000 101111 110010 010001 011001 010110 3 用避圈法 第 1 步 选 a e 和 c e 边 第 2 步 选 b d 边 为什么不选 a c 第 3 步 选 d f 边 a1 a2 a3 a4 a5 c a b e d f 1 5 2 2 6 1 9 3 8 c a b e d f 1 5 2 2 6 1 9 3 8 7 第 4 步 选 a b 边 这样 得到了最小的生成树 如右图中粗线所示 最小的生成树的权为 1 1 5 2 3 12 上学期作业中的最小的生成树求的不对 主要是没有把握 取权数最小的边 且 与前面取到的边不构成圈 常常是只注意取权数最小的边了 而忽略 不构成 圈 的要求 问 如果结点集是 V a b c d e 边集 E a b a c a e b d b e c e d e 对应边的权值依次为 5 2 1 2 6 1 9 那么会求吗 3 设有一组权为 2 3 5 7 11 13 17 19 23 29 31 试 1 画出相应的最优二叉树 2 计算它们的权值 解 1 最优二叉树如右图所示 方法方法 Huffman 从 2 3 5 7 11 13 17 19 23 29 31 中选 2 3 为最低层结点 并 从权数中删去 再添上他们的和数 即 5 5 7 11 13 17 19 23 29 31 再从 5 5 7 11 13 17 19 23 29 31 中选 5 5 为倒数第 2 层结点 并从上述数列中 删去 再添上他们的和数 即 7 10 11 13 17 19 23 29 31 然后 从 7 10 11 13 17 19 23 29 31 中选 7 10 和 11 13 为倒数第 3 层结点 并 从上述数列中删去 再添上他们的和数 即 17 17 24 19 23 29 31 2 权值为 2 6 3 6 5 5 7 4 11 4 13 4 17 3 19 3 23 3 29 3 31 2 12 18 25 28 44 52 51 57 69 87 62 505 讲评讲评 作业中最优二叉树都画对了 但计算总权值时把有些权的层数计算错了 导致总权值计算错误 问 如果一组权为 2 3 6 9 13 15 能否画出最优二叉树 五五 证明证明题题 证明题上学期的学生做的很不好 原因是他们对证明题方法没有掌握 也是 对一些概念不清楚所造成的 因此 希望大家认真学习教材和老师讲课中的证明 方法 并通过作业逐步掌握做证明题的方法 1 若无向图 G 中只有两个奇数度结点 则这两个结点一定是连通的 证明 证明 用反证法 设 G