第四章 Euler图和Hamilton图.pptVIP

顺时针分别旋转（旋转时顶点的标记不动） 如如图所示。 每旋转一次便产生一条哈密顿回路，且它们之间没有公共边。图10.2.5演示了n=5时的情景(图（b）是图（a）旋转90°后所得)，因此，合乎要求的哈密顿回路共有1+ (n-3)/2=(n-1)/2条。 货郎担问题(Travelling Salesman Problem,TSP) 与哈密顿图密切相关的是货郎担问题。设有n个村镇，已知每两个村镇之间的距离。一个货郎自某个村镇出发巡回售货，问这个货郎应该如何选择路线，使每个村镇经过一次且仅一次，并且总的行程最短。即在一个带权完全图中，找一个权最小的哈密顿图。 在n个顶点的带权完全图中，所有不同的哈密顿回路（包括有公共边的情况）总数是1/2 (n-1)！个。在如此众多的哈密顿回路中求一个总的权为最小的哈密顿回路，它的工作量是相当大的，这种求最优解的有效率的算法至今尚未找到。下面我们给出一个较好的近似算法——最邻近算法。 设G=〈V,E,w〉是n个顶点的带权完全图，w是从E到正整数集Z+的函数，对V中的任何三个顶点vi，vj，vk满足w(vi，vj）+w（vj，vk）≥w（vi，vk） 求最小权的哈密顿回路的最邻近算法步骤如下： （1）任选一点v0作起点，找一个与v0最近的相邻顶点vx，得到一条一边构成的路径。 （2）设vx是新加到这条路中的一点，从不在此路中的所有顶点中，选一个与vx最近的相邻点，将它与vx连成一边，构成一条新的路径。重复过程（2），直到G中所有顶点都在所构成的路径中。 （3）连接v0和最后加到路中的顶点，构成一条回路，它就是带权的哈密顿圈。 例4.2.3 图（a）是一带权无向完全图，用最邻近法求一条最短哈密顿回路。 解 算法步骤按图（b）、（c）、（d）、（e）、（f）的粗线边依次给出，图（f）即所求之带权哈密顿圈，权为47。 表面上看“最邻近算法”是很合理的，其实不然。例如图（a）的最短哈密顿回路应该是图（g）所示，它的权为35，这表明“最邻近算法”可能产生误差。 I have to put all these into…… * 第四章 Euler图和Hamilton图 欧拉是历史上最多产的数学家. 他生前发表的著作与论文有560 余种,死后留下了大量手稿.欧 拉自己说他未发表的论文足够 彼得堡科学院用上20 年,结果 是直到1862 年即他去世80 年 莱昂哈德·欧拉（Leonhard Euler ， 1707年4月5日～1783年9月18日） 后,彼得堡科学院院报上还在刊登欧拉的遗作.1911 年瑞士 自然科学协会开始出版欧拉全集,现已出版70 多卷,计划出 齐84 卷,都是大四开本.欧拉从18 岁开始创作,到76 岁逝 世,因此单是收进全集的这些文稿,欧拉平均每天就要写约 1.5 页大四开纸的东西,而欧拉还有不少手稿在1771 年的 彼得堡大火中化为灰烬.欧拉28 岁左眼失明,56 岁双目失 明,他完全是依靠惊人的记忆和心算能力进行研究与写作. §4.1 Euler图 欧拉图的概念是瑞士数学家欧拉（Euler）在研究哥尼斯堡（Knigsberg）七桥问题时形成的。在当时的哥尼斯堡城，有七座桥将普莱格尔（Pregel）河中的两个小岛与河岸连接起来，当时那里的居民热衷于一个难题：一个散步者从任何一处陆地出发，怎样才能走遍每座桥一次且仅一次，最后回到出发点？ 这个问题似乎不难，谁都想试着解决，但没有人成功。人们的失败使欧拉猜想：也许这样的解是不存在的，1936年他证明了自己的猜想。 为了证明这个问题无解，欧拉用A，B，C，D四个顶点代表陆地，用连接两个顶点的一条弧线代表相应的桥，从而得到一个由四个顶点、七条边组成的图，七桥问题便归结成：在所示的图中，从任何一点出发每条边走一次且仅走一次的通路是否存在。 §4.1.1 欧拉(无向)图 ?定义4.1.1 设G=〈V,E〉是连通图，经过G中每一条边一次且仅一次的通路（起点、终点不重合）称为欧拉通路（欧拉开迹），有欧拉通路的图称半欧拉图；经过每一条边一次且仅一次的回路称为欧拉回路（欧拉闭迹），有欧拉回路的图称欧拉图。一条欧拉通路即为一条行遍图中每条边的简单通路（迹），亦即一笔画问题。 定理4.1.1 设G是连通图，G是欧拉图当且仅当G的所有顶点均是偶度数点。 : 先证必要