获得树的最小顶点覆盖的好算法是什么? [英] What is a good algorithm for getting the minimum vertex cover of a tree?

问题描述

获得树的最小顶点覆盖的好算法是什么?

What is a good algorithm for getting the minimum vertex cover of a tree?

节点的邻居.

最小顶点数.

推荐答案

我希望 no在这里您可以找到与您的问题相关的更多答案.

I hope here you can find more related answer to your question.

我正在考虑我的解决方案，您可能需要对其进行改进，但只要动态编程在您的标签之一中，您可能需要:

I was thinking about my solution, probably you will need to polish it but as long as dynamic programing is in one of your tags you probably need to:

1. 对于每个 u 顶点定义 S+(u) 是带有顶点 u 和 S-(u) 的覆盖大​​小覆盖没有顶点 u.
2. 对于 u 的每个孩子 v，S+(u)= 1 + Sum(S-(v)).
3. S-(u)=Sum(max{S-(v),S+(v)}) 对于 u 的每个孩子 v.
4. 答案是 max(S+(r), S-(r)) ，其中 r 是树的根.

<小时>

阅读这篇后.更改上述算法以找到最大独立集，因为在维基文章中说明

---

After reading this. Changed the above algorithm to find maximum independent set, since in wiki article stated

一个集合是独立的当且仅当它的补集是一个顶点覆盖.

A set is independent if and only if its complement is a vertex cover.

因此，通过将 min 更改为 max，我们可以找到最大独立集，并通过补充最小顶点覆盖，因为这两个问题是等价的.

So by changing min to max we can find the maximum independent set and by compliment the minimum vertex cover, since both problem are equivalent.

这篇关于获得树的最小顶点覆盖的好算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！