max_clique#
- max_clique(G)[source]#
查找最大团
在最坏情况下，找到最大团/独立集的 \(O(|V|/(log|V|)^2)\) 近似。
- 参数:
- GNetworkX 图
无向图
- 返回:
- clique集合
图的近似最大团
- 引发:
- NetworkXNotImplemented
如果图是有向图或多重图。
说明
无向图 G = (V, E) 中的团是顶点集
C subseteq V的一个子集，使得 C 中任意两个顶点之间都存在一条边连接它们。这等价于说由 C 诱导的子图是完全图（在某些情况下，术语“团”也可能指该子图）。给定图中大小可能最大的团称为最大团。图 G 的团数
omega(G)是 G 中最大团的顶点数。G 的交数是能够覆盖 G 所有边的最小团数。https://en.wikipedia.org/wiki/Maximum_clique
参考文献
[1]Boppana, R., & Halldórsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2), 180–196. Springer. doi:10.1007/BF01994876
示例
>>> G = nx.path_graph(10) >>> nx.approximation.max_clique(G) {8, 9}