支配集是指在一個無向圖G=(V,E)中，V的子集S被稱為支配集，當(dāng)且僅當(dāng)對于V-S中的每一個點v，都有S中的某個點u，使得(u,v)∈E。特別地，最小的支配集S（即任意一個小于S的集合都不能成為支配集）被稱為最小支配集。
定義
支配集問題有兩個變體。第一個變體是在圖G=〈V , E〉中，V的一個子集S被稱為C強(qiáng)支配集(C是一個固定的正整數(shù))，當(dāng)且僅當(dāng)對于任何一個大小大于等于|S|-C的S的子集S'，對于V-S中的任何一個頂點v，都有S'中的某個頂點u，使得(u,v)∈E。第二個變體是在圖G=〈V , E〉中，V的一個子集S被稱為完全支配集，當(dāng)且僅當(dāng)對于V中的任何一個點v，都有S-{v}中的某個點u，使得(u,v)∈E。
原理
支配集D是圖G=
最小支配集
對于圖G=(V,E)來說，最小支配集指的是從V中取盡可能少的點組成一個集合，使得V中剩余的點都與取出來的點有邊相連。也就是說，設(shè)V'是圖的一個支配集，則對于圖中的任意一個頂點u，要么屬于集合V'，要么與V'中的頂點相鄰。在V'中除去任何元素后V'不再是支配集，則支配集V'是極小支配集。稱G的所有支配集中頂點個數(shù)最少的支配集為最小支配集，最小支配集中的頂點個數(shù)稱為支配數(shù)。
解法
貪心策略
首先選擇一點為樹根，再按照深度優(yōu)先遍歷得到遍歷序列，按照所得序列的反向序列的順序進(jìn)行貪心，對于一個既不屬于支配集也不與支配集中的點相連的點來說，如果他的父節(jié)點不屬于支配集，將其父節(jié)點加入到支配集。
樹形DP求樹
考慮最小支配集，每個點有兩種狀態(tài)，即屬于支配集合或者不屬于支配集合，其中不屬于支配集合時此點還需要被覆蓋，被覆蓋也有兩種狀態(tài)，即被子節(jié)點覆蓋或者被父節(jié)點覆蓋。總結(jié)起來就是三種狀態(tài)，現(xiàn)對這三種狀態(tài)定義如下:1):dp[i],表示點i屬于支配集合，并且以點i為根的子樹都被覆蓋了的情況下支配集中所包含最少點的個數(shù).2):dp[i],表示點i不屬于支配集合，且以i為根的子樹都被覆蓋，且i被其中不少于一個子節(jié)點覆蓋的情況下支配集所包含最少點的個數(shù).3):dp[i],表示點i不屬于支配集合，且以i為根的子樹都被覆蓋，且i沒被子節(jié)點覆蓋的情況下支配集中所包含最少點的個數(shù)。即i將被父節(jié)點覆蓋對于第一種狀態(tài),dp[i]含義為點i屬于支配集合，那么依次取每個兒子節(jié)點三種狀態(tài)中的最小值，再把取得的最小值全部加起來再加1,就是dp[i]的值了。即只要每個以i的兒子為根的子樹都被覆蓋，再加上當(dāng)前點i,所需要的最少的點的個數(shù),DP轉(zhuǎn)移方程如下:dp[i]=1+∑(u取i的子節(jié)點)min(dp[u],dp[u],dp[u])對于第三種狀態(tài),dp[i]含義為點i不屬于支配集合，且i被其父節(jié)點覆蓋。那么說明點i和點i的兒子節(jié)點都不屬于支配集合，所以點i的第三種狀態(tài)之和其兒子節(jié)點的第二種狀態(tài)有關(guān)，方程為:dp[i]=∑(u取i的子節(jié)點)dp[u]對于第二種狀態(tài)，略有些復(fù)雜。首先如果點i沒有子節(jié)點那么dp[i]應(yīng)該初始化為INF;否則為了保證它的每個以i的兒子為根的子樹被覆蓋，那么要取每個兒子節(jié)點的前兩種狀態(tài)的最小值之和，因為此時點i不屬于支配集，不能支配其子節(jié)點，所以子節(jié)點必須已經(jīng)被支配，與子節(jié)點的第三種狀態(tài)無關(guān)。如果當(dāng)前所選狀態(tài)中每個兒子都沒被選擇進(jìn)入支配集，即在每個兒子的前兩種狀態(tài)中，第一種狀態(tài)都不是所需點最小的，那么為了滿足第二種狀態(tài)的定義(因為點i的第二種狀態(tài)必須被其子節(jié)點覆蓋，即其子節(jié)點必須有一個屬于支配集，如果此時沒有，就必須強(qiáng)制使一個子節(jié)點的狀態(tài)為狀態(tài)一),需要重新選擇點i的一個兒子節(jié)點為第一種狀態(tài)，這時取花費最少的一個點，即取min(dp[u]-dp[u])的兒子節(jié)點u,強(qiáng)制取其第一種狀態(tài)，其他的兒子節(jié)點取第二種狀態(tài),DP轉(zhuǎn)移方程為:
例題講解
POJ—3659—Cell Phone NetworkDescriptionFarmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1≤N≤10,000) pastures (conveniently numbered 1..N) so they can all communicate.ExactlyN-1 pairs of pastures are adjacent, and for any two pasturesA andB (1≤A≤N; 1≤B≤N;A≠B) there is a sequence of adjacent pastures such thatA is the first pasture in the sequence andB is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.Input* Line 1: A single integer:N* Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers:AandBOutput* Line 1: A single integer indicating the minimum number of towers to installSample Input5 1 3 5 2 4 3 3 5Sample Output2解決方法1.貪心2.DP
參考資料 >
任意圖支配集精確算法回顧.百度學(xué)術(shù)搜索.2024-11-01
Efficient Broadcast in Mobile Ad Hoc Networks Using Connected Dominating Sets移動自組網(wǎng)絡(luò)中采用連通支配集的有效廣播技術(shù).百度學(xué)術(shù)搜索.2024-11-01
分布式算法.百度學(xué)術(shù)搜索.2024-11-01