3.3Hamilton图解析.ppt

证明：由推论3.3.6知，只要证明 的闭包是完全图。 1. 假设 不是完全图，则可以取 使 最大。不妨设 则由 的假设， ＜ 。 接下来证明对这个k，不满足定理的条件 2. 记 对于 ，我们有 中每个点在 的度不超过 中每个点在 的度不超过 且 3. 由于 是 的生成子图，因而在 中有个点的度不超过 ,以及至少有 个顶点的度 小于 所以对 ＜ ,有 和 ＜ 矛盾，定理得证。 1983年，范更华给出的一个充分条件 图 是一个2-连通图，对图 中的任 意两个顶点 ，只要 就有 则 是Hamilton图。 证明 取 则可以证明 的每个连通分支是完全 图 ，且每个分支与 之间至少有两条边，同 时由闭包定理，我们不妨假设 是完全图。 由此可以构造出 的一个Hamilton回路。 * §3.3 Hamilton图 起源于1856年英Hamilton设计的名为周游世界的游戏。在一个实心的正十二面体的二十个顶点上标以世界各地有名的二十座城市的名字，要求游戏者沿十二面体的棱从一个城市出发，经过每座城市恰好一次再回到出发点。将十二面体投影到平面上：将十二面体的顶点与棱分别对应图的顶点和边，就得到一个正十二面体图。则问题等价于在正十二面体图中找一个回路，包含图中一切顶点——Hamilton回路。 返回 结束 定义3.3.1 中含所有顶点的回路称为 的 Hamilton回路（简记为H-回路）； 含有H—回路的图称为Hamilton图（简记为H-图）； 含所有顶点的路称为Hamilton路（简记为H-路）。 注：一个图可能既有H-回路，又有H-路。 从定义可知，一个图的Hamilton回路与Euler环游是很相似的，差 别在于Hamilton回路是环游G的所有顶点回路，而Euler环游是环 游G的所有边的闭迹。 返回 结束 对于一个图是否存在Euler环游存在一个非常简洁的判别法。 但是到目前为止还没有找到Hamilton图的充要条件。 找到Hamilton图的简明有效的充分条件是图论中一个著名的问题：Hamilton问题。 现在分别讨论图存在H-回路的充分条件与必要条件。一个图G 有H-回路当且仅当G的基础简单图有H-回路，所以下面只考虑 简单图。 一、必要条件 证：令 是 的H-回路， 则 。 而 是生成子图，故 。 定理3.3.1 若 是H-图， 则 。 不要考虑 本身，而要从 的一个特殊子图(H-回路)中去寻找解决方法。 一般用其逆否命题解题。 返回 结束 定理4.3.1 仅给出了Hamilton图的必要条件，而不是充分条件，如著名的Peterson图，尽管满足：对 的每个非空真子集S，均有 ，但Peterson图不是Hamilton图。 推广到H-路上： 若 有H-路，则 。 证：令 是 的H-路，则 。 而 是生成子图，故 。 例 不是H-图。 因为 使得 返回 结束 二、充分条件 1. Dirac(1952) 是简单图且 ，若 ，则