??獨(dú)立集：在圖G=(V, E)中存在子集V'∈V，任意u，v∈V'，(u, v)?E（或圖G的任意邊至多有一個端點(diǎn)在計劃V'中），集合V'就是圖G的一個獨(dú)立集。這樣的最大集合V'稱圖G的最大獨(dú)立集。獨(dú)立集的大小為這樣的點(diǎn)個數(shù)。
獨(dú)立集問題的NPC證明
Ⅰ. 3-SAT ≤p Independent Set
??已知3-SAT是一個NP難問題，可在多項式時間內(nèi)將3-SAT歸約到獨(dú)立集問題，那么說明獨(dú)立集問題也是一個NP難問題。需要證明，給定的一個有k個句子的3-SAT問題實(shí)例Ф，構(gòu)造一個圖，當(dāng)且僅當(dāng)Ф被滿足時，該圖具有大小為k的獨(dú)立集。
第一步 構(gòu)造一個3-SAT問題的實(shí)例
??這里構(gòu)造了3個句子（k=3），每個句子包含三個變量的是/非形式。
第二步 構(gòu)造圖
- 每個句子由三個相連的頂點(diǎn)表示
-
連接每個變量的是和非取值，如x1和!x1
根據(jù)3-SAT實(shí)例構(gòu)造獨(dú)立集問題的圖
??Claim: G具有大小為k的獨(dú)立集，當(dāng)且僅當(dāng)Ф被滿足。（Ф有k個句子）
第三步 證明
??規(guī)約的正確性，需雙向證明，即獨(dú)立集存在，則Ф被滿足；Ф被滿足，則獨(dú)立集存在。
=>
??圖G存在大小為k的獨(dú)立集，那么各三角形中必然有一點(diǎn)在獨(dú)立集中（三角形內(nèi)的點(diǎn)均相鄰，不獨(dú)立）；
??將這k個點(diǎn)（變量）的值設(shè)為true，那么其余所有點(diǎn)的取值均可確定下來；
??因為這k個點(diǎn)在k個不同的句子中，則Ф能被滿足，得證。
<=
??Ф被滿足，在k個句子中選取三個變量設(shè)為true，它們對應(yīng)圖G中k個三角形中的k個點(diǎn)；
??這k個點(diǎn)剛好構(gòu)成圖G大小為k的獨(dú)立集（因為互反的變量不會同時為true，即不會同時在k個點(diǎn)中），得證。
Ⅱ. Vertex Cover ≡p Independent Set
??Vertex cover(點(diǎn)覆蓋)：在圖G=(V, E)中存在子集V'∈V，任意邊（u,v）∈E，有u∈V或v∈U（圖G中的任一邊至少有一個端點(diǎn)在集合V'中），則集合V'就是圖G的一個點(diǎn)覆蓋。這樣的最小集合V'稱圖G的最小點(diǎn)覆蓋。
證明
??S是圖G=(V, E)的獨(dú)立集，當(dāng)且僅當(dāng)V-S是一個點(diǎn)覆蓋。（獨(dú)立集和點(diǎn)覆蓋互為補(bǔ)集）
=>
??S是圖G的任一獨(dú)立集
??則任意邊(u,v)∈E，有u ? S或v ? S；那么u∈V-S或v∈V-S
??所以圖的任意邊至少有一個端點(diǎn)在集合V-S中，集合V-S是一個點(diǎn)覆蓋
<=
??V-S是圖G的任一點(diǎn)覆蓋
??則任意邊(u,v)∈E，有u∈V-S或v∈V-S；那么u ? S或v ? S
??所以圖的任意邊至少有一個端點(diǎn)不在集合S中，集合S是一個獨(dú)立集
得證。
獨(dú)立集問題和團(tuán)問題
??團(tuán)：在圖G=(V, E)中存在子集V''∈V，任意u，v∈V''，(u, v)∈E，集合V''就是圖G的一個團(tuán)（即完全子圖）。這樣的最大集合V''，稱圖G的最大團(tuán)，點(diǎn)的個數(shù)即團(tuán)的大小。
??在一個圖G(V, E)中，若存在最大獨(dú)立集V'，則最大團(tuán)是最大獨(dú)立集的補(bǔ)集V-V'。
??因此，可以用同樣的方法證明團(tuán)問題也是一個NP難問題，根據(jù)3-SAT構(gòu)造的圖是上圖的補(bǔ)圖。
??Claim: G包含一個規(guī)模為k的團(tuán)，當(dāng)且僅當(dāng)Ф是可滿足的。
Independent Set ≤p Clique
??圖G=(V, E)中存在獨(dú)立集S，當(dāng)且僅當(dāng)在G的補(bǔ)圖G'=(V, E')中，S是一個團(tuán)。（補(bǔ)圖：點(diǎn)不變，邊取補(bǔ)）
=>
??圖G中有獨(dú)立集S，則任意u, v∈S，有(u, v) ? E;
??那么(u, v)∈E'，即在圖G'，S集合中任意兩點(diǎn)均有相連的邊；所以S是圖G'的團(tuán)。
<=
??圖G'中有團(tuán)S，則任意u, v∈S，有(u, v)∈E'；
??那么(u, v) ? E，即在圖G，S集合中任意兩點(diǎn)均不相連；所以S是圖G的獨(dú)立集。
Q
??等價問題（≡p）是如何證明的
