哈密顿圈问题是NP完全的

【哈密顿圈问题】
对于一个有向图G=(V,E),如果G中的圈C恰好经过每一个顶点一次，则称圈C是一个哈密顿圈。即，哈密顿圈构成一条经过所有的顶点，没有重复的“路线”。如图6是一个含有哈密顿圈的图。

图6 一个含有哈密顿圈的有向图

证明哈密顿圈问题是NPC的，可以通过证明3-SAT$\leq_p$≤p​哈密顿圈来得到。
【3-SAT$\leq_p$≤p​哈密顿圈】
构造方法如下:
(1)对于每一个变量$x_i$xi​,创建3m+3个顶点。命名为$v_{i,1},...,v_{i,3m+3}$vi,1​,...,vi,3m+3​，并且对相邻的顶点，添加边($v_{i,j},v_{i,j+1}$vi,j​,vi,j+1​)和($v_{i,j+1},v_{i,j}$vi,j+1​,vi,j​)。如图中7中红色的点和绿色的边。如果$x_i$xi​为1，则路径$P_i$Pi​从左到右。反之，如果$x_i$xi​为0，则路径$P_i$Pi​从右到左。
（2）对于每一个变量，添加边$(v_{i,1},v_{i+1,1})$(vi,1​,vi+1,1​),$(v_{i,1},v_{i+1,3m+3})$(vi,1​,vi+1,3m+3​),$(v_{i,3m+3},v_{i+1,1})$(vi,3m+3​,vi+1,1​),$(v_{i,3m+3},v_{i+1,3m+3})$(vi,3m+3​,vi+1,3m+3​)。
（3）添加两个节点s,t。添加边$(s,v_{1,1})$(s,v1,1​),$(s,v_{1,3m+3})$(s,v1,3m+3​),$(v_{3m+3,1},t)$(v3m+3,1​,t),$(v_{3m+3,3m+3},t)$(v3m+3,3m+3​,t)。
（4）添加边$(t,s)$(t,s)。
构造后的图如图7所示。

图7 3-SAT到哈密顿圈的归约，第1部分
在图7中，可以看到有哈密顿回路：从t出发到达s，s再经过$P_{i}$Pi​，最后到达t，记为A。
之后对子句进行约束。
（5）对于每个子句$C_a$Ca​，假设子句为$C_1=x_1 \vee \overline x_2 \vee x_3$C1​=x1​∨x2​∨x3​，则这个子句表示哈密顿圈首先由左到右通过$P_1$P1​，然后由右向左通过$P_2$P2​，最后由左向右通过$P_3$P3​。如图8所示，添加点和边。

图8 3-SAT到哈密顿圈的归约，第2部分
可以看到，图中有哈密顿圈当且仅当3-SAT实例有满足的赋值。
证明：假设3-SAT实例有满足的赋值，则给出的哈密顿圈中，如果在满足的赋值中$x_i$xi​为1，则由左到右通过$P_{i}$Pi​，反之由右到左通过$P_{i}$Pi​。对于每一个子句，因为其是被满足的，所以至少有一条路径是按照与该项相关的“正确”的方向通过的。从而添加的子句顶点在哈密顿圈中能够被通过。反之，假设图G中有一个哈密顿圈，则所有添加的子句顶点（图8添加的点）都会被通过。即所有的子句都被满足。
因此，可以得到3-SAT实例是可满足的当且仅当G有哈密顿圈。证明了3-SAT$\leq_p$≤p​哈密顿圈。因此哈密顿圈问题是NPC的。

,.♥,.,.♥,.,.♥,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥♥,.,.♥,.,.♥,.,.♥,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥
广告时间：
本宝宝开通了一个公众号，记录日常的深度学习和强化学习笔记。希望大家可以共同进步，嘻嘻嘻！求关注，爱你呦！