2

我认为哈密顿循环问题可以概括为：

给定一个无向图G = (V, E)，哈密顿回路是一次G遍历每个顶点的G一次且仅一次。

现在，我想做的就是减少我的问题。我的问题是：

给定一个加权无向图G、整数k和 中的顶点u, v ，G是否有一条G从u到的简单路径v ，总权重至少为k？

所以知道哈密顿循环问题是NP完全的，通过将这个问题简化为哈密顿，这个问题也被证明是NP完全的。我的问题是将其简化为哈密顿量的功能。

  1. 最大的问题是哈密顿问题不处理边权重，所以我必须将我的图转换为没有任何权重的图。
  2. 最重要的是，这个问题有一个指定的开始和结束（u 和 v），而哈密顿量找到一个循环，所以任何开始都与结束相同。

对于（1），我正在考虑通过一个图表，其中所有总权重小于 k 的简单路径都被取出。对于（2），我认为这不是一个真正的问题，因为如果存在哈密顿循环，那么从 u 到 v 的简单路径可以从中切出。

所以，我真正的问题是：

  1. 我的解决方案会给我正确的答案吗？
  2. 如果是，那么我怎样才能取出将产生总重量小于 k 的简单路径的边缘而不影响实际解决方案可能需要这些边缘之一的可能性？因为如果一条边 e 被取出是因为它为 E 的一个子集产生了一个权重 < k 的简单路径，它仍然可以用于具有不同边组合的简单路径以产生一个权重 >= k 的路径。

谢谢！

4

3 回答 3

6

你的减少方向是错误的。为了证明您的问题是 NP 完全的，您需要将 Hamilton Circuit 简化为它，这很容易。即表明每个汉密尔顿电路问题都可以用你的问题变体来表达。

于 2011-12-03T22:33:34.147 回答
4

更多的是提示而不是答案：

未加权图可以解释为每条边都有权重的加权图1。在这样的图中，哈密顿循环的成本是多少？

于 2011-12-03T22:38:13.803 回答
2

关于循环和路径之间不匹配的部分是正确的，是您需要解决的问题。基本上你需要证明哈密顿路径问题也是NP完全的（循环问题的相对简单的减少）

至于另一部分，你做错了方向。您需要证明您的更复杂的问题可以解决哈密顿路径问题（因此是 NP-hard）。为此，您基本上必须使用单位成本边缘的特殊情况。

于 2011-12-03T22:38:00.617 回答