獨(dú)立集（independent set)
圖中每一條邊至多有一個頂點(diǎn)在這個集合中野来，也就是說不會存在一條邊包含的兩個頂點(diǎn)都在這個集合中，即集合中不存在相鄰的頂點(diǎn)功蜓。我們希望盡可能找到更多的這樣的頂點(diǎn)。
點(diǎn)覆蓋（vertex cover)
圖中每一條邊至少有一個頂點(diǎn)在這個集合中，也就是說用點(diǎn)去覆蓋整個圖的所有的邊产舞，當(dāng)然，我們希望找到最少的點(diǎn)去覆蓋所有的邊菠剩。
獨(dú)立集和點(diǎn)覆蓋互補(bǔ)
觀察圖易猫，發(fā)現(xiàn)互補(bǔ)
獨(dú)立集 ==p 點(diǎn)覆蓋
注意：p代表多項式時間等價
證明
先證明獨(dú)立集能在多項式時間內(nèi)推導(dǎo)出點(diǎn)覆蓋
-S是任意一個獨(dú)立集（圖為G=（V,E)）
-S中任意一條邊e(u,v)
-因為S是獨(dú)立集，所以u,v不能同時在S中具壮，假設(shè)u不在S中准颓，那么u必在V-S中哈蝇，同理假設(shè)v不在S中，則ｖ必在V-S中攘已，也有可能u,v都在V-S中炮赦，反正總而言之，V-S至少包含u,v中的一個贯被，是不是很熟悉眼五？沒錯，這就是點(diǎn)覆蓋的定義咯彤灶！所以V-S就是點(diǎn)覆蓋看幼。
反過來如果已知了點(diǎn)覆蓋，在多項式時間內(nèi)推導(dǎo)出獨(dú)立集
-V-S是任意一個點(diǎn)覆蓋
-假設(shè)在S中有兩個頂點(diǎn)u,v
-那么u,v一定不能構(gòu)成一條邊幌陕，為什么诵姜？因為假設(shè)u,v能構(gòu)成一條邊，那么按照點(diǎn)覆蓋的定義搏熄，u,v中至少有一個點(diǎn)應(yīng)該在V-S這個集合中棚唆，而不是都在集合S 里面
-因此，S中的任意兩個點(diǎn)不能構(gòu)成一條邊心例，即不存在相鄰的頂點(diǎn)宵凌，即S是獨(dú)立集。
最大團(tuán)問題
從無向圖的頂點(diǎn)集中選出k個并且k個頂點(diǎn)之間任意兩點(diǎn)之間都相鄰止后。最大的k就是最大團(tuán)瞎惫。
區(qū)分最大獨(dú)立集：從無向圖中的頂點(diǎn)中選出k個并且k個頂點(diǎn)之間互不相鄰，最大的k就是最大獨(dú)立集译株。
性質(zhì)
無向圖的最大團(tuán) ==p 該無向圖補(bǔ)圖的最大獨(dú)立集（補(bǔ)圖的意思就是有邊變無邊瓜喇，無邊變有邊）
證明
正向證明
-S是任意一個團(tuán)（G =（V，E））
-S中的任意兩點(diǎn)Su,v能構(gòu)成一條圖中的邊
-現(xiàn)在把u,v構(gòu)成的邊去掉
-那么u,v中任意兩點(diǎn)都不能構(gòu)成圖中的邊歉糜，即兩兩點(diǎn)不相鄰乘寒，則此時的S是獨(dú)立集
逆向證明
-S是獨(dú)立集
-那么S中的任意兩點(diǎn)u,v均不能構(gòu)成圖中的邊
-若u,v加上邊
-則S中任意的u,v之間都有邊，則S是團(tuán)
最大是怎么做到的
S是最大團(tuán)匪补，那么V-S中的任意兩點(diǎn)均不存在邊伞辛，取補(bǔ)圖的時候，無邊變有邊夯缺，即任意點(diǎn)都有相鄰點(diǎn)始锚，那么V-S中的所有點(diǎn)都不可出現(xiàn)在獨(dú)立集中。反過來喳逛，如果S是獨(dú)立集瞧捌，那么V-S中所有的點(diǎn)都至少有一條邊與它相連（獨(dú)立集和點(diǎn)覆蓋互補(bǔ)），那么取補(bǔ)圖的時候，V-S中所有點(diǎn)都不會有邊姐呐，即任意兩點(diǎn)都沒有邊殿怜，那么也就是說V-S中的點(diǎn)必不能出現(xiàn)在最大團(tuán)的集合中。
