max_clique#

max_clique(G)[source]#

寻找最大团

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

Parameters:

Returns:

Raises:

Notes

无向图 G = (V, E) 中的团是顶点集的一个子集 C subseteq V ，使得 C 中的每两个顶点之间都存在一条边。这等价于说由 C 诱导的子图是完全的（在某些情况下，术语“团”也可能指该子图）。

最大团是给定图中可能的最大团。图 G 的团数 omega(G) 是 G 中最大团的顶点数。G 的交集数是覆盖 G 所有边的团的最小数量。

References

[1]

Boppana, R., & Halldórsson, M. M. (1992). 通过排除子图来近似最大独立集。 BIT Numerical Mathematics, 32(2), 180–196. Springer. doi:10.1007/BF01994876

Examples

>>> G = nx.path_graph(10)
>>> nx.approximation.max_clique(G)
{8, 9}