獨立集（independent set)
圖中每一條邊至多有一個頂點在這個集合中，也就是說不會存在一條邊包含的兩個頂點都在這個集合中，即集合中不存在相鄰的頂點。我們希望盡可能找到更多的這樣的頂點。
點覆蓋（vertex cover)
圖中每一條邊至少有一個頂點在這個集合中，也就是說用點去覆蓋整個圖的所有的邊，當然，我們希望找到最少的點去覆蓋所有的邊。
獨立集和點覆蓋互補
觀察圖，發(fā)現(xiàn)互補
獨立集 ==p 點覆蓋
注意：p代表多項式時間等價
證明
先證明獨立集能在多項式時間內(nèi)推導出點覆蓋
-S是任意一個獨立集（圖為G=（V,E)）
-S中任意一條邊e(u,v)
-因為S是獨立集，所以u,v不能同時在S中，假設u不在S中，那么u必在V-S中，同理假設v不在S中，則ｖ必在V-S中，也有可能u,v都在V-S中，反正總而言之，V-S至少包含u,v中的一個，是不是很熟悉？沒錯，這就是點覆蓋的定義咯！所以V-S就是點覆蓋。
反過來如果已知了點覆蓋，在多項式時間內(nèi)推導出獨立集
-V-S是任意一個點覆蓋
-假設在S中有兩個頂點u,v
-那么u,v一定不能構成一條邊，為什么？因為假設u,v能構成一條邊，那么按照點覆蓋的定義，u,v中至少有一個點應該在V-S這個集合中，而不是都在集合S 里面
-因此，S中的任意兩個點不能構成一條邊，即不存在相鄰的頂點，即S是獨立集。
最大團問題
從無向圖的頂點集中選出k個并且k個頂點之間任意兩點之間都相鄰。最大的k就是最大團。
區(qū)分最大獨立集：從無向圖中的頂點中選出k個并且k個頂點之間互不相鄰，最大的k就是最大獨立集。
性質(zhì)
無向圖的最大團 ==p 該無向圖補圖的最大獨立集（補圖的意思就是有邊變無邊，無邊變有邊）
證明
正向證明
-S是任意一個團（G =（V，E））
-S中的任意兩點Su,v能構成一條圖中的邊
-現(xiàn)在把u,v構成的邊去掉
-那么u,v中任意兩點都不能構成圖中的邊，即兩兩點不相鄰，則此時的S是獨立集
逆向證明
-S是獨立集
-那么S中的任意兩點u,v均不能構成圖中的邊
-若u,v加上邊
-則S中任意的u,v之間都有邊，則S是團
最大是怎么做到的
S是最大團，那么V-S中的任意兩點均不存在邊，取補圖的時候，無邊變有邊，即任意點都有相鄰點，那么V-S中的所有點都不可出現(xiàn)在獨立集中。反過來，如果S是獨立集，那么V-S中所有的點都至少有一條邊與它相連（獨立集和點覆蓋互補），那么取補圖的時候，V-S中所有點都不會有邊，即任意兩點都沒有邊，那么也就是說V-S中的點必不能出現(xiàn)在最大團的集合中。
