顶点子集

Question

我有一个家庭作业问题,我不知道如何解决它.如果你能给我一个想法,我将非常感激.

这就是问题:"给定一个连通的无向图,它有N个顶点和N个边.每个顶点都有成本.你必须找到一个顶点子集,这样子集中顶点的总成本才是最小的,每个边缘都与子集中的至少一个顶点一起入射."

先感谢您!

PS:我已经解决了很长一段时间的解决方案,我想出的唯一想法是回溯或二分图中的最低成本匹配,但这两个想法对于N = 100000都太慢了.

Answer 1

由于边的数量严格要求顶点数量相同，因此它不是常见的顶点覆盖问题，而是NP完全问题。我认为这里有一个多项式解：

1. N 个顶点和 (N-1) 条边的图是一棵树。你的图有 N 个顶点和 N 个边。首先找到导致循环的糟糕边缘并将图变成树。您可以使用 DFS 来查找循环 ( O(N))。删除循环中的任何一条边都可以生成一棵树。在极端条件下，你会得到 N 可能的树（原始图是一个圆圈）。

2. O(N)对每个可能的树 ( )应用简单的动态规划算法 ( O(N^2))，然后找到成本最小的一棵。