第11章 特殊图

《第11章 特殊图》由会员分享，可在线阅读，更多相关《第11章 特殊图（110页珍藏版）》请在金锄头文库上搜索。

1、离散数学 电子科技大学 计算机科学与工程学院示范性软件学院 2020年5月31日星期日 第11章特殊图 11 0内容提要 几个特殊图的概念 欧拉图 哈密顿图 偶图 平面图 欧拉图 哈密顿图 偶图 平面图的判定 偶图的匹配 图的着色 欧拉图 哈密顿图 偶图 平面图的应用 10 1本章学习要求 11 2欧拉图 11 2 1欧拉图的引入与定义 定义11 2 1 设G是无孤立结点的图 若存在一条通路 回路 经过图中每边一次且仅一次 则称此通路 回路 为该图的一条欧拉通路 回路 EulerianEntry Circuit 具有欧拉回路的图称为欧拉图 EulerianGraph 规定 平凡图为欧拉图 以上

2、定义既适合无向图 又适合有向图 欧拉通路和欧拉回路的特征 欧拉通路是经过图中所有边的通路中长度最短的通路 即为通过图中所有边的简单通路 欧拉回路是经过图中所有边的回路中长度最短的回路 即为通过图中所有边的简单回路 如果仅用边来描述 欧拉通路和欧拉回路就是图中所有边的一种全排列 例11 2 1 判断下面的6个图中 是否是欧拉图 是否存在欧拉通路 欧拉图 欧拉图 不是欧拉图 但存在欧拉通路 不存在欧拉通路 不存在欧拉通路 不是欧拉图 但存在欧拉通路 11 2 2欧拉图的判定 定理11 2 1无向图G 具有一条欧拉通路 当且仅当G是连通的 且仅有零个或两个奇度数结点 分析只要找到了 就是存在的 我们

3、具体找一条欧拉通路 对于结点的度数 我们在通路中去计算 证明若G为平凡图 则定理显然成立 故我们下面讨论的均为非平凡图 必要性 设G具有一条欧拉通路L 则L经过G中的每条边 由于G中无孤立结点 因而L经过G的所有结点 所以G是连通的 对欧拉通路L的任意非端点的结点 在L中每出现一次 都关联两条边和 而当重复出现时 它又关联另外的两条边 由于在通路L中边不可能重复出现 因而每出现一次都将使获得2度 若在L中重复出现p次 则deg 2p 若端点 设 在通路中作为非端点分别出现p1和p2次 则deg 2p1 1 deg 2p2 1因而G有两个度数为奇数的结点 若端点 设在通路中作为非端点出现p3次

4、则deg 1 2p3 1 2 p3 1 因而G无度数为奇数的结点 充分性 构造性证明 我们从两个奇度数结点之一开始 若无奇度数结点 可从任一结点开始 构造一条欧拉通路 以每条边最多经过一次的方式通过图中的边 对于度数为偶数的结点 通过一条边进入这个结点 总可以通过一条未经过的边离开这个结点 因此 这样的构造过程一定以到达另一个奇度数结点而告终 若无奇度数结点 则以回到原出发点而告终 如果图中所有的边已用这种方式经过了 显然这就是所求的欧拉通路 如果图中不是所有的边都经过了 我们去掉已经过的边 得到一个由剩余的边组成的子图 这个子图的所有结点的度数均为偶数 因为原来的图是连通的 因此 这个子图必

5、与我们已经过的通路在一个或多个结点相接 从这些结点中的一个开始 我们再通过边构造通路 因为结点的度数全是偶数 因此 这条通路一定最终回到起点 我们将这条回路加到已构造好的通路中间组合成一条通路 如有必要 这一过程重复下去 直到我们得到一条通过图中所有边的通路 即欧拉通路 由定理11 2 1的证明知 若连通的无向图有两个奇度数结点 则它们是G中每条欧拉通路的端点 结论 推论11 2 1无向图G 具有一条欧拉回路 当且仅当G是连通的 并且所有结点的度数均为偶数 定理11 2 2有向图G具有一条欧拉通路 当且仅当G是连通的 且除了两个结点以外 其余结点的入度等于出度 而这两个例外的结点中 一个结点的

