哈密顿回路问题是NP完全问题

简介：
哈密顿回路问题是图论中的著名难题之一，寻找给定图中访问每个顶点恰好一次后再返回起点的路径。该问题是NP完全问题，意味着它属于复杂性类NP且与所有其他NP问题等价，即如果能高效解决此问题，则可以高效解决所有NP问题。 哈密顿圈问题是指在一个有向图G=(V,E)中，如果存在一个恰好经过每个顶点一次的圈C，则称该圈为哈密顿圈。换句话说，哈密顿圈是一条路径，它通过所有的顶点且没有重复访问任何节点。例如，在图6中的有向图就包含了一个这样的哈密顿圈。 证明哈密顿圈问题是NPC问题的一种方法是展示3-SAT可以多项式时间内归约到该问题上。具体构造如下： (1) 对于每一个变量 \(x_i\)，创建\(3m+3\)个顶点，并标记为 \(v_{i,1}, v_{i,2}, \ldots, v_{i,3m+3}\)，并且对于相邻的顶点之间添加边\((v_{i,j}, v_{i,j+1})\)。