-
分團問題
鎖定
在計算複雜度理論中,分團問題(clique problem)是圖論中的一個NP完全(NP-complete)問題。
- 中文名
- 分團問題
- 外文名
- clique problem
- 計算方法
- 列舉圖中所有k個點的子集合
- 學 科
- 計算複雜度理論
- 領 域
- 計算複雜度理論
分團問題內容簡介
一個大小為3的clique,clique是一個兩兩相連的一個點集,或是一個完全子圖(complete subgraph),如圖1中的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。
分團問題算法
最簡單的方法是用暴力法列舉圖中所有k個點的子集合,並檢查它是不是clique。在一個有V個點的圖中用暴力法找大小是k的clique至少要檢查
個子集合。
另外一個啓發式的方法是先找出所有一個點的clique,再慢慢合併成更大的clique直到不能再合併為止。
分團問題參見
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:12次歷史版本
- 最近更新: 水你喝不喝