我需要一个算法来找出在树上最大的独立设置。 我从所有叶节点的思维开始，然后删除直接父节点，这些叶子节点，然后选择我们删除了父节点的父节点，直到我们得到根递归地重复此过程。 而这O（n）的时间呢？ 任何回复理解。 谢谢。
而且任何人都可以请点我的算法来找出最大支配在树上设置。
Answer 1:
最大独立集
您可以计算最大的独立通过树的深度优先搜索设置。
搜索将计算两个值在图中的每个子树：
- A（1）=在扎根在我与约束我必须包括在所述一组节点的子树的最大独立集的大小。
- B（1）=在扎根在我用限制我不能被包括在该组节点的子树的最大独立集的大小。
这些可以通过递归考虑两种情况计算：
的子树的根不包括在内。
B（1）=总和（MAX（A（j）中，B（j）的），用于在儿童Ĵ（i））的
的子树的根是包括在内。
A（I）= 1 + SUM（B（j）的对于j儿童（i））的
在整个树中的最大的独立集的大小为max（A（根），B（根））。
极大支配集
按照维基百科支配集定义的最大支配集总是平凡等于包括图中的每个节点-但是这可能不是你的意思？
Answer 2:
为了找到最大独立顶点集，我们可以用一棵树的一个重要特性：每棵树是二分，即我们可以颜色的树只使用两种颜色，使得没有两个相邻的顶点具有相同颜色的顶点。
做一个DFS遍历并开始着色有黑色和白色的顶点。
挑顶点集（黑色或白色），其是在多数。 这会给你最大的独立设置的一棵树的顶点。
背后的为什么这个算法的工作中的直觉：
让我们先重温最大独立顶点集的定义。 我们必须选择一个边缘只有一个终点，我们必须覆盖满足这个属性树的每一个角落。 我们不允许选择一个边缘的两个端点。
现在是什么图形的bicoloring呢？ 它简单地将所述顶点组成两个子集（白色和黑色）和白色的顶点被直接连接到黑色的。 因此，如果我们选择要么全白或全黑的人，我们本来选择一个独立的组顶点。 因此，要选择最大独立集，去其尺寸较大的子集。
文章来源: algorithm to find max independent set in a tree
