maximum_independent_set#

maximum_independent_set(G)[source]#

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

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

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

独立集算法基于 [2]。

参数:

GNetworkX 图: 无向图

返回:

iset集合: 近似最大独立集

抛出:

NetworkXNotImplemented: 如果图是有向图或多重图。

注释

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

参考文献

[1]

维基百科: 独立集

[2]

Boppana, R., & Halldórsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2), 180–196. Springer.

示例

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