分團覆蓋問題
在計算複雜度理論內，找一個最小的分團覆蓋（clique cover）是一個圖論的NP完全問題。這問題屬於卡普的二十一個NP-完全問題之一，由卡普在1972年的論文"Reducibility Among Combinatorial Problems"證明為NP完全[1]。
分團覆蓋問題（有時叫做分成分團，partition into cliques）是問一個圖裡面的所有點可否分成k個分團。一旦給定了這個圖該怎麼分成k個分團，我們可以在多項式時間裡面檢證這個答案是否正確，因此我們可以知道這個問題屬於NP。
分團覆蓋問題是NP完全這件事情，可以藉由將此問題從k-圖著色問題（GRAPH k-COLOURABILITY）歸約出來而得證[2]。要推出這個結果，首先我們將一個k-圖著色問題的輸入圖G轉成其補圖G'。那麼，求出G' 怎麼分出k個分團這問題就等同於求出G怎麼分出k個獨立集；我們能將每個獨立集設立一個顏色來得到k個顏色，並且保證G內所有相同顏色的點不會互相連接。因此，解出G' 的分團問題，即是解出G的著色問題。因為我們已知k-著色問題是NP完全問題，所以我們能藉由將所有NP的問題先歸約為k-著色問題，再歸約為分團覆蓋問題，而將所有NP完全問題歸約成分團覆蓋問題。故分團覆蓋問題是NP完全問題。
相關的問題分團邊覆蓋則是考慮是否存在分團的集合能包含圖中所有的邊（edge）。這個問題也一樣是NP完全問題。
參考資料 编辑
- ^ Karp, Richard, Reducibility Among Combinatorial Problems (PDF), Miller, R. E.; Thatcher, J. W. (编), Proceedings of a Symposium on the Complexity of Computer Computations, Plenum Press: 85–103, 1972 [2008-08-29], （原始内容 (PDF)存档于2011-06-29）
- ^ Garey, Michael R.; Johnson, David S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman: 194, 1979, ISBN 0-7167-1045-5
 | 这是一篇小作品。你可以通过编辑或修订扩充其内容。 |