算法找到最大独立集在树上树上、算法、独立、最大
我需要一个算法寻找一棵树最大独立设置。我从所有的叶子节点开始思考，然后删除直接父节点，这些叶节点，然后选择我们删除父节点的父节点，重复此过程递归，直到我们得到根。并在O（n）时间完成这件事？任何答复是AP preciated。谢谢。
I need an algorithm to find max independent set in a tree. I'm thinking start from all leaf nodes, and then delete the direct parent nodes to these leaf nodes, then choose the parent nodes of the parent nodes we deleted, repeat this procedure recursively until we get to root. and is this done in O(n) time? any reply is appreciated. thanks.
和任何人都可以请点我一个算法来找出最大支配在树上设置。
And could anyone please point me an algorithm to find the max dominating set in a tree.
推荐答案
您可以计算通过树的深度优先搜索的最大独立集。
MAXIMUM INDEPENDENT SET
You can compute the maximum independent set by a depth first search through the tree.
搜索将计算两个值在图中每个子树：
The search will compute two values for each subtree in the graph:
A（I）=在扎根在我与节点i必须包括在集合约束子树的最大信号独立设置的大小。 B（I）=在扎根在我的限制，即节点i必须不包含在该组的子树的最大独立集的大小。这些可以递归考虑2案件计算：
These can be computed recursively by considering two cases:
子树的根不包括在内。
The root of the subtree is not included.
B（I）= SUM（最大（A（J），B（J））对于j的儿童（一））
B(i) = sum(max(A(j),B(j)) for j in children(i))
子树的根被包括在内。
A（I）= 1 +总和（B（J）对于j的儿童（一））
A(i) = 1 + sum(B(j) for j in children(i))
在整个树的最大独立集的规模最大（A（根），B（根））。
The size of the maximum independent set in the whole tree is max(A(root),B(root)).
最小支配集等于最大独立集这样的算法相同的作品。
The minimal dominating sets are equal to the maximal independent sets so the same algorithm works.
据维基百科支配集的定义的最大支配集始终是平凡等于包括在每一个节点图？ - 不过这可能不是你的意思
According to the definition of dominating set in wikipedia the maximum dominating set is always trivially equal to including every node in the graph - but this is probably not what you mean?
