??獨立集：在圖G=(V, E)中存在子集V'∈V捂龄，任意u躏哩，v∈V'悯蝉，(u, v)?E（或圖G的任意邊至多有一個端點在計劃V'中），集合V'就是圖G的一個獨立集挺峡。這樣的最大集合V'稱圖G的最大獨立集葵孤。獨立集的大小為這樣的點個數(shù)。
獨立集問題的NPC證明
Ⅰ. 3-SAT ≤p Independent Set
??已知3-SAT是一個NP難問題橱赠，可在多項式時間內(nèi)將3-SAT歸約到獨立集問題尤仍，那么說明獨立集問題也是一個NP難問題。需要證明狭姨，給定的一個有k個句子的3-SAT問題實例Ф宰啦，構造一個圖苏遥，當且僅當Ф被滿足時，該圖具有大小為k的獨立集赡模。
第一步 構造一個3-SAT問題的實例
??這里構造了3個句子（k=3）田炭，每個句子包含三個變量的是/非形式。
第二步 構造圖
- 每個句子由三個相連的頂點表示
-
連接每個變量的是和非取值漓柑，如x1和!x1
根據(jù)3-SAT實例構造獨立集問題的圖
??Claim: G具有大小為k的獨立集教硫，當且僅當Ф被滿足。（Ф有k個句子）
第三步 證明
??規(guī)約的正確性辆布，需雙向證明瞬矩，即獨立集存在，則Ф被滿足锋玲；Ф被滿足景用，則獨立集存在。
=>
??圖G存在大小為k的獨立集惭蹂，那么各三角形中必然有一點在獨立集中（三角形內(nèi)的點均相鄰伞插，不獨立）；
??將這k個點（變量）的值設為true盾碗，那么其余所有點的取值均可確定下來媚污；
??因為這k個點在k個不同的句子中，則Ф能被滿足置尔，得證杠步。
<=
??Ф被滿足氢伟，在k個句子中選取三個變量設為true榜轿，它們對應圖G中k個三角形中的k個點；
??這k個點剛好構成圖G大小為k的獨立集（因為互反的變量不會同時為true朵锣，即不會同時在k個點中）谬盐，得證。
Ⅱ. Vertex Cover ≡p Independent Set
??Vertex cover(點覆蓋)：在圖G=(V, E)中存在子集V'∈V诚些，任意邊（u,v）∈E飞傀，有u∈V或v∈U（圖G中的任一邊至少有一個端點在集合V'中），則集合V'就是圖G的一個點覆蓋诬烹。這樣的最小集合V'稱圖G的最小點覆蓋砸烦。
證明
??S是圖G=(V, E)的獨立集，當且僅當V-S是一個點覆蓋绞吁。（獨立集和點覆蓋互為補集）
=>
??S是圖G的任一獨立集
??則任意邊(u,v)∈E幢痘，有u ? S或v ? S；那么u∈V-S或v∈V-S
??所以圖的任意邊至少有一個端點在集合V-S中家破，集合V-S是一個點覆蓋
<=
??V-S是圖G的任一點覆蓋
??則任意邊(u,v)∈E颜说，有u∈V-S或v∈V-S购岗；那么u ? S或v ? S
??所以圖的任意邊至少有一個端點不在集合S中，集合S是一個獨立集
得證门粪。
獨立集問題和團問題
??團：在圖G=(V, E)中存在子集V''∈V喊积，任意u，v∈V''玄妈，(u, v)∈E乾吻，集合V''就是圖G的一個團（即完全子圖）。這樣的最大集合V''拟蜻，稱圖G的最大團溶弟，點的個數(shù)即團的大小。
??在一個圖G(V, E)中瞭郑，若存在最大獨立集V'辜御，則最大團是最大獨立集的補集V-V'。
??因此屈张，可以用同樣的方法證明團問題也是一個NP難問題擒权，根據(jù)3-SAT構造的圖是上圖的補圖。
??Claim: G包含一個規(guī)模為k的團阁谆，當且僅當Ф是可滿足的碳抄。
Independent Set ≤p Clique
??圖G=(V, E)中存在獨立集S，當且僅當在G的補圖G'=(V, E')中场绿，S是一個團剖效。（補圖：點不變，邊取補）
=>
??圖G中有獨立集S焰盗，則任意u, v∈S璧尸，有(u, v) ? E;
??那么(u, v)∈E'，即在圖G'熬拒，S集合中任意兩點均有相連的邊爷光；所以S是圖G'的團。
<=
??圖G'中有團S澎粟，則任意u, v∈S蛀序，有(u, v)∈E'；
??那么(u, v) ? E活烙，即在圖G徐裸，S集合中任意兩點均不相連；所以S是圖G的獨立集啸盏。
Q
??等價問題（≡p）是如何證明的
