一、定义

设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的最小路径数目。