6、入度比出度大1 另一个结点的出度比入度大1 推论11 2 2有向图G具有一条欧拉回路 当且仅当G是连通的 且所有结点的入度等于出度 欧拉通路与欧拉回路判别准则 对任意给定的无向连通图 只需通过对图中各结点度数的计算 就可知它是否存在欧拉通路及欧拉回路 从而知道它是否为欧拉图 对任意给定的有向连通图 只需通过对图中各结点出度与入度的计算 就可知它是否存在欧拉通路及欧拉回路 从而知道它是否为欧拉图 利用这项准则 很容易判断出哥尼斯堡七桥问题是无解的 因为它所对应的图中所有4个结点的度数均为奇数 也很容易得到例11 2 1的结论 定义11 2 2 设G e E 如果p G e p G 称e为G的桥

7、Bridge 或割边 Cutedge 显然 所有的悬挂边都是桥 Fleury算法 算法11 2 1求欧拉图G 的欧拉回路的Fleury算法 1 任取v0 V 令P0 v0 i 0 2 按下面的方法从E e1 e2 ei 中选取ei 1 a ei 1与vi相关联 b 除非无别的边可选取 否则ei 1不应该为G G e1 e2 ei 中的桥 3 将边ei 1加入通路P0中 令P0 v0e1v1e2 eiviei 1vi 1 i i 1 4 如果i E 结束 否则转 2 例11 2 2 用Fleury算法求欧拉图的一条欧拉回路 v1 v7 v5 v3 v2 v8 v4 e1 e2 e3 e4 e5

8、e6 e10 e7 e8 e9 e11 e12 v6 分析求从v1出发 按照Fleury算法 每次走一条边 在可能的情况下 不走桥 例如 在得到P7 v1e1v2e2v3e3v4e4v5e5v6e6v7e7v8时 G G e1 e2 e7 中的e8是桥 因此下一步选择走e9 而不要走e8 解从v1出发的一条欧拉回路为 P12 v1e1v2e2v3e3v4e4v5e5v6e6v7e7v8e9v2e10v4e11v6e12v8e8v1 11 2 3欧拉图的难点 仅有欧拉通路而无欧拉回路的图不是欧拉图 图中是否存在欧拉通路 欧拉回路图的判定非常简单 只需要数一下图中结点的度数即可 使用Fleury算

9、法求欧拉通路 回路 时 每次走一条边 在可能的情况下 不走桥 11 2 4欧拉图的应用 1 一笔画问题所谓 一笔画问题 就是画一个图形 笔不离纸 每条边只画一次而不许重复 画完该图 一笔画问题 本质上就是一个无向图是否存在欧拉通路 回路 的问题 如果该图为欧拉图 则能够一笔画完该图 并且笔又回到出发点 如果该图只存在欧拉通路 则能够一笔画完该图 但笔回不到出发点 如果该图中不存在欧拉通路 则不能一笔画完该图 例11 2 3 图中的三个图能否一笔画 为什么 解因为图 a 和 b 中分别有0个和2个奇度数结点 所以它们分别是欧拉图和存在欧拉通路 因此能够一笔画 并且在 a 中笔能回到出发点 而 b

10、 中笔不能回到出发点 图c中有4个度数为3的结点 所以不存在欧拉通路 因此不能一笔画 2 蚂蚁比赛问题 例11 2 4甲 乙两只蚂蚁分别位于图的结点A B处 并设图中的边长度相等 甲 乙进行比赛 从它们所在的结点出发 走过图中所有边最后到达结点C处 如果它们的速度相同 问谁先到达目的地 解图中仅有两个度数为奇数的结点B C 因而存在从B到C的欧拉通路 蚂蚁乙走到C只要走一条欧拉通路 边数为9条 而蚂蚁甲要想走完所有的边到达C 至少要先走一条边到达B 再走一条欧拉通路 因而它至少要走10条边才能到达C 所以乙必胜 3 计算机鼓轮设计 假设一个旋转鼓的表面被等分为24个部分 如图所示 其中每一部分

11、分别由导体或绝缘体构成 图中阴影部分表示导体 空白部分表示绝缘体 导体部分给出信号1 绝缘体部分给出信号0 根据鼓轮转动时所处的位置 四个触头A B C D将获得一定的信息 因此 鼓轮的位置可用二进制信号表示 试问如何选取鼓轮16个部分的材料才能使鼓轮每转过一个部分得到一个不同的二进制信号 即每转一周 能得到0000到1111的16个数 问题的等价描述与解决方法 问题的等价描述 把16个二进制数排成一个圆圈 使得四个依次相连的数字所组成的16个四位二进制数互不相同 问题的解决思想 设ai 0 1 i 1 2 3 16 鼓轮每转一个部分 信号就从a1a2a3a4变为a2a3a4a5 前者的右三位

