max_clique#
- max_clique(G)[源代码]#
找到最大的集团
查找 \(O(|V|/(log|V|)^2)\) 最大派系/独立集在最坏情况下的APX。
- 参数
- G网络X图表
无向图
- 返回
- clique设置
图的APX-最大团
- 加薪
- NetworkXNotImplemented
如果图是有向的或是多重图。
笔记
无向图中的一组G=（V，E）是顶点集的一个子集。
C subseteq V这样，对于C中的每两个顶点，都存在一条连接这两个顶点的边。这相当于说由c引起的子图是完整的（在某些情况下，术语clique也可以指子图）。最大集团是给定图表中最大可能规模的集团。集团编号
omega(G)图G的顶点数是图G中一个最大集团的顶点数。图G的交集数是图G所有边上的最小集团数。https://en.wikipedia.org/wiki/Maximum_clique
工具书类
- 1
Boppana，R.和Halld_rsson，M.M.（1992年）。通过排除子图近似最大独立集。位数字数学，32（2），180–196。Springer。doi:10.1007/bf01994876