一棵树的最小顶点覆盖数

Question

至少有三种算法可以在线性（O（n））时间中找到树中的最小顶点覆盖。我感兴趣的是对所有这些算法的修改，因此我还将获得这些最小顶点覆盖的数量。

例如，对于树P4（具有4个节点的路径），MVC的数量为3，因为我们可以选择以下节点：1和3、2和4或2和3。

当然，您可以描述任何一种免费算法的解决方案-并不是全部3.我只是对所有这些算法感兴趣，但是如果您有任何要添加的内容，请不要犹豫。

我将描述使您更轻松地知道的算法。

1.贪婪算法。

我们可以注意到，对于每个边缘，我们都必须包含一个节点。选择哪一个？假设我们有一个带有“正常”节点和叶子的边。哪个节点更好选择？当然不是叶子，因为另一个节点可能会帮助我们进一步提高优势。算法如下：

1. 从不是叶的任何节点开始。
2. 对于每个子对象，请进行DFS调用，并在返回时检查是否将父对象或子对象标记为顶点覆盖中的节点。如果不是，则必须选择其中之一，然后选择父项（并标记）。
3. 一片叶子什么都不做。

这是代码：https : //ideone.com/mV4bqg。

#include<stdio.h>
#include<vector>
using namespace std;

vector<int> graph[100019];
int mvc[100019];

int mvc_tree(int v)
{
    mvc[v] = -1;
    if(graph[v].size() == 1)
        return 0;
    int x = 0;
    for(int i = 0; i < graph[v].size(); ++i)
        if(!mvc[graph[v][i]])
        {
            x += mvc_tree(graph[v][i]);
            if(mvc[v] < 1 && mvc[graph[v][i]] < 1)
                ++x,
                mvc[v] = 1;
        }
    return x;
}

int main()
{
    int t, n, a, b, i;

    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(i = 1; i <= n; ++i)
            graph[i].clear();
        for(i = 1; i < n; ++i)
        {
            scanf("%d%d", &a, &b);
            graph[a].push_back(b);
            graph[b].push_back(a);
            mvc[i] = 0;
        }
        mvc[n] = 0;
        if(n < 3)
        {
            puts("1");
            continue;
        }
        for(i = 1; i <= n; ++i)
            if(graph[i].size() > 1)
                break;
        printf("%d\n", mvc_tree(i));
    }
    return 0;
}

2.动态编程算法。

我们还可以使用递归来解决任务。

MVC(v) = min(
              1 + sum(MVC(child) for child in v.children),
              v.children.size + sum(MVC(grandchild) for grandchild in v.grandchildren)
            )

当我们在节点v时，它可以在MVC中，也可以不在MVC中。如果是的话，我们将其添加到结果1中（因为我们包括了v），并且将其添加到所有v子级的子树的子结果中。另一方面，如果它不在MVC中，则他的所有子代都必须在MVC中，因此我们将子代数添加到结果中，并为每个子代添加子代子结果（即v的孙子代）。该算法是线性的，因为我们检查每个节点2次-为其父级和祖父母级。

3.动态编程2。

代替节点v的2个状态（在MVC中为1-，在MVC中为2-不在状态），我们可以使3添加“也许在MVC中”。有什么帮助？首先，我们称MVC（v =随机节点，“也许”），因为我们不知道v是否应该在MVC中。“可能”的结果是“是”和“否”的结果的最小值。“是”的结果是1 + sum（v.children中的child的MVC（child，“ maybe”））。而“否”的结果为sum（v.children中的child的MVC（child，“ yes”））。我认为原因很清楚。如果没有，请在评论中提问。因此，公式为：

MVC(v, "maybe") = min(MVC(v, "yes"), MVC(v, "no"))
MVC(v, "yes") = 1 + sum(MVC(child, "maybe") for child in v.children)
MVC(v, "no") = sum(MVC(child, "yes") for child in v.children)

