clique_removal

clique_removal(G)

重复地从图中移除团。

得到最大团和独立集的 \(O(|V|/(\log |V|)^2)\) 近似。返回找到的最大独立集，以及找到的极大团。

参数：

GNetworkX 图

无向图

返回值：

max_ind_cliques(集合, 列表) 元组

一个二元组，包含极大独立集（集合）和极大团列表（集合）。

抛出异常：

NetworkXNotImplemented

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

参考文献

[1]

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.clique_removal(G)
({0, 2, 4, 6, 9}, [{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}])