12、决定了后者的左三位 我们可把所有三位二进制数作为结点 从每个结点a1a2a3到a2a3a4连一条有向边表示a1a2a3a4这个四位二进制数 作出的所有可能的码变换的有向图 所有可能的码变换的有向图 e0 0000e8 1000e1 0001e9 1001e2 0010e10 1010e3 0011e11 1011e4 0100e12 1100e5 0101e13 1101e6 0110e14 1110e7 0111e15 1111 问题的求解 问题转化为在这个有向图中找一条欧拉回路 这个有向图中8个结点的出度和入度都是2 因此存在欧拉回路 例如e0e1e2e4e9e3e6e13e10e5e11

13、e7e15e14e12e8就是一条欧拉回路 根据邻接边的标号记法 这16个二进制数的可写成对应的二进制序列0000100110101111 把这个序列排成一个圆圈 与所求的鼓轮相对应 就得到鼓轮的设计 推广 存在一个2n个二进制数的循环序列 其中2n个由n位二进制数组成的子序列全不相同 将上述2n个二进制数的循环序列称为布鲁因 DeBrujin 序列 11 3哈密顿图 11 2 1哈密顿的引入与定义 哈密顿图 定义11 3 1经过图中每个结点一次且仅一次的通路 回路 称为哈密顿通路 回路 HamiltonianEntry circuit 存在哈密顿回路的图称为哈密顿图 HamiltonianG

14、raph 规定 平凡图为哈密顿图 以上定义既适合无向图 又适合有向图 哈密顿通路和哈密顿回路的特征 哈密顿通路是经过图中所有结点的通路中长度最短的通路 即为通过图中所有结点的基本通路 哈密顿回路是经过图中所有结点的回路中长度最短的回路 即为通过图中所有结点的基本回路 如果我们仅用结点来描述的话哈密顿通路就是图中所有结点的一种全排列哈密顿回路就是图中所有结点的一种全排列再加上该排列中第一个结点的一种排列 例11 3 1 判断下面的6个图中 是否是哈密顿图 是否存在哈密顿通路 哈密顿图 不存在哈密顿通路 不是哈密顿图 但存在哈密顿通路 哈密顿图 不是哈密顿图 但存在哈密顿通路 不存在哈密顿通路 1

15、1 3 2哈密顿图的判定 定理11 3 1设无向图G 是哈密顿图 V1是V的任意非空子集 则p G V1 V1 其中p G V1 是从G中删除V1后所得到图的连通分支数 分析考察G的一条哈密顿回路C 显然C是G的生成子图 从而C V1也是G V1的生成子图 且有p G V1 p C V1 故只需要证明p C V1 V1 即可 定理11 3 1证明 设C是G中的一条哈密顿回路 V1是V的任意非空子集 下面分两种情况讨论 1 V1中结点在C中均相邻 删除C上V1中各结点及关联的边后 C V1仍是连通的 但已非回路 因此p C V1 1 V1 2 V1中结点在C上存在r 2 r V1 个互不相邻 删

16、除C上V1中各结点及关联的边后 将C分为互不相连的r段 即p C V1 r V1 一般情况下 V1中的结点在C中即有相邻的 又有不相邻的 因此总有p C V1 V1 又因C是G的生成子图 从而C V1也是G V1的生成子图 故有p G V1 p C V1 V1 推论11 3 1 设无向图G 中存在哈密顿通路 则对V的任意非空子集V1 都有p G V1 V1 1 注意 定理11 3 1给出的是哈密顿图的必要条件 而不是充分条件 定理11 3 1在应用中它本身用处不大 但它的逆否命题却非常有用 我们经常利用定理11 3 1的逆否命题来判断某些图不是哈密顿图 即 若存在V的某个非空子集V1使得p G V1 V1 则G不是哈密顿图 例11 3 2 证明图中不存在哈密顿回路 分析利用定理11 3 1的逆否命题 寻找V的某个非空子集V1使得p G V1 V1 则G不是哈密顿图 找到V1 d e f 满足要求 证明在图中 删除结点子集 d e f 得新图 它的连通分支为4个 由定理11 3 1知 该图不是哈密顿图 因而不会存在哈密顿回路 定理11 3 2 设G 是具有n个结点的简单无向图 如果对任意