超哈密顿循环被定义为访问每个顶点一次的闭合行走，除了最多访问一个顶点一次以上。
问题：-证明确定一个给定的图是否包含超哈密顿循环是NP困难的。
我们可以将其从哈密顿循环问题中简化，这是一个NP难问题，但我不知道从哪里开始将其简化为超哈密顿循环问题。
你能告诉我做这件事的方法吗？
我们知道哈密顿路径问题是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中的哈密顿路径"到Vend到V3到V0。(此处V0 V1 V2 V3 V4为蝶形图(。这就是G'中的超哈密尔顿路径。。ii((反向(我们假设图G’有一个通过所有顶点的超哈密顿循环，包括V0 V1 V2V3 V4，因为V0是一个关节点，所以它必须被访问多次，并且没有其他顶点被访问超过同样，图形G的路径也可以在V3或V4处进入蝶形图，并在V3处离开蝶形图或V4(以不用于在蝶形图中输入的为准(。一旦路径离开蝶形图，它将访问每个图G在路径上的顶点，并返回到蝶形图(永远不要返回到图G的顶点(。此路径必须使用V3和V4中的一个退出，另一个从蝶形图进入图G的顶点(Ad V0是关节点，并且已经被多次访问，所以没有其他顶点可以被多次访问(。现在，为了将其转换为哈密顿路径，我们移除循环中与顶点V0 V1 V2 V3 V4对应的所有边。生成的路径将覆盖图的顶点V，并且将恰好覆盖它们一次。我们从G中的超哈密顿循环得到G中的哈密顿路径因此，我们可以说图G’包含超哈密尔顿环当且仅当图G包含哈密尔顿环路径因此，超哈密顿循环问题的任何实例都可以简化为哈密顿路径的实例问题因此，超哈密顿循环是NP难的。