在計算複雜度理論中，分團問題（clique problem）是圖論中的一個NP完全（NP-complete）問題。
基本介紹
- 中文名：分團問題
- 外文名：clique problem
- 計算方法：列舉圖中所有k個點的子集合
- 屬於：NP完全（NP-complete）問題
- 學科：計算複雜度理論
- 領域：計算複雜度理論
概述,算法,參見,
概述
在計算複雜度理論中，分團問題(clique problem)是圖論中的一個NP完備(NP-complete)問題。
圖1.一個大小為3的clique一個大小為3的clique，clique是一個圖中兩兩相連的一個點集，或是一個完全子圖(complete subgraph)，如右圖中的1, 2, 5三個點。
clique problem是問一個圖中是否有大小是k以上的clique。任意挑出k個點，我們可以簡單的判斷出這k個點是不是一個clique，所以這個問題屬於NP。
證明clique problem是NP完備可以很簡單的從獨立頂點集問題（Independent set problem）reduce。因為存在一個大小是k以上的clique等價於它的complement graph中存在一個大小是k以上的Independent set。
算法
另外一個啟發式的方法是先找出所有一個點的clique，再慢慢合併成更大的clique直到不能再合併為止。
