时间戳

首页 > 解决方案 > 多时无向加权图

algorithm - 多时无向加权图

问题描述

我正在参加生物信息学算法的硕士课程，我正在尝试解决一些练习以通过考试。我陷入了这个问题，我不明白我必须以哪种方式解决它。你能帮忙吗？感谢接下来的几行是练习：

争论你是否相信下面的问题有一个多项式时间算法输入：一个完全无向图 G，边上有非负权重，权重有界 W。 解：一条简单路径，在所有路径中具有最大可能顶点数以 G 为单位，重量 < W。

标签： algorithmgraphgraph-theory

解决方案

这是NP-Hard，因此没有已知的多项式解决方案。

从哈密顿路径问题1可以很容易地减少这个问题。

给定一个图G=(V, E)，创建：

G' = (V, E', w)
Where:
E' = VxV (all edges)
w(u,v) = 1    if (u,v) is in E
         2    otherwise

现在，当且仅当是 hamiltonian时，G'具有最大权重的有效解。|V|G

(->) 如果 'G' 是汉密尔顿式，则有一条路径v1->v2->...->vn。所有这些边的权重为 1，因此总权重G'为|V|-1，使其最大且有效。

(<-) 如果在G'with中有一条路径value<|V|，并且我们知道它是最大的 - 所以如果它通过所有顶点 - 它不能有边 with w(u,v)=2（否则它将超过最大权重）。那么，这条路径在 中是哈密顿路径G。

(1)哈密顿路径是经过图中所有顶点的简单路径。如果一个图有这样一条路径，我们称它为哈密顿图。哈密​​顿路径问题是找出一个图是否是哈密顿图。

推荐阅读