动机
恰好访问每个顶点一次的路线,与恰好经过每条边一次的欧拉(Euler)路线是不同问题。哈密顿(Hamilton)圈没有类似度数奇偶性那样简单的完整判别法。但度数条件仍能保证其存在。我们证明两个这样的条件,并用反例防止把充分条件误认为必要条件。
定义
定义 4.1.1
(哈密顿路径与哈密顿圈)
本节 是有限简单无向图,。哈密顿路径恰好访问每个顶点一次。对 ,哈密顿圈是包含每个顶点的圈;写成闭合序列时只在末尾重复起点。含哈密顿圈的图称为哈密顿图。非空图的最小度记为 。
这样的度数界约束每个顶点,而不是平均度。简单图中顶点度数至多为 。下列定理排除 ;在本节的圈约定下,那些图没有哈密顿圈。
定理/命题
定理 4.1.2
(Ore 条件)
设图有 个顶点。若每对不同且不相邻的顶点 均满足 ,则图有哈密顿圈。
推论 4.1.3
(Dirac 条件)
设图有 个顶点。若 ,则图有哈密顿圈。
证明思路
证明
(边极大的反例与两条交叉边)
先用反证法证明 Ore 条件。假设存在反例。只要添加缺边后图仍非哈密顿,就一次添加一条。可能的边数有限,过程停在一个边极大的非哈密顿图 。它的度数不小于原图,故仍满足 Ore 条件。 不是完全图,因为至少三个顶点的完全图有哈密顿圈。选 中不相邻的 。
由极大性,加入 后出现哈密顿圈。此圈必用到新边,因为 本身没有哈密顿圈。删除新边,留下 中从 到 的哈密顿路径,记为
对 ,定义两个指标集
它们的大小分别是 和 ,因为路径恰好列出每个其他顶点一次。两集合大小之和至少为 ,可用指标却只有 个,因此必有交集。取交集中 :从 沿路径走到 ,经边 到 ,再沿路径反向走到 ,最后经边 回到起点。这在 中形成哈密顿圈,矛盾。指标集自动排除有问题的端点: 不属于 , 不属于 ,因为 不相邻。
证明透视
指标交集如何闭合路径
Ore 条件在两个不同地方被使用。首先,它必须在由 过渡到边极大图 时保持成立;由于加边从不降低度数,它确实保持,这正是“极大反例”论证得以成立的原因。其次,它只应用于一对顶点:加入其边后便完成哈密顿圈的那对不相邻顶点 。极大性提供了生成路径 ,单凭度数假设永远得不到这条路径。
关键的一步是 与 中错开一位的指标,使一个共同指标同时给出两条交叉边 与 ;计数 迫使这样的指标存在。 不相邻使 不属于 、 不属于 ,所以两条交叉边都确实是 的边。论证以与“ 不是哈密顿图”的假设矛盾而完成。
证明
(由 Ore 推出 Dirac)
Dirac 条件蕴含 Ore 条件:任意不同且不相邻的两顶点度数和至少为 。若图为完全图,结论显然;上述证明也涵盖该情况,因为此时 Ore 条件真空成立。阈值可以不是整数,但度数是整数;当 为奇数时, 等价于 。
例题详解
例题 4.1.4
(应用度数条件)
八顶点简单图最小度为 4。因为 ,Dirac 条件成立,所以存在哈密顿圈。定理证明存在,但没有直接指出该圈;寻找具体圈是另一个算法任务。
例题 4.1.5
(条件失败但圈存在)
六圈 按定义就是哈密顿图,最小度为 2。Dirac 条件要求最小度至少为 3,因此不能应用。充分条件失败不等于结论失败。
例题 4.1.6
(删除顶点的障碍)
两个三角形仅共享一个顶点时,没有哈密顿圈。删除共享顶点会使图不连通。如果存在哈密顿圈,删去该顶点后,圈上其余边构成一条经过所有剩余顶点的路径;因此删点后的图仍连通。矛盾证明圈不存在。
常见错误
常见错误
(在 Ore 条件中检查相邻顶点对)
Ore 条件针对不相邻的顶点对;不必检查相邻对。若不存在不相邻的顶点对,条件真空成立。
常见错误
(以平均度代替最小度)
平均度高不代表最小度高。团 加一个孤立顶点有 ,平均度为 ,却不可能有哈密顿圈;任何更大的团加一个孤立顶点也是如此。
常见错误
(推断 Dirac 定理的逆命题)
圈本身构成一族无限多个哈密顿图,最小度只有二;当 时小于 。充分度数条件也不会给出最短哈密顿圈,更不能直接解决加权旅行商问题。
总结
Ore 条件控制不相邻顶点对的度数和;更强的 Dirac 最小度条件蕴含它。证明先把极大反例转化为生成路径,再利用两个指标集的交集将路径闭合。充分假设失败时,结论仍未确定。
练习
快速检查
(九顶点简单图最小度为 。Dirac 定理说明什么?)
解答 · 答案
因为 ,图是哈密顿图;定理没有指出具体的圈。
快速检查
(七圈最小度为 。Dirac 假设失败是否意味着它没有哈密顿圈?)
解答 · 答案
不是。给出的七圈本身恰好访问每个顶点一次,是哈密顿圈。Dirac 定理不适用,但其逆命题不成立。
从删点得到必要条件
哈密顿圈给出一族有用的必要条件。
命题 4.1.7
(从哈密顿图中删除顶点)
设 非空。若 是哈密顿图,删除 及其关联边得到的图 至多有 个连通分支,孤立的剩余顶点也算分支。
证明
(把圈切成若干段)
从一个圈删除 个顶点至多留下 段路径,每个剩余顶点都属于其中一段,而 的额外边可以合并这些段,不能增加分支。若 ,剩余图有零个分支,不等式仍成立。
当 时,结论是删除任一顶点后图仍连通,所以哈密顿图没有割点。它的最小度也至少为二,因为圈上每个顶点有两个不同的圈邻点。这些都是必要条件,但单独使用甚至同时使用一般都不充分。要证明圈不存在,可以找出使 的分支数大于 的集合 ,或找一个度至多为一的顶点;找不到这类集合并不能证明存在哈密顿圈。
例题 4.1.8
( 没有哈密顿圈)
考虑完全二部图 。删除较小一侧的两个顶点,另一侧三个顶点成为孤立点,留下三个分支,多于删去的两个顶点,所以它没有哈密顿圈。也可用交替性证明:二部图中的圈在两侧之间交替,因此哈密顿圈必须使用两侧相同数量的顶点。两种证明都无需检验所有顶点排列。
即使二部图两侧大小相差一,仍可能有哈密顿路径。 中将较小一侧记为 ,另一侧记为 ,则 是哈密顿路径。它不能闭合成圈,因为两端在同一侧,不相邻。所以即使都经过所有顶点,路径和圈也必须区分。
最小度阈值的紧性
Dirac 阈值的大小不只是取整产生的假象。
反例模式
最小度比阈值少一
断言:对偶数 ,最小度 已足以保证哈密顿圈。对偶数 ,取两个大小为 的团,各选一个顶点,用单条边连接。每个顶点度数至少为 ,但连接边是桥。哈密顿圈不能包含桥,因为圈的其余边将给桥的端点提供另一条路径;而圈若经过两边的顶点,又必须使用唯一连接边。所以该图非哈密顿。最小的非平凡情形 是两个三角形 与 以边 相连:度数为 ,删除 就把 与 分开。阈值 不能降低一。
对奇数 ,取两个大小为 的团,使它们恰共享一个顶点,其余顶点互不相同。共享顶点是割点;删除后剩两个非空分支。每个非共享顶点的度数为 ,共享顶点度数为 ,故最小度为 。该图同样非哈密顿。这两族图说明,将整数阈值 降低一,不能对这些阶数的所有图保持定理结论。
桥不能在圈上是局部结论:圈上其余边给出绕过该边的路径。在偶数阶构造中,若圈要覆盖两个团,连通结构迫使它跨越两者之间的唯一边。两个步骤都不可缺少。
构造性解释及其局限
Ore 的证明可以反向阅读。加入缺边 后出现哈密顿圈,删去该边得到从 到 的生成路径。度数和条件保证存在指标 ,使重排路径所需的两条交叉边都存在,从而构造不使用 的圈。对具体路径可写出两个指标集并检查交集。但上述证明假设能够取得添加边后图中的哈密顿圈;就目前表述,它是存在性证明,本身没有给出快速找到该圈的方法。
例如生成路径为 ,且图中有 和 。取 ,得到圈 。两条交叉边代替了缺失的闭合边 ;返回 前六个顶点各出现一次。即便图整体不满足 Ore 条件,只要这些边存在,这种局部重排仍然有效;全局条件的作用是保证证明中的路径必有这样一个指标。
目前没有已知的高效一般算法:判定一个图是否为哈密顿图是 NP 完全问题。
自然的下一个问题
有没有快速的一般哈密顿性检验?
目前没有已知的高效一般算法:判定一个图是否为哈密顿图是 NP 完全问题。
Ore 条件和 Dirac 条件容易检查,但只适用于相当稠密的图。对一般的图,判定问题“ 有没有哈密顿圈?”是 NP 完全的;若它有多项式时间算法,NP 中每个问题都会有多项式时间算法。目前没有已知的这种算法。因此本节把充分条件与明确的障碍(例如删点检验)配合使用,而不是给出完整的刻画。
快速检查
(图中有度为一的顶点,它可能是哈密顿图吗?)
解答 · 答案
在 的圈约定下不能。哈密顿圈在每个顶点使用两条不同的关联边,但度为一的顶点只有一条。
快速检查
(证明两侧顶点数不相等的二部图没有哈密顿圈。)
解答 · 答案
每条边都跨越两侧,故圈必须在两侧之间交替。回到起点时圈使用两侧的顶点数相等。哈密顿圈包含所有顶点,因而两侧大小必须相等。
快速检查
(路径 所在图还含 和 。给出哈密顿圈。)
解答 · 答案
取 ,所需交叉边正是 、。圈为 ;中间几条边沿原路径反向走,两条额外边将其闭合。
比较两个度数检验
Dirac 条件只需检查一个数 ;即使某个顶点的度数较低,Ore 条件仍可能适用。例如从 中删除共享一个端点 的两条边。 的度为 2,小于 ,所以 Dirac 不适用。它的两个非邻点各有度 3,度数和为 。这些是仅有的不相邻顶点对,所以 Ore 条件成立,图是哈密顿图。可把 放在它的两个邻点之间,再沿剩余两个顶点连接成圈。
检验 Ore 条件需要检查不相邻顶点对及其度数和。若某一对违反不等式,定理只是没有给出结论,哈密顿圈仍可能存在。反之,若所有相关顶点对均满足条件,定理保证存在,但不计算不同圈的数目。应用时应说明图的阶数和所用度数,使读者能核查所有相关顶点对。