查看“︁分團問題”︁的源代码

在[[計算複雜性理論|計算複雜度理論]]中，分團問題（clique problem）是[[圖論]]中的一個[[NP完全]]（NP-complete）問題。

[[File:6n-graf-clique.svg|right|300px|thumb|一個大小為3的clique]]
团（clique）是一個[[图论|圖]]中兩兩相鄰的一個頂點[[集合 (数学)|集]]，或是一個[[完全圖|完全]]子圖（complete subgraph），如右圖中的1、2、5三個頂點。

分团问题是問一個圖中是否有大小是''k''以上的团。任意挑出k個點，我們可以簡單的判斷出這''k''個點是不是一個团，所以這個問題屬於[[NP]]。

證明這問題是[[NP完備]]，我們可以很簡單的將{{link-en|獨立頂點集問題|Independent set problem}}(Independent set problem)歸約成這個問題。因為存在一個大小是''k''以上的分團，等價於它的[[補圖]]中存在一個大小是''k''以上的[[獨立集]]。

== 演算法 ==

最簡單的方法是用[[暴力破解法|暴力法]]列舉[[圖]]中所有''k''個點的[[子集合]]，並檢查它是不是团。在一個有''V''個點的[[圖]]中用暴力法找大小是''k''的团至少要檢查<math>\frac{V!}{k!(V-k)!}</math>個子集合。

另外一個启发式的方法是先找出所有一個點的团，再慢慢合併成更大的团直到不能再合併為止。

[[Category:計算複雜性理論]]
[[Category:数学问题]]