clique_removal#
- clique_removal(G)[source]#
重复地从图中移除团。
结果得到一个 \(O(|V|/(\log |V|)^2)\) 的最大团和独立集的近似解。返回找到的最大独立集以及找到的最大团。
- Parameters:
- GNetworkX 图
无向图
- Returns:
- max_ind_cliques(集合, 列表) 元组
最大独立集和最大团的列表（集合）的 2-元组。
- Raises:
- NetworkXNotImplemented
如果图是有向的或是一个多重图。
References
[1]Boppana, R., & Halldórsson, M. M. (1992). 通过排除子图来近似最大独立集。 BIT 数值数学, 32(2), 180–196. Springer.
Examples
>>> G = nx.path_graph(10) >>> nx.approximation.clique_removal(G) ({0, 2, 4, 6, 9}, [{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}])