algorithm - 在树中找到最大独立集的算法

Question

我需要一种算法来找到树中的最大独立集。我想从所有叶子节点开始，然后删除这些叶子节点的直接父节点，然后选择我们删除的父节点的父节点，递归地重复这个过程，直到我们到达根节点。这是在 O(n) 时间内完成的吗？任何答复表示赞赏。谢谢。

谁能给我一个算法来找到树中的最大支配集。

Answer 1

最大独立集

您可以通过深度优先搜索树来计算最大独立集。

搜索将为图中的每个子树计算两个值：

1. A(i) = 以 i 为根的子树中最大独立集的大小，约束条件是节点 i 必须包含在集合中。
2. B(i) = 以 i 为根的子树中最大独立集的大小，限制为节点 i 不得包含在集合中。

这些可以通过考虑两种情况递归计算：

1. 不包括子树的根。

   B(i) = sum(max(A(j),B(j)) for j in children(i))

2. 包括子树的根。

   A(i) = 1 + sum(B(j) for j in children(i))

整棵树中最大独立集的大小为max(A(root),B(root))。

最大支配集

根据维基百科中支配集的定义，最大支配集总是微不足道地等于包括图中的每个节点——但这可能不是你的意思？

Answer 2

简单快速的方法：

只要图不为空，就迭代地将一个叶子 v（度数为 1）添加到独立集 V 中，并删除 v 及其邻居。

这应该有效，因为

• 一棵树总是有一个度为 1 的顶点，

• 向 V 添加一个度数为 1 的顶点可以保持最优性，并且

• 这一步骤的结果再次给出了一棵树或一片森林，它是树木的联合体。

Answer 3

• 为了找到最大的独立顶点集，我们可以使用树的一个重要属性：每棵树都是二分树，即我们可以只使用两种颜色为树的顶点着色，这样没有两个相邻的顶点具有相同的颜色。

• 进行 DFS 遍历并开始用黑色和白色为顶点着色。

• 选择数量更多的一组顶点（黑色或白色）。这将为您提供树的最大独立顶点集。

为什么这个算法有效背后的一些直觉：

• 让我们首先重新审视最大独立顶点集的定义。我们必须只选择一条边的一个端点，并且我们必须覆盖满足这个属性的树的每一条边。我们不允许选择边的两个端点。

• 现在图的双色有什么作用？它只是将一组顶点分成两个子集（WHITE 和 BLACK），而 WHITE 彩色顶点直接连接到 BLACK 顶点。因此，如果我们选择全白或全黑，我们本质上是在选择一组独立的顶点。因此要选择最大独立集，请选择大小较大的子集。