在树中找到最大独立集的算法 [英] algorithm to find max independent set in a tree

问题描述

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

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

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

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:

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

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

These can be computed recursively by considering two cases:

1. 不包括子树的根.

1. The root of the subtree is not included.

B(i) = sum(max(A(j),B(j)) for j in children(i))

B(i) = sum(max(A(j),B(j)) for j in children(i))

包含子树的根.

A(i) = 1 + sum(B(j) for j in children(i))

A(i) = 1 + sum(B(j) for j in children(i))

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

The size of the maximum independent set in the whole tree is max(A(root),B(root)).

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

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?

这篇关于在树中找到最大独立集的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！