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

最大独立集

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

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

1. A（i）=根于i的子树中最大独立集的大小，约束条件是必须将节点i包含在集合中。
2. B（i）=根于i的子树中最大独立集的大小，并且限制节点i不得包含在集合中。

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

1. 不包括子树的根。

B（i）= sum（max（A（j），B（j））for children（i）中的j）

1. 包含子树的根。

A（i）= 1 + sum（B（j）对于孩子中的j（i））

整个树中最大独立集的大小为max（A（root），B（root））。

最大化设定

根据Wikipedia中的支配集定义，最大支配集总是微不足道地等于包括图中的每个节点-
但这可能不是您的意思吗？