证明无向图的哈密顿回路问题多项式时间规约到有向图的哈密顿问题

首先，哈密顿回路问题是指在一个无向图中是否存在一个简单回路，使得该回路经过图中的每个点恰好一次。而哈密顿问题则是指在一个有向图中是否存在一个简单路径，使得该路径经过图中的每个点恰好一次。

我们需要证明的是，无向图的哈密顿回路问题可以在多项式时间内规约到有向图的哈密顿问题。也就是说，我们可以将任意一个无向图的哈密顿回路问题转化为一个有向图的哈密顿问题，并且这个转化过程可以在多项式时间内完成。

具体的转化方法如下：

1. 对于给定的无向图G=(V, E)，构造一个有向图G'=(V', E')，其中V' = V，E' 包含两部分边：

- 对于无向图G中的每条边(u, v)，在G'中添加两条有向边(u, v)和(v, u)。
- 对于无向图G中的每个节点v，在G'中添加一个与v相同的节点v'，并且对于每个与v相邻的节点u，在G'中添加一条有向边(v, u')和一条有向边(u', v)。

2. 现在我们需要证明，如果无向图G存在哈密顿回路，则有向图G'存在哈密顿路径；反之亦然。

- 如果无向图G存在哈密顿回路，那么这个回路必然经过每个节点。在有向图G'中，我们可以通过沿着每个节点的对应节点v'，然后依次沿着它们对应的边(u', v)和(v, u)走过每个节点，从而构造出一条哈密顿路径。
- 反之，如果有向图G'存在哈密顿路径，那么这个路径必然经过每个节点的对应节点v'。如果这个路径依次经过了每个节点的对应节点v'，然后依次沿着它们对应的边(u', v)和(v, u)走过每个节点，那么我们就得到了一个简单回路，它经过了图G中的每个节点，因此G存在哈密顿回路。

由此可见，无向图的哈密顿回路问题可以在多项式时间内规约到有向图的哈密顿问题，证毕。