获取树的最小顶点覆盖的良好算法是什么？

Question

如何得到一棵树的最小顶点覆盖的好算法？

输入：

节点的邻居。

输出：

最小顶点数。

- John Retallack

---

听起来像是在为考试复习，但找不到讲义笔记了。 - Tamas Czinege

只为让伟大而强大的Welbog感到困惑，+1。 - GEOCHET

Answer 1

阅读了这里的答案后，我并没有完全理解，所以我想从这里发布一个帖子。

总体思路是将树以任意节点为根，然后询问该根节点是否在覆盖集中。如果是，则通过递归计算其子树的最小顶点覆盖。如果不是，则必须在根节点的每个子节点上放置顶点，以覆盖根节点和其子节点之间的每条边。在这种情况下，需要对根节点的孙子进行递归。

例如，如果您有以下树：

    A
   / \
  B   C
 / \ / \
D  E F  G

注意，通过检查，您知道最小顶点覆盖是{B, C}。我们将找到这个最小覆盖。

我们从A开始。

A在覆盖范围内

我们移至B和C的两个子树，并对此算法进行递归。我们不能简单地说B和C不在覆盖范围内，因为即使AB和AC已被覆盖，我们也无法确定是否需要将B和C包含在覆盖范围内。

(考虑以下树，其中根和其中一个子节点都在最小覆盖范围内({A, D})

)

  A
 /|\___
B C    D
      /|\
     E F G

A不在覆盖集合中

但我们知道AB和AC必须被覆盖，所以我们必须将B和C添加到覆盖集合中。由于B和C已经在覆盖集合中，所以我们可以递归它们的子节点，而不是递归B和C（即使我们这样做，它也不会给我们更多信息）。

"正式"

令C(x)为以x为根的最小覆盖集合的大小。

那么，

C(x) = min ( 
            1 + sum ( C(i) for i in x's children ),                    // root in cover
            len(x's children) + sum( C(i) for i in x's grandchildren)  // root not in cover
            )

- Achal Dave

Answer 2

T(V,E)是一棵树，这意味着对于任何叶子节点，任何最小的顶点覆盖都必须包括叶子节点或与叶子节点相邻的顶点。这给我们提供了找到S（顶点覆盖）的以下算法：

1. 找到树的所有叶子节点（BFS或DFS），在树中需要O（| V |）。

2. 如果(u,v)是这样一条边，使得v是叶子节点，那么将u添加到顶点覆盖中，并修剪（u,v）。这将留下一个森林T_1（V_1，E_1），...，T_n（U_n，V_n）。

3. 现在，如果V_i = {v}，即| V_i | = 1，则该树可以被放弃，因为所有与v相连的边都被覆盖。这意味着我们具有递归的终止条件，其中我们具有一个或没有顶点，我们可以计算每个T_i的S_i作为覆盖，定义S为步骤2中的所有顶点和每个T_i的覆盖集合的并集。

现在，我们只需要验证如果原始树仅具有一个顶点，则返回1并且从不开始递归，即可计算出最小的顶点覆盖。

编辑：实际上，在思考了一会儿后，这可以用一个简单的DFS变体来完成。

- user44242

---

有人真的关心这个答案吗？我认为这个答案比标记的答案简单得多，更好。 - Jackson Tale

Answer 3

我希望你能在这里你可以找到更多相关的问题答案。

---

我考虑了我的解决方案，可能需要修改，但只要动态规划是其中一个标签，您可能需要:

1. 对于每个u顶点，定义S+(u)为 使用顶点u的覆盖大小和S-(u) 不使用顶点u的覆盖大小。
2. S+(u)= 1 + Sum(S-(v))，其中v是u的子节点。
3. S-(u)=Sum(max{S-(v),S+(v)})，其中v是u的子节点。
4. 答案是max(S+(r), S-(r)),其中r是树的根节点。

---

阅读完这篇文章后。将上述算法更改为查找最大独立集，因为在维基百科文章中说明：

一个集合是独立的，当且仅当它的补集是顶点覆盖。

因此，通过将min更改为max，我们可以找到最大独立集，并通过补集找到最小的顶点覆盖，由于这两个问题是等价的。

- Artem Barger

---

这并没有太大帮助，我正在寻找伪代码或更详细的算法解释。 - John Retallack

不一定需要动态规划 - John Retallack

顺便提一下，树的递归结构无疑指向了回溯解决方案。 - Artem Barger

还有一个错误，仅将min更改为max是不够的，例如： (3)(4) | (3)(1) | | | (0)(1) (0)(1) (0)(1) 示例的格式为(S-v)(S+v)，max(S+(r), S-(r))（其中r是根）为4，这显然是错误的。 - John Retallack

它没有正确格式化示例，根节点（3,4）有一个子节点（3,1），其有3个子节点（0,1）（0,1）（0,1）。 - John Retallack

Answer 4

{- Haskell implementation of Artem's algorithm -}

data Tree = Branch [Tree]
    deriving Show

{- first int is the min cover; second int is the min cover that includes the root -}
minVC :: Tree -> (Int, Int)
minVC (Branch subtrees) = let
    costs = map minVC subtrees
    minWithRoot = 1 + sum (map fst costs) in
    (min minWithRoot (sum (map snd costs)), minWithRoot)

- Dave

Answer 5

我们需要为每个节点找到最小点覆盖。我们有两个选择，要么将其包括在内，要么不包括它。但是根据问题，对于每条边 (u,v)，'u' 或 'v' 中的任意一个都应该在点覆盖中，因此如果当前顶点未被包含，则我们需要包括其子节点；如果我们包括当前顶点，则可能根据最优解决方案决定是否包括其子节点。

这里，DP1[v] 表示任意顶点 v 包括时的情况，DP2[v] 表示任意顶点 v 不包括时的情况。

DP1[v] = 1 + sum(min(DP2[c], DP1[c]))，这意味着包括当前顶点并且可能包括其子节点，取决于什么是最优的。

DP2[v] = sum(DP1[c])，这意味着不包括当前顶点，则需要包括当前顶点的子节点。c 是顶点 v 的子节点。

然后，我们的解决方案就是 min(DP1[root], DP2[root])。

#include <bits/stdc++.h>
using namespace std;

vector<vector<int> > g;

int dp1[100010], dp2[100010];

void dfs(int curr, int p){
    for(auto it : g[curr]){
        if(it == p){
            continue;
        }
        dfs(it, curr);
        dp1[curr] += min(dp1[it], dp2[it]);
        dp2[curr] += dp1[it];
    }
    dp1[curr] += 1;
}

int main(){
    int n;
    cin >> n;
    g.resize(n+1);
    for(int i=0 ; i<n-1 ; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    cout << min(dp1[1], dp2[1]);
    return 0;
} 

- Aman

Answer 6

我们可以使用基于深度优先搜索的算法来解决这个问题：

DFS(node x)
{

    discovered[x] = true;

    /* Scan the Adjacency list for the node x*/
    while((y = getNextAdj() != NULL)
    {

        if(discovered[y] == false)
        {

            DFS(y);

           /* y is the child of node x*/
           /* If child is not selected as a vertex for minimum selected cover
            then select the parent */ 
           if(y->isSelected == false)
           {
               x->isSelected = true;
           }
        }
   }
}

叶子节点永远不会被选择为顶点覆盖。

- Sumit Trehan

Answer 7

我会简单地使用线性规划来解决最小顶点覆盖问题。 将其表述为整数线性规划的公式可以看起来像这个：ILP formulation

我认为你自己的实现不会比这些高度优化的LP求解器更快。

- Hannes