分團問題

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

一個大小為3的clique

團（clique）是一個圖中兩兩相鄰的一個頂點集，或是一個完全子圖（complete subgraph），如右圖中的1、2、5三個頂點。

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

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

演算法

最簡單的方法是用暴力法列舉圖中所有k個點的子集合，並檢查它是不是團。在一個有V個點的圖中用暴力法找大小是k的團至少要檢查${\frac {V!}{k!(V-k)!}}$個子集合。

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