np - 超哈密顿循环

Question

Ultra-Hamiltonian 自行车被定义为一种封闭的步行，它只访问每个顶点一次，除了最多一个顶点访问不止一次。

问题：- 证明确定给定图是否包含超哈密顿循环是 NP 难的。

我们可以从哈密顿循环问题中减少它，这是一个 NP 难题，但我没有从哪里开始将它减少到超哈密顿循环问题。

你能告诉我这样做的方法吗？

Answer 1

我们知道哈密顿路径问题已知是 NP 完全问题，现在为了证明超哈密顿循环是 NP 难的，我们将哈密顿路径问题简化为超哈密顿循环问题。证明：哈密顿路径≤P超哈密顿循环证明：对于由图G =（V，E）组成的哈密尔顿路径问题的每个实例作为输入，都可以转换为由图G' =组成的超哈密顿循环问题(V'，E')。我们将按以下方式构造图 G'： V' = 添加原始图 G 的顶点 V，并在蝴蝶形成中添加 5 个附加顶点 V0 V1 V2 V3 V4（解释如下），使得原始图 G 连接到顶点 V3 和 V4。这里在图 G' 的顶点数增加了 5，V' =V+5。E' = 添加原始图G的边E，在新添加的顶点V3和V4之间添加新边到图G的所有原始顶点。在G'中边数增加顶点数2V。这5个添加的顶点（V0 V1 V2 V3 V4）在以V0为关节点的蝶形图中，可以在多项式时间内得到新的图G'。约简的有效性可以通过以下两个主张来证明： i)（前向）让我们假设图 G 包含一条哈密顿路径，覆盖图的 V 个顶点，从一个随机顶点开始，比如 Vstart，到 Vend 结束，现在因为我们将所有顶点连接到 G' 中的两个新顶点 V3 和 V4。我们通过分别使用边 Vend 到 V3 和 V4 到 Vstart 将原始哈密顿路径扩展到超哈密顿循环。图 G' 现在包含遍历所有顶点的循环，除了 V0（蝴蝶图中的关节点）被多次访问，这个遍历从 V0 到 V1 到 V2 到 V0 到 V4 到 Vstart 到 G 中的“汉密尔顿路径” ” 到 V3 到 V0。（这里V0 V1 V2 V3 V4是蝴蝶图）。所以这是 G' 中的超哈密顿路径。. ii)(后向) 我们假设图 G' 有一个超哈密顿循环通过所有顶点，包括 V0 V1 V2 V3 V4，因为 V0 是一个关节点，所以它必须被访问不止一次，并且没有其他顶点被多次访问，图 G 的路径也可以在 V3 或 V4 进入蝴蝶图，并在 V3 或 V4 离开蝴蝶图（以不用于进入蝴蝶图的为准）。一旦路径离开蝴蝶图，它将访问路径中图 G 的每个顶点并返回到蝴蝶图（永远不会回到图 G 的顶点）。这条路径必须使用 V3 和 V4 中的一个用于退出，另一个用于从蝴蝶图进入图 G 的顶点（广告 V0 是关节点并且已经被多次访问，因此不能多次访问其他顶点）。现在要将其转换为哈密顿路径，我们删除循环中与顶点 V0 V1 V2 V3 V4 对应的所有边。生成的路径将覆盖图的顶点 V 并将它们恰好覆盖一次。所以在这里我们从 G' 中的超哈密顿循环得到 G 中的哈密顿路径因此我们可以说图 G' 包含超哈密顿循环当且仅当图 G 包含哈密顿路径。所以，超哈密顿循环问题的任何实例都可以简化为哈密顿路径问题的实例。因此，超哈密顿循环是 NP-Hard。