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

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

最大支配集

根据definition of dominating set in wikipedia最大支配集总是简单地等于包括图中的每个节点 - 但这可能不是你的意思？