大数据

当前位置:首页 > 大数据

《算法导论》第三十四章(续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],使得两条路径的并包含了附件图中的所有顶点。

《算法导论》第三十四章(续7)

除了附件图中的那些顶点外,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


相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~