一种在树中查找最大独立集的算法

Question

我需要一种算法来在树中找到最大独立集。 我考虑从所有叶节点开始，然后删除这些叶节点的直接父节点，然后选择我们删除的父节点的父节点的父节点，以此递归重复此过程，直到到达根节点。这个算法的时间复杂度是O(n)吗？感谢您的任何回复。

还有谁能指点我一个在树中找到最大支配集的算法。

- starcaller

---

我没有理解你的问题，最大独立集是什么意思？你想要具有最大值的节点还是其他的？因为你所描述的方法将在二叉树中拥有2^n个叶子节点。那么，从哪里开始，简要描述一下树的实现方式，它是二叉树吗？ - Omkant

给定一棵包含n个节点的普通树，找出其最大独立集（http://en.wikipedia.org/wiki/Maximal_independent_set）。 - fgb

仅考虑完全二叉树以简化问题。 - starcaller

你想要一个最大独立集（尽可能大的独立集之一）还是一个极大独立集（不能再添加更多顶点的独立集）？最大独立集显然是极大的，但是找到不一定是最大的极大独立集更容易（所有树都是二分图，所以只需取二分图的一侧）。 - David Richerby

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))。

极大支配集

根据维基百科定义的支配集定义，最大支配集总是平凡地等于包含图中每个节点-但这可能不是您想要的？

- Peter de Rivaz

---

我认为最小支配集不等于最大独立集。星形图是一棵树，在那里它们显然不相等，或者我错过了什么？最小支配集不应该是最大独立集的补集吗？ - yassin

如果每个节点都有负权重，那么上述解决方案是否仍然正确？ - Loc Huynh

Answer 2

简单快速的方法：

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

这应该是有效的，因为：

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

• 将一个度为1的节点添加到V中可以保持最优性，

• 这样一步的结果再次给出一个树或森林，它是若干个树的并集。

- Wrdlbrmpfd

Answer 3

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

• 进行深度优先遍历，并开始用黑色和白色对顶点进行着色。

• 选择顶点集（黑色或白色），其中数量更多。这将为树提供最大独立顶点集。

一些关于为什么该算法有效的直觉：

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

• 现在，图的双色化有什么作用？它只是将顶点集划分为两个子集（白色和黑色），并且白色着色的顶点直接连接到黑色着色的顶点。因此，如果我们选择所有白色或所有黑色，则本质上选择了一个独立的顶点集。因此，为了选择最大独立集，请选择大小更大的子集。

- Sumit Trehan

---

这是不正确的。它找到了一个极大独立集（无法添加任何顶点的集合），但不是最大独立集（可能具有最大基数的集合之一）。考虑通过取边xy并在x和y相邻处添加两个叶子来形成的树。最大独立集是所有叶子：四个顶点。但是图的每一侧仅包含三个顶点。 - David Richerby

你能不能计算出最大的两种方式： 1）BLACK或WHITE列表的最大值 2）执行BLACK和WHITE着色，但每次到达叶节点时将其添加到叶节点的最大独立集中从（1）或（2）返回的最大列表是最终答案。 - Alex Spencer