一、定義
設G=(V,E)是一個圖，邏輯結構分為兩部分：V和E集合，其中，V是頂點，E是邊。
簡單定義如下：
樹(圖)的最小支配集：點集中取出儘量少的點，使剩下的點與取出來的點都有邊相連。
樹(圖)的最小點覆蓋：點集中取出儘量少的點，使得所有邊都與選出的點相連。
樹(圖)的最大獨立集：點集中取出儘量多的點，使得這些點兩兩之間沒有邊相連。
二、詳細描述1、最小支配集(minimal dominating set)對於圖G=(V,E)來說，設V'是圖G的一個支配集，則對於圖中的任意一個頂點u，要麼屬於集合V'，要麼與V'中的頂點相連。在V'中除去任何元素後V'不再是支配集，則支配集V'是極小支配集。稱G中所有支配集中頂點個數最少的支配集為最小支配集，最小支配集中的頂點個數稱為支配數。
如圖2-1 最小點覆蓋V' = {1}，紅色結點1覆蓋了2、3、4、5結點。
圖2-1
如圖2-2 最小點覆蓋V' = {2，6，7}，紅色結點2覆蓋了1、4、5結點；紅色結點6覆蓋了3、8、9結點；紅色結點7覆蓋了重複的3、9結點。
圖2-2
2、最小點覆蓋(minimum point coverage)對於圖G=(V,E)來說，設V'是圖G的一個頂點覆蓋，從V中取儘量少的點組成一個集合，使得E中所有的邊都與取出來的點相連。在V'中除去任何元素後V'不再是頂點覆蓋，則V'是極小點覆蓋。稱G中所有頂點覆蓋中頂點個數最小的覆蓋為最小點覆蓋。
如圖2-3 極小點覆蓋，也是最小點覆蓋V' = {1, 2, 3}，紅色結點1覆蓋了4紅色的條邊；藍色的結點2覆蓋了2條藍色的邊；綠色的結點3覆蓋了兩條綠色的邊。
圖2-3
如圖2-4 最小點覆蓋V' = {2, 4, 7}， 紅色的結點2覆蓋了3條邊(2, 5),(2, 6),(2, 8); 紅色的結點4覆蓋了3條邊(4, 7),(4, 8),(4, 9); 紅色的結點7覆蓋了3條邊(7, 1),(7, 3),(7, 4)。
如圖2-4
如圖2-5 最小點覆蓋V' = {2, 3, 8，9}， 紅色的結點2覆蓋了3條邊(2, 1),(2, 4),(2, 5); 紅色的結點3覆蓋了3條邊(3, 1),(3, 6),(3, 7); 紅色的結點8覆蓋了3條邊(8, 4),(8, 5),(8, 6)；紅色的結點9覆蓋了2條邊(9, 6),(9, 7)。
圖2-5
3、最大獨立集(minimum independent set)對於圖G=(V,E)來說，設V'是圖G的一個獨立集，則對於圖中任意一條邊(u,v)，u和v不能同時屬於集合V'，甚至可以u和v都不屬於集合V'。在V'中新增任何不屬於V'元素後V'不再是獨立集，則V'是極大獨立集。稱G中所有頂點獨立集中頂點個數最多的獨立集為最大獨立集。
如圖2-6 極大獨立集，也是最大獨立集V' = {2，3}
圖2-6
如圖2-7 最大獨立集V' = {1，4，5，6，7}。
圖2-7
如圖2-8 最大獨立集V' = {a，c，j，f，g}, 極大獨立集V' = {a，d，h，f},
圖2-8
三、演示例子先介紹貪心策略的基礎知識：
貪心策略是一種常見的演算法思想，具體是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的區域性最優解。貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關，這樣求出的區域性最優解也是全域性最優解。
1、最小支配集最小支配集問題具有貪心選擇性質和最優子結構性質。
1.1 貪心演算法首先選擇一結點為樹根，再按照深度優先遍歷得到遍歷序列，按照所得序列的反向序列的順序進行貪心，對於一個即不屬於支配集也不與支配集中的點相連的點來說，如果他的父結點不屬於支配集,將其父結點加入到支配集。
以根結點深度優先遍歷整棵樹，求出每個點在深度優先遍歷序列中的編號和每個點的父結點編號。按照深度優先遍歷的反向順序檢查每個點，如果當前點不屬於支配集也不與支配集的點相連，且它的父結點不屬於支配集，將其父結點加入到支配集，支配集中點的個數加 1，標記當前結點, 當前結點的父結點, 當前結點的父結點的父結點。因為這些結點要麼屬於支配集(當前點的父結點)，要麼與支配集中的點相連（當前結點和當前結點的父結點的父結點）。圖3-1 圖G
已知：如圖3-1 G(V，E)。
求：圖G的最小支配集。
解答：為了簡化描述，先做如下宣告：
條件A：當前點不屬於支配集也不與支配集的點相連,且它的父結點不屬於支配集。
標記B: 標記當前結點，當前結點的父結點，當前結點的父結點的父結點。
第1步，首先對圖3-1的圖G按從左到右的順序進行深度優先搜尋，獲取結果序列：1，2，4，8，5，6，3，7，9。其反向順序為：9，7，3，6，5，8，4，2，1。記住搜尋時的父結點（因為有多個鄰結點時，選擇鄰結點的次序不同會導致有多個搜尋序列，對應的同一個編號的結點的父結點也會不同）。
第2步，開始初始化支配集V’ = { }, V={9，7，3，6，5，8，4，2，1}，考察當前結點9，滿足條件A， 則將其父結點7加入支配集，有V’ = {7 }。 當前結點9採取動作標記B，則V={9*，7*，3*，6，5，8，4，2，1}。如3-2所示。
圖3-2
第3步，考察V中沒做標記的結點6，滿足條件A，則將其父結點8加入支配集，有V’ = {7，8 }。 對當前結點8採取動作標記B，則V={9*，7*，3*，6*，5，8*，4*，2，1}。如圖3-3所示。
圖3-3
第4步，考察V中沒做標記的結點5，其父結點8在支配集中，不滿足條件A，也做標記，有V={9*，7*，3*，6*，5*，8*，4*，2，1}。
第5步，考察V中沒做標記的結點2，滿足條件A，則將其父結點1加入支配集，有V’ = {7，8，1}。對當前結點2採取動作標記B，則V={9*，8*，7*，6*，5*，4*，3*，2*，1*}。如圖3-4所示。
圖3-4
最終採用貪心演算法得到了圖3-1中圖G的最小支配集V’ = {7，8，1}。
再舉一例
如圖3-5所示的圖G。
圖3-5
第1步，其深度優先搜尋結果0，3，1，5，2，4，6。逆序為6，4，2，5，1，3，0。
第2步，開始初始化支配集V’ = { }, V={6，4，2，5，1，3，0}，選結點6，滿足條件A，將父結點5加入V’ = {5 }, 標記V={6*，4，2*，5，1*，3，0}。
第3步，選結點4，父結點是5，不滿足條件A。標記V={6*，4*，2，5*，1*，3，0}。
第4步，選結點2，父結點是5，不滿足條件A。標記V={6*，4*，2*，5*，1*，3，0}。
第5步，選結點3，滿足條件A。父結點0加入V’ = {5，0 }, 標記V={6*，4*，2*，5*，1*，3*，0*}。
採用貪心演算法得到最小支配集V’ = {5，0}。如圖3-6所示。
圖3-6
小結：
對圖3-1，選擇的根不同，選擇的相鄰結點不同，導致深度優先搜尋的結果序列不同，可能會有多個不同的最小支配集。
1.2 樹形動態規劃演算法
強調一下，這裡的動態規劃演算法只適合樹形圖。
一個結點被覆蓋，分為3種情況：
被它自己覆蓋被它的兒子結點覆蓋被它的父親覆蓋1> 狀態定義
對於每個點設計了三種狀態，這三種狀態的意義如下：
dp[i][0]: 點i屬於支配集，並且以點i為根的子樹都被覆蓋了的情況下，支配集中包含的最少點數。
dp[i][1]: 點i不屬於支配集，且以i為根的子樹都被覆蓋，且i被其中不少於1個子結點覆蓋的情況下，支配集包含的最少點數。
dp[i][2]: 點i不屬於支配集，且以i為根的子樹都被覆蓋，且i沒被子結點覆蓋的情況下，支配集包含的最少點數。
狀態轉移方程第一種狀態
dp[i][0]等於每個兒子結點的3種狀態（其兒子是否被覆蓋沒有關係）的最小值之和加1，即只要每個以i的兒子為根的子樹都被覆蓋，再加上當前點i,所需要的最少點的個數。
轉移方程為：
dp[i][0] = 1 + Σmin( dp[son(i)][0], dp[son(i)][1], dp[son(i)][2] )
第二種狀態
如果點i沒有子結點，那麼dp[i][1]=INF（無窮大）；否則，需要保證它的每個以i的兒子為根的子樹都被覆蓋，那麼要取每個兒子結點的前兩種狀態的最小值之和，因為此時i點不屬於支配集，不能支配其子結點，所以子結點必須已經被支配，與子結點的第三種狀態無關。如果當前所選的狀態中，每個兒子都沒有被選擇進入支配集，即在每個兒子的前兩種狀態中，第一種狀態都不是所需點最少的，那麼為了滿足第二種狀態的定義，需要重新選擇點i的一個兒子的狀態為第一種狀態，這時取花費最少的一個點，即取min(dp[u][0]-dp[u][1])的兒子結點，強制取其第一種狀態，其他兒子結點都取第二種狀態。
轉移方程為：
if(i沒有子結點) dp[i][1] = INFelse dp[i][1] = Σmin( dp[son(i)][0], dp[son(i)][1] ) + inc其中對於inc有：if(上面式子中的Σmin(dp[son(i)][0], dp[son(i)][1]) 中包含某個dp[son(i)][0]) inc=0;else Inc = min(dp[son(i)][0]-dp[son(i)][1])。第三種狀態
i不屬於支配集，且以i為根的子樹都被覆蓋。i沒被子結點覆蓋，那麼說明點i和點i的兒子結點都不屬於支配集，則點i的第三種狀態只與其兒子的第二種狀態有關。
轉移方程為：
dp[i][2] = Σdp[son(i)][1]。圖3-7 圖G
2.1 貪心策略在用貪心法解決最小點覆蓋問題中，它貪的是覆蓋的邊最多的頂點。用鄰接矩陣儲存無向圖，矩陣中每行的和即為頂點的出度。出度最多的頂點即為最優量度標準。
最小點覆蓋其一般特性：
(1)找覆蓋邊最多的頂點
(2)已選中的頂點和未選中的頂點
(3)選擇函式：從未選的頂點集中找到出度最多的頂點
第1步，從圖3-7中，對圖G建立鄰接矩陣，橫座標與縱座標代表結點編號，直接相鄰結點置1，沒有直接相鄰置0。如圖3-8所示。
圖3-8
第2步，設h[i] (i=1-9)表示1到9行每一行的1的累加和。h[1]=3, h[2]=4, h[3]=4,h[4]=3,...,h[9]=3。找到其中最大值 h[2]=4的結點2， 將結點2對應的第2行與第2列中所有的1改為0。如圖3-9所示。
圖3-9
第3步，重新計算矩陣值，得到最大值h[3]=4, 找到結點3，對應的第3行第3列所有的1改為0。如圖3-10所示。
圖3-10
第4步，重新計算矩陣值，得到最大值h[8]=4, 找到結點8，對應的第8行第8列所有的1改為0。如圖3-11所示。
圖3-11
第5步，重新計算矩陣值，得到最大值h[9]=3, 找到結點9，對應的第9行第9列所有的1改為0。如圖3-12所示。
圖3-12
採用貪心演算法得到最小點覆蓋V’ = {2，3，8，9}。如圖3-13所示。
圖3-13
2.2 樹形動態規劃法：狀態定義
對於最小的覆蓋問題，為每個點設計了兩種狀態，這兩種狀態的意義如下：
1> dp[i][0]: 點i屬於點覆蓋，並且以點i為根的子樹中所連線的邊都被覆蓋的情況下，點覆蓋集所包含的最少點數；
2> dp[i][1]: 點i不屬於點覆蓋，並且以點i為根的子樹中所連線的邊都被覆蓋的情況下，點覆蓋集所包含的最少點數。
狀態轉移方程
第一種狀態
dp[i][0]，等於每個兒子結點的兩種狀態的最小值之和加1
狀態轉移方程如下：
dp[i][0] = 1 + Σmin(dp[son(i)][0], dp[son(i)][1])第二種狀態
dp[i][1]，要求所有與i連線的邊都被覆蓋，但是i點不屬於點覆蓋，那麼i點所有的子結點都必須屬於點覆蓋，即對於點i的第二種狀態與所有子結點的第一種狀態無關，在數值上等於所有子結點的第一種狀態之和。
狀態轉移方程如下：
dp[i][1] = Σdp[son(i)][0]首先選擇一點為樹根，再按照深度優先遍歷得到遍歷序列，按照所得序列的反向序列的順序進行貪心，對於一個即不屬於支配集也不與支配集中的點相連的點來說，如果他的父結點不屬於最大獨立集，將其父結點加入到獨立集。
3.2 樹形動態規劃法狀態定義
對於最大獨立集問題，為每個結點設立兩種狀態，這兩種狀態的意義如下：
1> dp[i][0]: 點i屬於獨立集的情況下，最大獨立集中點的個數
2> dp[i][1]: 點i不屬於獨立集的情況下，最大獨立集中點的個數
狀態轉移方程
第一種狀態
dp[i][0]，由於點i屬於獨立集，他的子結點都不能屬於獨立集，所以只與第二種狀態有關。
狀態轉移方程如下：
dp[i][0] = ∑dp[son(i)][1] + 1第二種狀態
點i的子結點可以屬於獨立集，也可以不屬於獨立集。
狀態轉移方程如下：
dp[i][1] = ∑max(dp[son(i)][1], dp[son(i)][0])這個狀態轉移方程的意思就是：
當 i 結點被選中的時候，那麼它的所有兒子結點肯定不能被選中；當 i 結點沒有被選中的時候，它的兒子結點可以屬於獨立集，也可以不屬於獨立集，所以取兩者中的較大者。四、附錄附錄1定義：如果一個圖是二分圖，那麼它的最大獨立集就是多項式時間可以解決的問題了。
求證： |最大獨立集| = |V|-|最大匹配數|證明：設最大獨立集數為U，最大匹配數為M，M覆蓋的頂點集合為EM。為了證明|U|=|V|-|M|，我們分兩步證明|U|<=|V|-|M|和|U|>=|V|-|M|1、 先證明 |U|<=|V|-|M|M中的兩個端點是連線的，所有M中必有一個點不在|U|集合中，所以|M|<=|V|-|U|2、 再證明|U|>=|V|-|M|假設(x,y)屬於M首先我們知道一定有|U|>=|V|-|EM|，那麼我們將M集合中的一個端點放入U中可以嗎？假設存在(a,x)，(b,y)，(a,b)不在EM集合中如果(a,b)連線，則有一個更大的匹配存在，矛盾如果(a,b)不連線，a->x->y->b有一個新的增廣路，因此有一個更大的匹配，矛盾所以我們可以瞭解到取M中的一個端點放入U中肯定不會和U中的任何一個點相連，所以|U|>=|V|-|EM|+|M|=|V|-|M|所以，|U|=|V|-|M|
附錄2二分圖的最小頂點覆蓋
定義：尋找一個點集，使得圖上任意一條邊至少一個端點位於這個點集內部。
求證：二分圖的|最小點集| = |最大匹配|
證明：按照定義所說，就是最大匹配中的每個匹配的一個結點就是最小點集。如果有一條邊的兩個端點都不在EM中，那最大匹配就會變成|M|+1，產生矛盾。所以又|最小點集|<=|最大匹配|我們現在只看最大匹配M，如果最小點集小於M，那麼肯定有邊無法涉及到，因此|最小點集|>=|最大匹配|所以有|最小點集|=|最大匹配|對於一個一般圖是NP Hard的問題，對於二分圖可能就是多項式可解的問題。
附錄3最小路徑覆蓋
定義：
一個有向無環圖，要求用盡量少的不相交的簡單路徑覆蓋所有的結點。
構圖：
建立一個二分圖，把原圖中的所有結點分成兩份（X集合為i，Y集合為i’），如果原來圖中有i->j的有向邊，則在二分圖中建立i->j’的有向邊。
求證：|最小路徑覆蓋| = |V| - |M|
證明：
圖4-1
圖4-1中，對應左邊的DAG構造了右邊的二分圖，可以找到二分圖的一個最大匹配M：1->3′ 3->4’，那麼M的這兩條匹配邊怎樣對應DAG中的路徑的邊呢？使二分圖的一條邊對應於DAG中的一條有向邊：1->3’對應於左圖的1->3，這樣DAG中的1就有一個後繼結點（3回事1的唯一後繼結點，因為二分圖中的一個頂點之多關聯一條邊！），所以1不會成為DAG中的一條路徑中的結尾頂點，同樣，3->4’對應於左圖的3->4，3也不會成為結尾頂點，那麼原圖中總共有4個頂點，減去2個有後繼的頂點，還有兩個頂點，即DAG路徑的結尾頂點，每個即為頂點對應一個路徑。二分圖中尋找最大匹配M，就是找到了對應DAG中的非路徑結尾頂點的最大數目，那麼DAG中|V|-|M|就是DAG中結尾頂點的最小數目，即DAG的最小路徑數目。