哈密​​顿循环的约简算法

Question

我认为汉密尔顿循环问题可归纳如下:

给定一个无向图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的路径.

谢谢!

Answer 1

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