maximum_independent_set

maximum_independent_set(G)

返回一个近似最大独立集。

独立集或稳定集是图中的一个顶点集合，其中任意两个顶点都不相邻。也就是说，它是一个顶点集合 I，对于 I 中的任意两个顶点，它们之间没有边相连。等价地，图中的每条边在 I 中最多有一个端点。一个独立集的大小是它包含的顶点数 [1]。

最大独立集是给定图 G 中的一个最大独立集，其大小记为 \(lpha(G)\)。寻找这样一个集合的问题被称为最大独立集问题，是一个 NP 难优化问题。因此，不太可能存在一个有效的算法来找到一个图的最大独立集。

独立集算法基于 [2]。

Parameters:

GNetworkX 图

无向图

Returns:

iset集合

近似最大独立集

Raises:

NetworkXNotImplemented

如果图是有向的或是一个多重图。

Notes

在最坏情况下找到 \(O(|V|/(log|V|)^2)\) 的独立集近似。

References

[1]

Wikipedia: 独立集

[2]

Boppana, R., & Halldórsson, M. M. (1992). 通过排除子图来近似最大独立集。 BIT 数值数学, 32(2), 180–196. Springer.

Examples

>>> G = nx.path_graph(10)
>>> nx.approximation.maximum_independent_set(G)
{0, 2, 4, 6, 9}