复杂度也是O（n），因为每个节点都要检查两次-“是”和“否”。

Answer 1

动态规划解决方案

该解决方案扩展了您的第三种算法“动态规划 2 号”：我们递归地定义了六个函数

cover_maybe(v) := min(cover_no(v), cover_yes(v))
cover_no   (v) := sum(cover_yes  (child) for child in v.children)
cover_yes  (v) := sum(cover_maybe(child) for child in v.children) + 1

count_maybe(v) :=
  count_no (v)                  if cover_no(v) < cover_yes(v) 
  count_yes(v)                  if cover_no(v) > cover_yes(v) 
  count_no (v) + count_yes(v)   if cover_no(v) == cover(yes)

count_no   (v) := product(count_yes  (child) for child in v.children)
count_yes  (v) := product(count_maybe(child) for child in v.children)

前三个函数 cover_maybe、cover_no 和 cover_yes 精确对应于状态“maybe”、“no”和“yes”的 MVC 函数。他们计算需要包含在 v 下面的子树的顶点覆盖中的最小顶点数：

• cover_maybe(v) 确定 v 下面的子树的最小顶点覆盖。
• cover_no(v)：v 下面的子树的 MVC，条件是 v 不包含在此 cover 中。
• cover_yes(v)：v 下面的子树的 MVC，条件是 v 包含在此 cover 中。

说明：

• cover_maybe(v)：在任何顶点覆盖中，v要么包含在覆盖中，要么不包含在覆盖中。MVC 选择包含顶点数最少的解决方案：cover_no(v) 和 cover_yes(v) 中的最小值。
• cover_no(v)：如果 v 不包含在 cover 中，则所有子元素都必须包含在 cover 中（以便覆盖从 v 到子元素的边缘）。因此，我们需要在 cover_yes(child) 中为 v 的所有子节点添加包含的顶点。
• cover_yes(v)：因为 v 包含在 cover 中，所以它已经覆盖了从 v 到孩子的边缘 --- 我们不限制是否将孩子包含在 cover 中，因此为所有孩子添加 cover_maybe(child) v.

接下来的三个函数计算这些 MVC 问题的解决方案的数量：

• count_maybe(v) 计算 v 下面的子树的 MVC 解决方案的数量。
• count_no(v) 计算 MVC 解决方案的数量，条件是 v 不包含在覆盖范围内。
• count_yes(v) 计算 MVC 解决方案的数量，条件是 v 包含在封面中。

说明：

• count_maybe(v)：我们需要考虑三种不同的情况：如果 cover_no(v) 小于 cover_yes(v)，那么最好始终将 v 从 cover 中排除：count_maybe(v)=count_no(v)。类似地，如果 cover_yes(v) 小于 cover_no(v)，我们总是将 v 包含在 cover 中并设置 count_maybe(v)=count_yes(v)。但如果 count_no(v) 等于 count_yes(v)，那么我们可以在封面中包含或排除 v。可能性的数量是总和：count_maybe(v)=count_no(v)+count_yes(v)。
• count_no(v) 和 count_yes(v)：因为我们已经知道是否将节点 v 包含或排除在覆盖层中，所以我们为子节点留下了独立的子树。可能的解决方案的数量是每个子树的解决方案计数的乘积。正确子问题（count_yes 或 count_maybe）的选择如上所述（对于 cover_no(v) 和 cover_yes(v)）。

关于实施的两个注意事项：

• 与动态编程一样，您必须缓存每个函数的结果：第一次计算结果并将其存储在缓存中。当再次询问相同的查询时，将从缓存中读取结果而不是再次计算结果。通过这种缓存，该算法的运行时间为 O(n)，因为每个节点的六个函数中的每一个最多可以计算一次。
• 您必须从树的根开始计算（而不是像您在问题中建议的那样使用随机节点）：即使问题是用无向定义的——我们的“分而治之”算法也会选择一个根节点并安排节点的子节点根据其与根的距离。