分團覆蓋問題在計算複雜度理論內，找一個最小的分團覆蓋（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完全問題。 參考資料
|
Index:
pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
Portal di Ensiklopedia Dunia
