分團問題
外观
在計算複雜度理論中,分團問題(clique problem)是圖論中的一個NP完全(NP-complete)問題。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/86/6n-graf-clique.svg/300px-6n-graf-clique.svg.png)
团(clique)是一個圖中兩兩相鄰的一個頂點集,或是一個完全子圖(complete subgraph),如右圖中的1、2、5三個頂點。
分团问题是問一個圖中是否有大小是k以上的团。任意挑出k個點,我們可以簡單的判斷出這k個點是不是一個团,所以這個問題屬於NP。
證明這問題是NP完備,我們可以很簡單的將獨立頂點集問題(Independent set problem)歸約成這個問題。因為存在一個大小是k以上的分團,等價於它的補圖中存在一個大小是k以上的獨立集。
演算法
[编辑]最簡單的方法是用暴力法列舉圖中所有k個點的子集合,並檢查它是不是团。在一個有V個點的圖中用暴力法找大小是k的团至少要檢查個子集合。
另外一個启发式的方法是先找出所有一個點的团,再慢慢合併成更大的团直到不能再合併為止。