主题
Search

最大团


G 的最大团是 (即,最大可能大小的完全子图)对于 G。请注意,一些作者将最大团简称为“团”。最大团的大小被称为图的团数,而对于给定的,找到团大小的问题是一个NP-完全问题 (Skiena 1997)。

给定 g 中的最大团可以在 Wolfram 语言 中使用以下命令找到:FindClique[g][[1]]。命令Sort[FindClique[g,Length /@ FindClique[g], All]] 将找到所有最大团。

完全 k-部图 的最大团大小为 k。不包含完全图 K_p 作为子图的最大阶数-n 图称为 图兰图 T(n,p-1) (Gross and Yellen 2006, pp. 476-477; 注意 Skiena 1990, p. 218 以及 Pemmaraju 和 Skiena 2003, pp. 247-248 中略微非标准的索引 T(n,p))。


另请参阅

穴居人图, , 团图, 团数, 完全图, 导出子图, 极大团 聚会问题, 完美图, 拉姆齐数, 图兰定理

使用 Wolfram|Alpha 探索

参考文献

Bellare, M.; Goldreich, O.; 和 Sudan, M. "自由位、PCP 和非近似性——迈向严格的结果。" SIAM J. Comput. 27, 804-915, 1998.Cormen, T.; Leiserson, C.; 和 Rivest, R. 算法导论。 Cambridge, MA: MIT 出版社, 1990.Harary, F. 图论。 Reading, MA: Addison-Wesley, 1994.Karp, R. M. "组合问题之间的可归约性。" 计算机计算的复杂性 (R. Miller 和 J. Thatcher 编辑). New York: Plenum, pp. 85-103, 1972.Garey, M. R. 和 Johnson, D. S. 计算机与难解性:NP-完全性理论指南。 New York: W. H. Freeman, 1983.Gross, J. T. 和 Yellen, J. 图论及其应用,第二版。 Boca Raton, FL: CRC Press, pp. 476-477, 2006.Manber, U. 算法导论:一种创造性方法。 Reading, MA: Addison-Wesley, 1989.Pemmaraju, S. 和 Skiena, S. 计算离散数学:Mathematica 中的组合学和图论。 Cambridge, England: Cambridge University Press, pp. 247-248, 2003.Skiena, S. "最大团。" §5.6.1 in 实现离散数学:Mathematica 中的组合学和图论。 Reading, MA: Addison-Wesley, pp. 215 和 217-218, 1990.Skiena, S. S. "团和独立集" 和 "团。" §6.2.3 和 8.5.1 in 算法设计手册。 New York: Springer-Verlag, pp. 144 和 312-314, 1997.Sloane, N. J. A. 序列 A005289/M3440 在 "整数序列在线百科全书" 中。

引用为

Weisstein, Eric W. "最大团。" 来自 MathWorld--一个 Wolfram Web 资源。 https://mathworld.net.cn/MaximumClique.html

学科分类