20

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

输入：

节点的邻居。

输出：

最小顶点数。

4

7 回答 7

15

看了这里的答案后我并没有完全理解，所以我想我会从这里发布一个

一般的想法是，您将树的根放在任意节点上，并询问该根是否在封面中。如果是，则通过递归计算以其子树为根的子树的最小顶点覆盖。如果不是，那么根的每个孩子都必须在顶点覆盖中，这样根和它的孩子之间的每条边都被覆盖。在这种情况下，您对根的孙子进行递归。

例如，如果您有以下树：

    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由于BandC在封面中，我们可以递归他们的孩子而不是递归Band 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
            )
于 2012-11-13T23:34:13.430 回答
11

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 相关的边都被覆盖了。这意味着我们有一个递归的终止条件，我们有一个或没有顶点，我们可以计算S_i作为每个T_i的覆盖，并将 S 定义为步骤 2 中的所有顶点联合每个T_i的覆盖。

现在，剩下的就是验证如果原始树只有一个顶点，我们返回 1 并且永远不会开始递归，并且可以计算最小顶点覆盖。

编辑：

其实想了想，用一个简单的DFS变种就可以完成。

于 2009-06-01T14:17:46.687 回答
10

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

我在考虑我的解决方案，可能您需要完善它，但只要动态编程在您的标签之一中，您可能需要：

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

看完这篇。更改了上述算法以找到最大独立集，因为在 wiki 文章中声明

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

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

于 2009-05-29T17:09:10.253 回答
2 
{- 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)
于 2009-05-30T17:17:13.443 回答
2

我们可以使用基于 DFS 的算法来解决这个问题：

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;
           }
        }
   }
}

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

于 2014-05-18T06:21:15.227 回答
2

我们需要为必须选择的每个节点找到最小的顶点覆盖，要么包含它，要么不包含它。但是根据每条边（u，v）的问题，'u'或'v'中的任何一个都应该在封面中，所以我们需要注意如果当前顶点不包括在内，那么我们应该包括它的孩子，并且如果我们包含当前顶点，那么我们可能会也可能不会根据最佳解决方案包含其子节点。

在这里，任何顶点 v 的 DP1[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;
}
于 2017-07-14T10:27:46.077 回答
0

我会简单地使用线性程序来解决最小顶点覆盖问题。作为整数线性程序的公式可能看起来像这里给出的公式：ILP公式

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

于 2014-05-17T10:56:27.023 回答