大学离散数学 欧拉图与哈密尔顿图.ppt

* * 15.2.4 应用举例 分析 穷举法 近似算法 ………… * 通过G的每条边一次且仅一次的通路称为G的欧拉通路／Euler Path／E路径； 通过G的每条边一次且仅一次的回路称为G的欧拉回路／Euler Circuit／E回路； 具有欧拉回路的图称为欧拉图(Eulerian)。 半欧拉图 规定：平凡图是欧拉图 * 若G存在欧拉回路： P＝（v0e1v1e2……ekv0） （其中:对?i,j(1≤i＜j≤k),有ei≠ej,且P中包含G中所有的边） 显然图连通； 另外：当沿着该路径往下走，每经过一个顶点，都需要经过关联该顶点的两条边，且这两条边从未画过，即：使顶点的度增加2，故G中无奇度顶点。 再证充分性（构造性证明）： 若G连通，且无奇度顶点，我们来构造一条欧拉回路。 任取一个顶点作为起点，以每条边最多经过一次的方式通过图的边。 对经过的每个点（偶度点），有一条边进去，总可以通过一点从未走过的边离开该顶点，这样总可以回到原出发点，构造条简单回路L1。若L1经过图中所有的边，则L1就是欧拉回路. 不然，去掉已经画过的边，得到余下边组成的子图G1，该子图的顶点均为偶度点，而G是连通的，G1和L1至少在一个顶点vi相接,于是在G1中从v1出发，重复第1步，得到回路L2。若L1∪L2经过图中所有的边，则得欧拉通路；否则重复第3步，得到回路L3，由于E有限，故存在欧拉回路。 * ？ （我国数学家管梅谷教授，于1962年写出论文解决了这一问题，被国际数学界称为中国邮路问题。） * 若是欧拉图，则G的欧拉回路就是问题的最优解。 若G恰有2个奇度点，且邮局所在的点就是其中一个奇度点，则G具有欧拉通路，则邮递员走遍所有的街道一次到达另一个奇度点，这时再选择其间的一条最短路径返回邮局。这样，中国邮路问题转化为求G的欧拉通路和两点的最短路径问题。 若G中次数为奇数的结点多于2，则回路中必须增加更多的重复边，这时，怎样使重复边的总长度最小？ * 这个问题是从哈密尔顿发明的一个数学游戏引出的。1859年哈密尔顿发明了一种游戏，并作为一个玩具以25个金币卖给了一个玩具商。这个玩具是用12个正五边形的面做成的一个正12面体，这个12面体共20个顶点，并以世界上20个著名城市名命名，要求游戏者沿着这个12面体的棱，走遍每个城市一次且仅一次，最后回到出发点。他把这个游戏称之为“周游世界”游戏。 这就是“绕行世界”问题。即找一条经过所有顶点（城市）的基本道路（回路）。 * Willam Rowan Hamilton(1805~1865): 爱尔兰神童(child prodigy)——三一学院(Trinity College) 四元数(quaternion)：a+bi+cj+dk, 放弃乘法交换律! 1843年10月16日，在数学史上是一个重要的日子：这一天爱尔兰的数学家哈密尔顿（William Rowan Hamilton）发现了“四元数”（Quaternion）。 许多数学家认为“四元数”的发现是19世纪纯数学方面的一个最重要的发现。爱尔兰政府为了纪念这个发现，在1943年特别发行了纪念哈密尔顿的邮票（图一）。 注： 该图满足定理15.6的条件, 这表明此条件是必要、而不充分的. * 计算机科学学院 刘芳 计算机科学学院 刘芳 * * 第15章 欧拉图和哈密顿图 15.1 欧拉图 15.2 哈密尔顿图 * * 15.1 欧拉图 15.1.1 问题引入 15.1.2 欧拉图 15.1.3 欧拉图的判定定理 15.1.4 中国邮路问题 * * 15.1.1 问题引入 哥尼斯堡七桥问题 Seven bridges of K?nigsberg problem 问题分析： A C B D * * 15.1.2 欧拉图 定义15.1： 设Ｇ＝＜V，E＞是连通图 欧拉通路（Euler Path） 半欧拉图 欧拉回路（Euler Circuit） 欧拉图 (Eulerian) 说明 规定平凡图是欧拉图； 欧拉通路是简单通路, 欧拉回路是简单回路； 环不影响图的欧拉性。 * * 15.1.2 欧拉图 实例 * * 15.1.3 欧拉图的判定定理 无向欧拉（半欧拉）图的判定定理 定理15.1 无向图G是欧拉图? G是连通的且无奇度顶点。 定理15.2 无向图G是半欧拉图? G是连通的，且G中恰有2个奇度顶点 * * 15.1.3 欧拉图的判定定理 例1： 无欧拉通(回)路 欧拉图 欧拉图 半欧拉图 半欧拉图 无欧拉通(回)路 * * 15.1.3 欧拉图的判定定理 例2： A C B D * * 15.1.3 欧拉图的判定定理 例3：一笔画问题及推广 问题描