6.5 欧拉、哈密顿通路.ppt

第六章图论Graphs 图 Graph 可直观地表示离散对象之间的相互关系 研究它们的共性和特性 以便解决具体问题 6 1图的概述 IntroductionofGraph6 2图的术语 GraphTerminology6 3图的表示与同构 RepresentingGraphandGraphIsomorphism6 4连通性 Connectivity6 5欧拉通路与哈密顿通路 EulerandHamiltonPaths6 6最短通路问题 ShortestPathProblem6 7平面图 PlanarGraphs6 8图的着色 GraphColoring 学习内容 6 5欧拉通路与哈密顿通路EulerandHamiltonPath Konigsberg 哥尼斯堡 七桥问题 问题 能否从河岸或小岛出发 通过每一座桥 而且仅仅通过一次回到原地 Euler 欧拉 1736年对这个问题 给出了否定的回答 将河岸和小岛作为图的顶点 七座桥为边 构成一个无向多重图 问题化为图论中简单回路的问题 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 定义1 欧拉通路 回路 G V E 称包含E中所有边的简单通路为欧拉通路 EulerPath E通路 包含E中所有边的简单回路为欧拉回路 EulerCircuit E回路 注 包含欧拉回路的图称为欧拉图 E图 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 例1图中是否存在欧拉回路 若无 存在欧拉通路 6 5欧拉通路与哈密顿通路EulerandHamiltonPath G1存在欧拉回路eabedceG2不存在欧拉回路和欧拉通路G3存在欧拉通路adcabdeb 例2图中是否存在欧拉回路 若无 存在欧拉通路 6 5欧拉通路与哈密顿通路EulerandHamiltonPath H1不存在欧拉回路和欧拉通路H2存在欧拉回路agcbedfaH3不存在欧拉回路 存在欧拉通路cabcdb 定理1 欧拉定理 没有度为0的孤立顶点的无向图存在欧拉通路的充要条件是 1 图是连通的 2 图中奇度顶点个数是0个或2个 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 证明 必要性 若存在欧拉通路 且没有0度顶点 则每个顶点都有边关联 而边又全在欧拉通路上 故所有顶点都连通 除了起点 终点外 欧拉通路每经过一个顶点 使顶点的度增加2 故只有起点和终点才可能成为奇度顶点 而一个奇度顶点是不可能的 当无奇度顶点时 是欧拉回路 充分性 若 1 2 成立 构造欧拉通路 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 若图G存在奇度顶点 任取一个作为起点 若不存在 则任取一个顶点作为起点 若此图有n条边 总度为2n 每进入或离开一个顶点 让此顶点的度减1 由于除了两个 或没有 奇度顶点外 其余顶点度为偶数 只要进得去 一定出得来 直至进入另一个奇度顶点 或起点 作为终点 这样构造的是简单通路 如果经过所有的边 即得到一条欧拉通路 不然 记走过的简单通路为p1 p1上顶点集V1 边集E1 G1 V1 E1 是G的子图 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 若G2 V2 E2 是G1的关于G的补图 E2 E E1 但V1 V2 否则G不连通 设C V1 V2 从C出发 用上面方法作G2的简单回路p2回到C 这能做到 因为作好p1后 留下顶点的度都是偶度 若p1 p2经过所有边 则欧拉通路是p1走到C时 先把p2走完 最后走完p1的余下通路 若p1 p2仍未经过所有边 将p1 p2视为p1重复上述过程 由于E边有限 故存在欧拉通路 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 例1 1 顶点的度 A 3 B 2 C 4 D 2 E 6 F 2 G 6 H 2 I 4 J 3 其中奇度顶点A J2 从A出发 走一条通路P1 A C E A B C D E F G H I J 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 3 G1 V1 E1 V1 A B C D E F G H I J E1 A C C E E A A B B C C D D E E F F G G H H I I J 则G2 V2 E2 E2 E G E J J G G I I G V2 E G I J E V1 V2 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 4 在G2中从E出发回到E的回路 E J G E 加入到P1中P1 A C E A B C D E J G E F G H I J 5 还有未经过的边 重复上述过程 从G出发 G I G 再加入即得欧拉通路 P1 A C E A B C D E J G E F G I G H I J 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 推论1 欧拉定理 没有度为0的孤立顶点的无向图存在欧拉回路的充要条件是 1 图是连通的 2 图中没有奇度顶点 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 定理2 有向图的欧拉定理 不含出 入度为0的孤立顶点的有向图具有欧拉通路的充要条件是 1 弱连通 2 除了可能有2个顶点 一个入度比出度大1 一个出度比入度大1 其余顶点出度等于入度 推论 不含出 入度为0的孤立顶点的有向图具有欧拉回路的充要条件是 1 弱连通 2 所有顶点出度等于入度 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 欧拉通路 回路的应用与推广 1 一笔画问题2 如果奇度顶点个数为2K个 此问题是K笔画问题3 中国邮递员问题4 电路布线 网络组播和分子生物学 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 欧拉通路 回路的应用与推广 1 一笔画问题2 如果奇度顶点个数为2K个 此问题是K笔画问题3 中国邮递员问题4 电路布线 网络组播和分子生物学 6 5欧拉通路与哈密顿通路EulerandHamiltonPath Hamilton 哈密顿 通路问题 1857年发明的一种游戏 在一个实心的正十二面体 20个顶点标上世界著名大城市的名字 要求游戏者从某一城市出发 遍历各城市一次 最后回到原地 这就是 绕行世界 问题 即找一条经过所有顶点 城市 的基本回路 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 定义1 哈密顿通路 回路 G V E G中经过V中所有顶点的基本通路称为哈密顿通路 HamiltonPath 简称H通路 G V E G中经过V中所有顶点的基本回路称为哈密顿回路 HamiltonCircuit 简称H回路 注 存在哈密顿回路的图称为哈密顿图 H图 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 图A每个顶点都是奇度的 不存在E通路 但有H通路 图B存在E通路 不存在H通路 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 有哈密顿回路或通路吗 图G1有H回路 图G2有H通路 无H回路 图G3无H通路 也无H回路 定理3 设G V E 是n个顶点的简单图 如果任一对不相邻的顶点度之和 n 1 则G中一定有H通路 n 2 证明 1 G一定连通 否则G分为二个不连通的分图G1 G2 其中G1有n1个顶点 G2有n2个顶点 G1中每个顶点度 n1 1 G2中每个顶点度 n2 1 从G1中取一个顶点 G2中取一个顶点 这一对顶点度之和 n1 1 n2 1 n1 n2 2 n 2 n 1 与定理的假设矛盾 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 注意 此定理条件显然不是必要条件 如n 6的n边形 二个顶点度之和 4 4 n 1 而n边形显然有H通路 2 用归纳法证明G中存在H通路 任取一条边 V1 V2 是含2个顶点的基本通路 如果已有p个顶点的基本通路 V1 V2 Vp p n 1 必能构造p 1个顶点的基本通路 a 如果在V V1 V2 Vp 中存在与V1或Vp相邻的顶点 则基本通路自然可以扩充一个顶点 b 如果V1 Vp仅与 V1 V2 Vp 中顶点相邻 则 V1 V2 Vp 必可适当排列 形成回路 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 如果V1与Vp相邻 显然成了环 不然 由于V1 Vp仅与 V1 V2 Vp 中顶点相邻 V1 Vp的度 p 1 不妨设V1的度为k p 1 分别记相邻顶点为Vi1 Vi2 Vik 它们前面的顶点 指在基本通路 V1 V2 Vp 中的序 为 Vp必与中某顶点相邻 否则Vp的度 p 1 k V1与Vp的度之和 k p 1 k p 1 n 1 与任一对顶点度之和 n 1矛盾 不妨Vp与Vj 1相邻 V1与Vj相邻 将V1与Vj连起来 Vp与Vj 1连起来 并将Vj 1到Vj的边去掉 就形成一个环 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 又由G的连通性 总可在V V1 V2 Vp 中找到一个点Vx 与 V1 V2 Vp 中某一顶点相邻 不妨与Vk相邻 Vk V1 Vk Vp 连上Vx与Vk的边 去掉Vk 1到Vk的边 可以从Vk 1为起点 一直走到Vk 再到Vx 这是一条p 1个顶点的基本通路 如果p 1 n 仍继续扩充基本通路内的顶点 直至达到n 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 推论 奥尔定理 G V E 是n 3的简单图 若任何一对不相邻顶点的度之和 n 则G必有哈密顿回路 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 由于推论条件也必满足定理3条件 存在H通路 可类似于定理1的方法找到一条H回路 定理5 无向 有向完全图一定存在H通路 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 定理4 狄拉克定理若G是带n个顶点的连通简单图 n 3 且G中每个顶点的度都至少为n 2 则G有哈密顿回路 要判别一个图不存在H通路 H回路 也不是很容易的 只能对无向图给出一些必要条件 1 H通路存在必要条件 连通 至多只能有二个顶点的度 2 其余顶点的度 2 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 2 H回路存在必要条件 对V的任一非空真子集S G S的连通分支个数 S 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 解 取S A1 A2 G S存在3个连通分支 根据H回路存在的必要条件之二 可知H回路不存在 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 应用问题之一 Knight stour应用问题之二 GrayCode应用问题之三 TowerofHanoi 6 5欧拉通路与哈密顿通路EulerandHamiltonPath 旋转的指针的位置可以表示成数字的形式 一种方式是把圆周等分成2n段弧并且用长度为n的位串给每段弧赋值 格雷码GrayCode 在指针上用n个接触点来确定指针位置 每个接触点用来读出位置的数字表示中的一位 格雷码GrayCode 当指针靠近两段弧的边界时 读出指针的位置可能出错 格雷码GrayCode 3位都错 最多1位错 可用n立方体Qn来为问题建模弧的满足要求的标记就是求Qn的一个哈密顿回路 格雷码GrayCode Q3 格雷码是上世纪40年代弗兰克 格雷为把数字信号传送过程中错误的影响降到最低而发明的 思考题 在某次国际会议的预备会议中 共有8人参加 他们来自不同的国家 已知他们中任何两个无共同语言的人中的每一个 与其余有共同语言的人数之和大于或等于8 问能否将这8个人排在圆