动机
哈密顿(Hamilton)路径恰好访问每个顶点一次。哈密顿圈则把这样的访问首尾相接成一个环。二者的定义很接近,但归约必须保持每一个“是”实例与“否”实例的答案,包括端点和边的方向。旅行商问题中也出现类似的问题:把图中缺失的边设为高代价可以编码哈密顿圈,但度量的三角不等式限制了这些边的代价可以取多大。
我们将证明若干显式的图变换,并由此推出判定问题与近似方面的后果。作为已声明的前置结论,我们使用至少有两个顶点的简单无环有向图上有向哈密顿圈问题的标准 NP 完全性。本章不从 SAT 出发证明该前置结论,但会证明由它推出的每一个变换,并给出目标判定问题的证书。
定义
定义 4.5.1
(哈密顿路径与哈密顿圈)
有向哈密顿圈是全体顶点的一个循环排列,其中每一对相邻的有序顶点(包括首尾闭合的那一对)都是有向边。有向哈密顿路径是访问每个顶点恰好一次且遵守边方向的顶点序列。在无向简单图中,相应的路径与圈使用无向边。对于无向圈,我们只考虑至少三个顶点的情形,并要求它是简单圈。
定义 4.5.2
(旅行商实例、巡回与度量成本)
这里的对称旅行商实例是 个顶点上的完全无向图,各边带有非负整数代价。巡回是一个哈密顿圈,其代价是各边代价之和。度量实例还要求对任意三个互异顶点都有 。判定版本询问是否存在代价不超过某个整数阈值的巡回。
定理 4.5.3
(路径与无向圈)
有向哈密顿圈可在多项式时间内归约到有向哈密顿路径,也可归约到无向哈密顿圈。下面的构造把“是”实例映到“是”实例,把“否”实例映到“否”实例。
定理 4.5.4
(代价为一和二的巡回)
个顶点上的无向哈密顿圈可归约到代价取值于 、阈值为 的度量旅行商判定问题。对任意固定的有理数 ,若对任意非负对称巡回代价存在多项式时间的 -近似算法,则无向哈密顿圈存在多项式时间算法。
两个定理的证明分别见下面各构造部分。
有向圈到有向路径
在有向图中选定一个顶点 。用新的起点 和新的终点 取代它。把每条原有边 改为 ,把每条边 改为 。保留其他顶点之间的所有边。不添加任何进入 的边,也不添加任何离开 的边。
证明
(拆分一个顶点不改变是否存在哈密顿圈)
若原图有哈密顿圈,则从 开始遍历该圈,把开头的 换成 ,把结尾处的闭合换成 ,便得到新图中的一条哈密顿路径。反之,新图中的任意哈密顿路径必以 开头,因为 没有入边;也必以 结尾,因为 没有出边。把两个端点合并为单个顶点 即闭合成原图中的有向哈密顿圈。其他顶点各被访问恰好一次,且每条被改向的边都对应一条原有边。
新图只增加一个顶点,被改向的边至多线性多条。该构造并不假定原图中的任意哈密顿路径都能闭合;它构造的是代表同一个原顶点两侧的两个端点。
概念视角结构
哈密顿圈是置换的单一循环
用后继映射 记录有向哈密顿圈, 把每个顶点送到紧随其后的顶点。这样 是顶点集上的双射,对每个 都有 为边,而且 只有一个穿过所有顶点的循环;反过来,满足这些条件的 就是哈密顿圈。去掉“只有一个循环”的条件,便得到覆盖所有顶点的若干不相交有向圈,这只是一个普通的二分图完美匹配问题。困难完全在于迫使它只有一个循环。
有向圈到无向圈
对每个有向顶点 ,创建三个无向顶点 ,以及内部边 和 。对每条有向边 ,添加一条无向边 。不添加其他边。
证明
(构件构造的正确性)
有向哈密顿圈给出无向哈密顿圈:把每个构件从入顶点经中间顶点走到出顶点,并取表示每次有向转移的那条边。反之,所构造无向图中的任意哈密顿圈必须在每个中间顶点处同时使用它的两条内部边,因为该顶点的度为二。因此它把每个构件作为连续的“入—中—出”路径走过,方向可以是正向或反向。
每条外部边都连接一个出顶点和一个入顶点。若某个构件被正向(由入顶点到出顶点)遍历,圈便从它的出顶点经外部边离开,并在下一个构件的入顶点进入,所以下一个构件也被正向遍历。同一论证说明反向遍历之后接着的也是反向遍历。因此所有构件的遍历方向一致,必要时把整个圈反转,便可假定全部都是正向。
此时所用的每条外部边都形如 ,对应原图的有向边 。收缩各构件便得到有向哈密顿圈。构件共含 个顶点和 条边,因此该变换是多项式的。有向环已被排除;反平行的有向边会产生连接不同构件端点的两条互异的无向外部边。
证明透视
度数为二与出入配对用在哪里
这个证明有两个互相独立的强制步骤。第一,中间顶点的度数为二,所以哈密顿圈必须使用它的两条内部边;这使每个构件成为连续的“入—中—出”路径,并防止圈从同一个端点进入又离开构件。第二,外部边只连接出顶点和入顶点,所以从某个构件的出顶点离开,下一次进入必然是在入顶点,遍历方向不可能在构件之间翻转。
两个步骤缺一不可。若去掉中间顶点,圈可以在同一个入顶点使用两条外部边,而这种走法没有对应的有向边。论证最后把圈上每条外部边读作有向边 ,便得到一个恰好经过每个原有顶点一次的有向圈。
两个目标问题都属于 NP:给定的顶点序列是否包含所需顶点、是否互异、相邻顶点之间是否有边,都可在多项式时间内检验。结合所声明的有向圈前置结论,这些归约证明了在上述约定下,有向哈密顿路径和无向哈密顿圈都是 NP 完全的。
从哈密顿圈到度量巡回
给定 的无向简单图 ,在同一顶点集上构造完全图。原有的边代价为一,非边代价为二。三角不等式成立:每个代价至多为二,而经过另一个不同中间顶点的路线含两条边,每条代价至少为一。
证明
(成本一和二保持答案不变)
若 有哈密顿圈,则该圈作为巡回的代价为 。反之,每个巡回恰有 条边,每条代价至少为一。代价至多为 的巡回只能使用代价为一的边,因此它是 的哈密顿圈。所以阈值 同时保持了两种答案。给定的巡回及其代价和可在多项式时间内检验,结合前述前置结论与归约,得到该度量判定问题是 NP 完全的。
即使输入图不连通,这些代价仍是度量的。此时完全巡回实例依然存在;高代价的边连接原图中不相邻的顶点。这些边使巡回成为可能,但当不存在仅由原有边构成的圈时,它们会把巡回代价推高到 以上。
任意巡回代价下的间隔
证明
(常数倍近似算法会判定哈密顿圈)
固定有理常数 。这次给原有边赋代价一,给非边赋代价 。若存在哈密顿圈,则最优值恰为 。若不存在,则每个巡回都使用某条代价为 的边,其代价至少为 。
设有一个多项式时间算法,对这些非负实例总是返回代价至多为最优值 倍的巡回。运行它,并把返回的整数代价与 比较。在“是”实例中,输出代价至多为 ;在“否”实例中,每个可行输出的代价都大于 。这就在多项式时间内判定了无向哈密顿圈。对固定的有理数 ,整数 的编码长度是多项式的,且图是完全图,因此该变换是多项式的。
反例模式
间隔构造并不是度量实例
声称:以大成本 构造的实例是度量的,所以这个间隔也能排除度量巡回的常数倍近似。在路径 上取 来验证。此时 ,故 ,而 。但 ,三角不等式不成立。只要两个不相邻的顶点有共同邻点,对每个 都会出现同样的失败。因此间隔论证只适用于任意非负成本;成本一和二的实例是度量的,但它的“否”实例巡回成本只保证至少为 。
结论是有条件的:除非 ,否则对任意对称非负巡回代价,不存在多项式时间的固定常数近似算法。这与度量巡回的正面近似保证并不矛盾,后者的抄近路证明用到了三角不等式。
例题详解
例题 4.5.5
(拆分有向圈)
对有向圈 ,把 拆分为 。新边包括 、 和 ,给出哈密顿路径 。把它的两个端点合并回 ,便恢复原来的圈。
例题 4.5.6
(两个顶点的有向圈)
设顶点 之间同时有有向边 和 ,则无向构件构造给出六元圈 。方向相反的两条有向边变成两条不同的外部边,所构造的无向图仍是简单图。
例题 4.5.7
(路径图上的度量代价)
设输入图为三个顶点的路径 。其完全代价图给 赋代价一,给 赋代价二。唯一的无向巡回代价为四,大于阈值三,这与路径图没有哈密顿圈相符。三角不等式在 上经由 取等号。
例题 4.5.8
(“是”实例的间隔)
对四个顶点的四元圈,代价为一的圈总代价为四。在取大 的构造中取 ,则 ,满足所述因子的算法在这个“是”实例上必须返回代价至多为八的巡回。在同样规模的“否”实例中,每个巡回的代价至少为十二。
常见错误
常见错误
(把归约的方向读反)
归约的方向很重要。从问题 到问题 的多项式归约,把 的求解器变成 的求解器;它本身并不能把 的求解器变成 的求解器。上面每个证明都给出了两个方向的见证变换,使“是/否”等价性是显式的。
常见错误
(没有严格区分两种情形的阈值)
判定阈值必须严格区分两种情形。对于度量构造,每个巡回有 条边且代价至少为 ,所以阈值 恰好成立。对于近似间隔,仅仅选一个很大的数而不与 比较是不够的。所选的 使“否”实例的下界严格大于“是”实例允许的最大输出。
常见错误
(把闭合顶点算作两次)
圈的证书按循环顺序列出顶点,并可对照相应的边或代价表示进行检验。它不需要把起点作为另一个顶点再列一次;回到第一个顶点的最后一条边单独检验。这样可避免把重复书写的闭合记号误当作访问了某个顶点两次。
归约的适用范围
无向构件的证明依赖于中间顶点恰有两条关联边这一事实。哈密顿圈必须使用这两条边,这就排除了从同一端点进入并离开构件的可能。外部边的模式随后使整个巡回上各构件的方向同步。若只是为每个有向顶点画三个顶点,而不证明这两个事实,就无法排除虚假的无向圈。
旁注
先用度数检验构件
信任一个构件之前,先列出哈密顿圈在构件每个顶点上被迫采取的走法,从度数为二的顶点开始。固定了被迫使用的边之后,才去问剩下的选择在原图中代表什么。
度量归约只使用代价一和二,因此其二进制编码特别小。然而这并不能给出常数因子的困难间隔:“否”实例中的巡回代价可能只比 多一,比值 趋近于一。它证明的是精确判定的困难性。任意代价归约之所以能产生更大的间隔,恰恰是因为它允许不满足三角不等式的代价。
本章以有向哈密顿圈的 NP 完全性作为前置结论。这里的证明建立的是下游的归约和成员性证书,而不是从 SAT 出发的原始归约。配套单元中针对哈密顿路径的指数级子集动态规划仍是有效的精确算法;NP 完全性仅在通常的复杂度假设下排除多项式时间算法。
总结
把指定的有向顶点拆分为被强制的路径端点,或把每个有向顶点替换为三个顶点的无向构件。代价为一的原有边与代价为二的非边给出度量巡回判定问题的归约。更大的非度量间隔给出有条件的常数因子不可近似性结论,并明确指出三角不等式所带来的限制。
练习
快速检查
(在有向图到路径的变换中,为什么每条哈密顿路径必须以 开始、以 结束?)
留意哪些边进入 、哪些边离开 。
解答 · 答案
没有边进入 ,所以它不能出现在其他路径顶点之后;没有边离开 ,所以它不能出现在其他顶点之前。哈密顿路径包含这两个顶点。
快速检查
(为什么无向构件图中的任何哈密顿圈都必须包含 的两条关联边?)
数一数 有几个邻点。
解答 · 答案
中间顶点恰好只有这两个邻点,而圈在其每个顶点上使用两条不同的关联边。
快速检查
(对于没有哈密顿圈的五顶点图,在成本一/成本二的构造中,每个巡回的成本有什么下界?)
巡回恰有五条边。
解答 · 答案
每个巡回有五条边。原图没有哈密顿圈,所以这些边中至少一条成本为二,其余至少为一,故每个巡回的成本至少为六。精确的最优值可以更大。
快速检查
(对 、,在大间隔构造中计算 以及“否”实例的下界。)
用 ,并数一数巡回的其余边。
解答 · 答案
。“否”实例中的任何巡回都要用一条昂贵的边,以及另外两条成本至少为一的边,所以成本至少为 ,大于 。