《算法导论》第三十四章（续7）

34.5.3哈密顿回路问题

现在，我们再回过头来讨论34.2节中定义的哈密顿回路问题。

定理34.13  哈密顿回路问题是NP完全问题。

证明  先来说明HAM-CYCLE属于NP。已知一个图G=(V，E)，我们选取的证书是形成哈密顿回路的|VI个顶点所组成的序列。验证算法检查到这一序列恰好包含v中每个顶点一次(但第一个顶点会在末尾重复出现一次)，并且它们在G中形成一个回路。也就是说，它要检查每一对连续顶点及首、尾顶点之间是否都存在着一条边。我们可以在多项式时间内验证这一证书。

现在，我们来证明VERTEX-COVER≤pHAM-CYCLE。从而证明HAM-CYCLE是NP完全的。给定一个无向图G=(V，E)和一个整数k，构造一个无向图G'=(V'，E')，使得它包含一个哈密顿回路，当且仅当G中有一个大小为k的顶点覆盖。

上述构造过程需应用到附件图(widget)，它是一个图的一部分，往往加上了某些特性。图34-16(a)中示出了我们用到的附件图。对于每条边(u， v)∈E，我们所构造的图G都将包含这一附件图的一份副本，用W...来表示。对W.中的每个顶点，用[u，v，i]或[v，u，i来表示，其中1≤i≤<6，因此，每个附件图W..包含12个顶点。如图34-16(a)所示，附件图W...还包含14条边。

除附件图的内部结构外，我们还通过限制附件图与构造出来的图G其余部分之间的连接，来强加一些有用的特性。特别地，只有顶点[_u，o，1]、[u， v，6]、[o， u，1]和[v，u，6]包含与外界相连的边。G中的任何哈密顿回路都必须以图34-16(b)～(d)中所示三种方法中的某一种来遍历W 中的边。如果回路由顶点[u，v，1]进人，则必定由顶点[u， v，6]退出。且它或者访问附件图中的12个顶点(图34-16(c))，或者访问从[u， v，1]到[u， v，6]的6个顶点(图34-16(c))。在后一种情况中，回路必须重新进入附件图以访问顶点[u，v，1]到[u， v，6]。类似地，如果回路是从顶点_u， v，1]进入的，则必须从顶点[u， v，6]退出，且它或者访问附件图中的所有12个顶点(图34-16(d))，或者访问从[v， u，1]到[v，u，6]的6个顶点(图34-16(c))。不存在上述以外的其他路径能访问附件图中所有12个顶点。特别地，不可能构造出两个“顶点不相交”路径，其中一条连接[_u， v，1]与[v， u，6]，另一条连接了[v，u，1]和[u， v，6]，使得两条路径的并包含了附件图中的所有顶点。

除了附件图中的那些顶点外，V'中唯一的其他顶点为选择器顶点(selector vertex)s，s2，",s。我们利用与G中选择器顶点关联的边来选择G中那些能实现k个顶点覆盖的顶点

除了附件图中的边之外，E中还有另外两类边，如图34-17所示。首先，对于每个顶点u∈v,都加入一些边来连接一对一对的附件图，从而形成一条路径，它包含了所有对应于G中与u关联的边的附件图。对于与每个顶点u∈V相邻的所有顶点，将其任意地排序为u”，u，…,u dewoefit)，其中degree(u)是与u相邻的顶点的数目。通过将边〈(Lu,u ,6],Lu, u+1),1]:1≤i≤degree(u)一1)}加入E中，即可在G中构造出一条穿越所有附件图的路径，这些附件图与那些关联于顶点u上的边相对应。例如，在图34-17中，我们将与w相邻的顶点排序为α，y，z，这样图34-17(b)中的图G'就包含了边([w， ，6]，[w，y，1])和([w，y，6]，[w，z，1])。对于每个顶点u∈V，G中的这些边形成了一条包含一系列附件图的路径，这些附件图都与G中关联于顶点u上的边对应。

这些边给我们的直觉就是，如果选择了G的顶点覆盖中的某一顶点u∈V，就可以在G中构造出一条从Lu，u”，1]到[u，u( desrelt)，6]的路径，它“覆盖”了所有与关联于顶点u的边对应的附件图。也就是说，对于这些附件图中的每一个(如Wa)，该路径或者包含所有的12个顶点(如果u在顶点覆盖中，但u不在顶点覆盖中)，或者只是6个顶点[u，u，1]，[u，u，2]，[u，u，3]，…，[u，u，6](如果u和u都在顶点覆盖中)。

E中的最后一类边将这些路径中的第一个顶点[u，u，1]及最后一个顶点[u，udegrekw)，6]与每一个选择器顶点连接起来。也就是说，包含了以下的边:

{(s;,Lu,u,1]):u∈v, 1≤j≤kU{(s;,Lu.udegrekt),6]):u eV, 1≤j≤k