主題
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))。


另請參閱

穴居人圖, , 團圖, 團數, 完全圖, 匯出子圖, 極大團 聚會問題, 完美圖, 拉姆齊數, 圖蘭定理

使用 探索

參考文獻

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. "最大團。" 來自 --一個 資源。 https://mathworld.tw/MaximumClique.html

學科分類