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

Question

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

并且有人可以请指出一个算法来找到树中的最大支配集.

Answer 1

最大独立集

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

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

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

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

1. 子树的根不包括在内.

   B(i)=儿童j的总和(max(A(j),B(j))(i))

2. 包含子树的根.

   A(i)= 1 +总和(儿童(i)中j的B(j))

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

最大限定集

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