獨(dú)立集（independent set)
圖中每一條邊至多有一個(gè)頂點(diǎn)在這個(gè)集合中，也就是說(shuō)不會(huì)存在一條邊包含的兩個(gè)頂點(diǎn)都在這個(gè)集合中，即集合中不存在相鄰的頂點(diǎn)。我們希望盡可能找到更多的這樣的頂點(diǎn)。
點(diǎn)覆蓋（vertex cover)
圖中每一條邊至少有一個(gè)頂點(diǎn)在這個(gè)集合中，也就是說(shuō)用點(diǎn)去覆蓋整個(gè)圖的所有的邊，當(dāng)然，我們希望找到最少的點(diǎn)去覆蓋所有的邊。
獨(dú)立集和點(diǎn)覆蓋互補(bǔ)
觀察圖，發(fā)現(xiàn)互補(bǔ)
獨(dú)立集 ==p 點(diǎn)覆蓋
注意：p代表多項(xiàng)式時(shí)間等價(jià)
證明
先證明獨(dú)立集能在多項(xiàng)式時(shí)間內(nèi)推導(dǎo)出點(diǎn)覆蓋
-S是任意一個(gè)獨(dú)立集（圖為G=（V,E)）
-S中任意一條邊e(u,v)
-因?yàn)镾是獨(dú)立集，所以u(píng),v不能同時(shí)在S中，假設(shè)u不在S中，那么u必在V-S中，同理假設(shè)v不在S中，則ｖ必在V-S中，也有可能u,v都在V-S中，反正總而言之，V-S至少包含u,v中的一個(gè)，是不是很熟悉？沒(méi)錯(cuò)，這就是點(diǎn)覆蓋的定義咯！所以V-S就是點(diǎn)覆蓋。
反過(guò)來(lái)如果已知了點(diǎn)覆蓋，在多項(xiàng)式時(shí)間內(nèi)推導(dǎo)出獨(dú)立集
-V-S是任意一個(gè)點(diǎn)覆蓋
-假設(shè)在S中有兩個(gè)頂點(diǎn)u,v
-那么u,v一定不能構(gòu)成一條邊，為什么？因?yàn)榧僭O(shè)u,v能構(gòu)成一條邊，那么按照點(diǎn)覆蓋的定義，u,v中至少有一個(gè)點(diǎn)應(yīng)該在V-S這個(gè)集合中，而不是都在集合S 里面
-因此，S中的任意兩個(gè)點(diǎn)不能構(gòu)成一條邊，即不存在相鄰的頂點(diǎn)，即S是獨(dú)立集。
最大團(tuán)問(wèn)題
從無(wú)向圖的頂點(diǎn)集中選出k個(gè)并且k個(gè)頂點(diǎn)之間任意兩點(diǎn)之間都相鄰。最大的k就是最大團(tuán)。
區(qū)分最大獨(dú)立集：從無(wú)向圖中的頂點(diǎn)中選出k個(gè)并且k個(gè)頂點(diǎn)之間互不相鄰，最大的k就是最大獨(dú)立集。
性質(zhì)
無(wú)向圖的最大團(tuán) ==p 該無(wú)向圖補(bǔ)圖的最大獨(dú)立集（補(bǔ)圖的意思就是有邊變無(wú)邊，無(wú)邊變有邊）
證明
正向證明
-S是任意一個(gè)團(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)不相鄰，則此時(shí)的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ǔ)圖的時(shí)候，無(wú)邊變有邊，即任意點(diǎn)都有相鄰點(diǎn)，那么V-S中的所有點(diǎn)都不可出現(xiàn)在獨(dú)立集中。反過(guò)來(lái)，如果S是獨(dú)立集，那么V-S中所有的點(diǎn)都至少有一條邊與它相連（獨(dú)立集和點(diǎn)覆蓋互補(bǔ)），那么取補(bǔ)圖的時(shí)候，V-S中所有點(diǎn)都不會(huì)有邊，即任意兩點(diǎn)都沒(méi)有邊，那么也就是說(shuō)V-S中的點(diǎn)必不能出現(xiàn)在最大團(tuán)的集合中。
