支配集

数学术语

支配集的定义如下：给定无向图G =（V , E），其中V是点集， E是边集，称V的一个子集S称为支配集当且仅当对于V-S中任何一个点v, 都有S中的某个点u, 使得(u, v) ∈E。

定义

支配集问题的两个变形。

定义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=的一个顶点子集，对于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转移方程为:

例题讲解

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

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

解决方法

1.贪心

2.DP