基本介紹
- 中文名：支配集
- 外文名：dominating set
- 屬性：集合
定義,原理,最小支配集,解法,貪心策略,樹形DP求樹,例題講解,
定義
支配集問題的兩個變形。
定義1 在圖G=〈V , E〉中,V 的一個子集S 稱為C 強支配集( C 是某個固定的常正整數) 若且唯若對任何一個大小不小於| S| - C 的S 的一個子集S′,對於V - S 中任何一個頂點v ,都有S′中的某個定點u ,使得( u , v) ∈E。
定義2 在圖G=〈V , E〉中,V 的一個子集S 稱為完全支配集若且唯若對於V 中任何一個點v ,都有S - { v} 的某個點u ,使得( u , v) ∈E。
原理
D是圖G=<V,E>的一個頂點子集，對於G的任一頂點v，要么v屬於D，要么與D中的一個頂點相鄰，則D稱為圖G的一個支配集。若在D集中去掉任何元素後D不再是支配集，則稱D是極小支配集。稱圖G的所有支配集中頂點個數最少的支配集為最小支配集，最小支配集中的頂點個數稱為圖G的支配數。
如何求G的所有極小支配集合？
對符號X,Y,Z，定義兩種運算X+Y（加法運算，或運算）和XY（乘法運算，與運算），滿足以下運算定律：
交換律：X+Y = Y+X; XY = YX
結合律：(X+Y)+Z = X+(Y+Z); (XY)Z = X(YZ)
分配律：X(Y+Z) = XY+XZ
吸收律：X+X = X; XX = X; X+XY = X
求所有極小支配集的公式：
一個頂點與它相鄰的所有頂點進行加法運算組成一個因子項，n個因子項再相乘。連乘過程中根據上述運算規律展開成積之和的形式。每一積項給出一個極小支配集。
(1 + 2 + 3 + 4)(2 + 1 + 4)(3 + 1 + 4)(4 + 1 + 2 + 3 + 5 + 6)(5 + 4 + 6)(6 + 4 + 5)
=15 + 16 + 4 + 235 + 236
故極小支配集為
{V1, V5}, {V1, V6}, {V4}, {V2, V3, V5}, {V2, V3, V6}
最小支配集
對於圖G = (V, E) 來說,最小支配集指的是從 V 中取儘量少的點組成一個集合, 使得 V 中剩餘的點都與取出來的點有邊相連.也就是說,設 V' 是圖的一個支配集,則對於圖中的任意一個頂點 u ,要么屬於集合 V', 要么與 V' 中的頂點相鄰. 在 V' 中除去任何元素後 V' 不再是支配集, 則支配集 V' 是極小支配集.稱G 的所有支配集中頂點個數最少的支配集為最小支配集,最小支配集中的頂點個數稱為支配數.
解法
貪心策略
首先選擇一點為樹根,再按照深度優先遍歷得到遍歷序列,按照所得序列的反向序列的順序進行貪心,對於一個即不屬於支配集也不與支配集中的點相連的點來說,如果他的父節點不屬於支配集,將其父節點加入到支配集
樹形DP求樹
考慮最小支配集,每個點有兩種狀態,即屬於支配集合或者不屬於支配集合,其中不屬於支配集合時此點還需要被覆蓋,被覆蓋也有兩種狀態,即被子節點覆蓋或者被父節點覆蓋.總結起來就是三種狀態,現對這三種狀態定義如下: 1):dp[i][0],表示點 i 屬於支配集合,並且以點 i 為根的子樹都被覆蓋了的情況下支配集中所包含最少點的個數. 2):dp[i][1],表示點 i 不屬於支配集合,且以 i 為根的子樹都被覆蓋,且 i 被其中不少於一個子節點覆蓋的情況下支配集所包含最少點的個數.
3):dp[i][2],表示點 i 不屬於支配集合,且以 i 為根的子樹都被覆蓋,且 i 沒被子節點覆蓋的情況下支配集中所包含最少點的個數.即 i 將被父節點覆蓋
對於第一種狀態,dp[i][0]含義為點 i 屬於支配集合,那么依次取每個兒子節點三種狀態中的最小值,再把取得的最小值全部加起來再加 1,就是dp[i][0]的值了.即只要每個以 i 的兒子為根的子樹都被覆蓋,再加上當前點 i,所需要的最少的點的個數,DP轉移方程如下:
dp[i][0] = 1 + ∑(u 取 i 的子節點)min(dp[u][0], dp[u][1], dp[u][2])
對於第三種狀態,dp[i][2]含義為點 i 不屬於支配集合,且 i 被其父節點覆蓋.那么說明點 i 和點 i 的兒子節點都不屬於支配集合,所以點 i 的第三種狀態之和其兒子節點的第二種狀態有關,方程為:
dp[i][2] =∑(u 取 i 的子節點)dp[u][1]
對於第二種狀態,略有些複雜.首先如果點 i 沒有子節點那么 dp[i][1]應該初始化為 INF;否則為了保證它的每個以 i 的兒子為根的子樹被覆蓋,那么要取每個兒子節點的前兩種狀態的最小值之和,因為此時點 i 不屬於支配集,不能支配其子節點,所以子節點必須已經被支配,與子節點的第三種狀態無關.如果當前所選狀態中每個兒子都沒被選擇進入支配集,即在每個兒子的前兩種狀態中,第一種狀態都不是所需點最小的,那么為了滿足第二種狀態的定義(因為點 i 的第二種狀態必須被其子節點覆蓋,即其子節點必須有一個屬於支配集,如果此時沒有,就必須強制使一個子節點的狀態為狀態一),需要重新選擇點 i 的一個兒子節點為第一種狀態,這時取花費最少的一個點,即取min(dp[u][0] - dp[u][1])的兒子節點 u,強制取其第一種狀態,其他的兒子節點取第二種狀態,DP轉移方程為:
對於第二種狀態,略有些複雜.首先如果點 i 沒有子節點那么 dp[i][1]應該初始化為 INF;否則為了保證它的每個以 i 的兒子為根的子樹被覆蓋,那么要取每個兒子節點的前兩種狀態的最小值之和,因為此時點 i 不屬於支配集,不能支配其子節點,所以子節點必須已經被支配,與子節點的第三種狀態無關.如果當前所選狀態中每個兒子都沒被選擇進入支配集,即在每個兒子的前兩種狀態中,第一種狀態都不是所需點最小的,那么為了滿足第二種狀態的定義(因為點 i 的第二種狀態必須被其子節點覆蓋,即其子節點必須有一個屬於支配集,如果此時沒有,就必須強制使一個子節點的狀態為狀態一),需要重新選擇點 i 的一個兒子節點為第一種狀態,這時取花費最少的一個點,即取min(dp[u][0] - dp[u][1])的兒子節點 u,強制取其第一種狀態,其他的兒子節點取第二種狀態,DP轉移方程為:
if(i 沒有子節點) dp[i][1] = INFelse dp[i][1] = ∑(u 取 i 的子節點)min(dp[u][0], dp[u][1]) + inc其中對於 inc 有:if(上面式子中的 ∑(u 取 i 的子節點)min(dp[u][0], dp[u][1]) 中包含某個 dp[u][0], 即存在一個所選的最小值為狀態一的兒子節點) inc = 0else inc = min(dp[u][0] - dp[u][1]) (其中 u 取點 i 的兒子節點)
例題講解
POJ—3659—Cell Phone Network
Description
Farmer 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.
Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B 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: A and B
* Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B
Output
* Line 1: A single integer indicating the minimum number of towers to install
Sample Input
5 1 3 5 2 4 3 3 5
Sample Output
2
解決方法
1.貪心
#include<iostream> #include<cstdlib> #include<cstdio> #include<vector> using namespace std; const int MAXN=10010; struct node { int to; int next; } edge[MAXN*2]; int head[MAXN*2],num; int dfn[MAXN]; vector<int> son[MAXN];//記錄自己的兒子編號範圍末端 int fat[MAXN];//記錄自己的父親 int color[MAXN];//是否與支配集相鄰 int flag[MAXN];//是否屬於支配集 int n,cnt; int ans; void add(int x,int y) { edge[++num].next=head[x]; edge[num].to=y; head[x]=num; } void Tarjan(int k) { dfn[k]=++cnt; int x; for(int i=head[k]; i ; i=edge[i].next ) { x=edge[i].to; if( !dfn[x] ) { son[k].push_back(x); Tarjan( x ); fat[ dfn[x] ]=k; } } return ; } void dp( ) { int x,y; for(int i=n; i>=1; i--) { if( color[i] || flag[i] ) continue ; x=fat[i]; if( flag[ dfn[ x ] ] ) continue ; if( x==0 ) if( !flag[1] && !color[1] ) { ans++; break; } flag[ dfn[ x ] ]=1; color[ dfn[ x ] ]=1; color[ dfn[ fat[ dfn[x] ] ] ]=1; y=son[x].size(); for(int j=0; j<=y-1; j++) color[ dfn[ son[x][j] ] ]=1; ans++; } return ; } int main() { int u,v; scanf("%d",&n); for(int i=1; i<=n-1; i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } fat[1]=0; Tarjan( 1 ); dp( ); printf("%d",ans); return 0; }2.DP
#include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> using namespace std; const int MAXN=10010; const int INF=int(1e7); struct node { int to; int next; } edge[MAXN*2]; int head[MAXN*2],num; int dp[MAXN][3]; /* 1):dp[i][0],表示點 i 屬於支配集合,並且以點 i 為根的子樹都被覆蓋了的情況下支配集中所包含最少點的個數. 2):dp[i][1],表示點 i 不屬於支配集合,且以 i 為根的子樹都被覆蓋,且 i 被其中不少於一個子節點覆蓋的情況下支配集所包含最少點的個數. 3):dp[i][2],表示點 i 不屬於支配集合,且以 i 為根的子樹都被覆蓋,且 i 沒被子節點覆蓋的情況下支配集中所包含最少點的個數.即 i 將被父節點覆蓋. */ int n; void add(int x,int y) { edge[++num].next=head[x]; edge[num].to=y; head[x]=num; } void DP( int k,int fat ) { dp[ k ][ 0 ]=1; dp[ k ][ 2 ]=0; bool s=0; int x,sum=0,inc=INF; for(int i=head[ k ]; i ;i=edge[i].next ) { x=edge[i].to; if( x==fat ) continue ; DP( x,k ); dp[ k ][ 0 ]+=min(dp[ x ][ 0 ],min(dp[ x ][ 1 ],dp[ x ][ 2 ])); if( dp[ x ][ 0 ] <= dp[ x ][ 1 ] ) { sum+=dp[ x ][ 0 ]; s=1; } else { sum+=dp[ x ][ 1 ]; inc=min(inc,dp[ x ][ 0 ]-dp[ x ][ 1 ]); } if( dp[ x ][ 1 ]!=INF && dp[ k ][ 2 ]!=INF ) //x不是葉子節點，而且k有父親，即k不是根 dp[ k ][ 2 ]+=dp[ x ][ 1 ]; else dp[ k ][ 2 ]=INF; } if( inc==INF && !s )//k沒有子節點 dp[ k ][ 1 ]=INF; else { dp[ k ][ 1 ]=sum; if( !s )//如果不為零，則k的子節點中有一個已經染色 dp[ k ][ 1 ]+=inc; } return ; } int main() { int u,v; scanf("%d",&n); for(int i=1; i<=n-1; i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } DP( 1,0 ); int ans=min(dp[1][0],dp[1][1]); printf("%d\n",ans); return 0; }