算法找到'最大'独立设置在一个简单的图 [英] Algorithm to find 'maximal' independent set in a simple graph

问题描述

在的话，可以有人张贴方向，争取找到了'最大'独立设置在一个简单的图？

我读了一些东西ETH网站，说我们可以找到这样的O（N）通过简单地选择一个随机的顶点v比扫描休息，试图寻找是否有从v到其余的优势。

感谢

解决方案

是的，根据定义，最大indpendent组是其中没有更多的顶点可以在不违反独立条件下增加了一个独立设置的。

所以，刚刚好转的顶点，直到你可以挑不出更会给你一个极大独立集，可以在线性时间（| V | + | | E在如线性）完成

请注意，这是从的最大的独立集，这是一个独立设置的尽可能大的规模和发现，是一个NP难不同。

in words, can someone post directions towards finding the 'maximal' independent set in a simple graph?

I read up something from ETH site which said one can find such in O(n) by simply picking a random vertex v and than scanning the rest and attempting to find if there's an edge from v to the rest.

Thanks

解决方案

Yes, by definition, a maximal indpendent set is an independent set to which no more vertices can be added without violating the 'independence' condition.

So just picking vertices till you can pick no more would give you a maximal independent set, can be done in linear time (i.e. linear in |V| + |E|).

Note, this is different from maximum independent set, which is an independent set of the largest possible size and finding that is NP-Hard.

这篇关于算法找到'最大'独立设置在一个简单的图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！