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

Question

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

INPUT:

节点的邻居.

OUTPUT:

最小顶点数.

Answer 1

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变体来完成.

Answer 2

我在阅读完这些答案后并不完全明白,所以我想我会从这里发一个

一般的想法是,您将树根植于任意节点,并询问该根是否在封面中.如果是,则通过递归计算以其子项为根的子树的最小顶点覆盖.如果不是,则根的每个子节点都必须位于顶点覆盖中,以便覆盖根节点及其子节点之间的每条边.在这种情况下,你递归根的孙子孙女.

例如,如果您有以下树:

    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
            )

Answer 3

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

我在考虑我的解决方案,可能你需要对它进行修改,但只要动态编程在你的一个标签中,你可能需要:

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,我们可以找到最大的独立集,并通过补充最小顶点覆盖,因为两个问题都是等价的.