maximum_independent_set#
- maximum_independent_set(G)[源代码]#
返回一个近似的最大独立集。
独立集或稳定集是图中没有两个相邻的顶点的集合。也就是说，它是一组顶点，使得对于i中的每两个顶点，没有连接这两个顶点的边。等价地，图中的每条边在I中至多有一个端点。独立集的大小是它所包含的顶点的数目 [1].
最大独立集是给定图G的最大独立集，其大小表示为 \(\alpha(G)\) 。寻找这样一个集合的问题称为最大独立集问题，是一个NP-Hard优化问题。因此，不太可能存在用于寻找图的最大独立集的有效算法。
独立集算法基于 [2].
- 参数
- G网络X图表
无向图
- 返回
- iset设置
APX-极大独立集
- 加薪
- NetworkXNotImplemented
如果图是有向的或是多重图。
笔记
查找 \(O(|V|/(log|V|)^2)\) 在最坏的情况下，独立集的APX。
工具书类