最大完全子图

最大完全子圖（Maximum Complete Subgraph），也稱為最大團（Maximum Clique），是在一個圖中找到的最大的完全圖（Complete Graph）。完全圖是指圖中任意兩個頂點之間都存在邊。最大完全子圖的問題是在一個給定的圖中找到這樣的完全子圖，使得它包含的頂點數儘可能多。

例如，在一個包含6個頂點的圖中，如果存在一個包含5個頂點的完全子圖，那麼這個完全子圖就是最大完全子圖，因為不可能在一個圖中找到包含6個頂點的完全子圖。

最大完全子圖問題是一個NP-完全問題，這意味著對於給定的圖，沒有已知的可以在多項式時間內找到最大完全子圖的算法。對於小規模的圖，可以使用暴力搜尋或者一些啟發式算法來找到最大完全子圖。對於大規模的圖，通常需要使用近似算法或者專門針對特定類型圖的算法。

在圖論中，完全子圖的頂點數稱為團數（clique number），而最大完全子圖的頂點數稱為最大團數（maximum clique number）。最大團問題是圖理論中的一個核心問題，它在許多領域都有套用，如組合最佳化、機器學習、計算機視覺和生物信息學等。