多时间无向加权图
Undirected weighted graph in polytime
我正在参加生物信息学算法硕士课程，我正在尝试解决一些练习以通过考试。我陷入了这个问题，我不明白我必须以哪种方式解决它。你能帮忙吗？
感谢接下来的几行是练习：
Argue whether you believe that the following problem has a polynomial time algorithm
Input: A complete undirected graph G with non-negative weights on the edges, and a weight bound W.
Solution: A simple path with the maximum possible number of vertices among all paths in G of weight < W.
这是NP-Hard，因此没有已知的多项式解。
很容易从Hamiltonian Path problem1.
减少这个问题
给定一个图 G=(V, E)，创建：
G' = (V, E', w)
Where:
E' = VxV (all edges)
w(u,v) = 1 if (u,v) is in E
2 otherwise
现在，G' 有一个具有 |V| 最大权重的有效解，当且仅当 G 是哈密尔顿方程。
(->) 如果 'G' 是哈密顿分布，则存在路径 v1->v2->...->vn。所有这些边的权重都是 1，所以 G' 中的总权重是 |V|-1，使其最大且有效。
(<-) 如果 G' 中有一条路径 value<|V|，并且我们知道它是最大的 - 所以如果它经过所有顶点 - 它不能有边 w(u,v)=2（否则会超过最大权重）。然后，这条路径在 G.
中是哈密顿路径
(1) 哈密尔顿路径 是一条穿过图中所有顶点的简单路径。如果一个图有这样一条路径，我们称它为哈密尔顿图。 哈密顿路径问题 是判断一个图是否是哈密顿路径。
我正在参加生物信息学算法硕士课程，我正在尝试解决一些练习以通过考试。我陷入了这个问题，我不明白我必须以哪种方式解决它。你能帮忙吗？ 感谢接下来的几行是练习：
Argue whether you believe that the following problem has a polynomial time algorithm Input: A complete undirected graph G with non-negative weights on the edges, and a weight bound W. Solution: A simple path with the maximum possible number of vertices among all paths in G of weight < W.
这是NP-Hard，因此没有已知的多项式解。
很容易从Hamiltonian Path problem1.
减少这个问题给定一个图 G=(V, E)，创建：
G' = (V, E', w)
Where:
E' = VxV (all edges)
w(u,v) = 1 if (u,v) is in E
2 otherwise
现在，G' 有一个具有 |V| 最大权重的有效解，当且仅当 G 是哈密尔顿方程。
(->) 如果 'G' 是哈密顿分布，则存在路径 v1->v2->...->vn。所有这些边的权重都是 1，所以 G' 中的总权重是 |V|-1，使其最大且有效。
(<-) 如果 G' 中有一条路径 value<|V|，并且我们知道它是最大的 - 所以如果它经过所有顶点 - 它不能有边 w(u,v)=2（否则会超过最大权重）。然后，这条路径在 G.
(1) 哈密尔顿路径 是一条穿过图中所有顶点的简单路径。如果一个图有这样一条路径，我们称它为哈密尔顿图。 哈密顿路径问题 是判断一个图是否是哈密顿路径。