换句话说，有人可以发布在简单图中找到“最大”独立集的指示吗？
我从 ETH 网站上读到了一些内容，其中说人们可以通过简单地选择一个随机顶点 v 并扫描其余顶点并尝试查找从 v 到其余顶点是否存在边来在 O(n) 中找到这样的内容。
Thanks
是的，根据定义，最大独立集是在不违反“独立”条件的情况下不能添加更多顶点的独立集。
因此，只需选择顶点直到您无法再选择为止，就会给您一个最大的独立集，可以在线性时间内完成（即 |V| + |E| 中的线性）。
注意，这与maximum独立集，这是一个尽可能大的独立集，并且发现它是NP-Hard。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
