有关独立集的算法

关于独立集的问题有很多，比如地图填色问题、区域控制问题等。好多实际问题都可以抽象成独立集的问题，然后解决，比如对地图上的国家填充颜色，相邻的国家不能使用同一种颜色，这时就可以使用独立集求解。在上篇文章中《带权请求策略的几种算法》中，一种解法就使用了独立集的方法，下面我也会把具体的解法写出来。

问题描述

图G表示为，V为G的顶点集，E为G的边集，设顶点a属于独立集S，那么S中所有属于图G的顶点都没有边直接相连。

Figure 1.1 A independent set whose node colored gray in the graph

我们称上图中灰色节点为图的一个独立集。一般独立集的问题有求解图的独立集，求解图的最大独立集问题。

几种不同的独立集

一个图可以有多个独立集，每一个独立集都有一些特性，对他们归纳总结，我大致分一下几个类别：最大独立集、最小独立集、最多独立集、最少独立集、关联顶点独立集。

• 最大独立集，这种独立集最为常见，就是图G的独立集中包含顶点最多的那一个独立集。
• 最小独立集，顾名思意，相对于最大独立集来说，就是包含顶点最少的独立集，所以它没有研究意义，它包含的顶点数恒等于1
• 最少独立集，设S为包含图G独立集的集合，也就是说S的元素都是图G的独立集，且S中元素包含的顶点=图G的顶点集V，当S的容量最小时，我们称S为G的最少独立集。在Scheduling All Intervals（多资源请求安排策略，多个请求使用同一资源，但时间有交叉，求提供最少的资源满足这些请求。）问题上，可以使用最少独立集的理论来解决，而不是贪心算法。
• 最多独立集，相对于上面的最少独立集，它没有研究意义，最多独立集恒等于{{a},{b},……}
• 关联顶点最大独立集，即包含顶点A的关于图G的独立集，有时候为了获得包含某顶点的独立集，我们不得不求出图全部的独立集，这很浪费资源，因此更好的策略是直接求关于某点的独立集。

求解几种不同独立集的算法

1.最少独立集求解算法

从上一节我们知道了最少独立集的概念，怎么求解图G的最少独立集呢？本方法我叫做验证法，下面是伪代码：

//初始化最少集S，当前独立集s1
S={};s1={V[0]};
S.Append(s1);
//遍历顶点集V
for(i=1;i<V.length;i++){
    //如果当前顶点与前面所有的独立集有边
    if(V[i]与S中的顶点有边){
        //初始化一个新的独立集
        ns={};
        ns.Append(V[i]);
        S.Append(ns);
    }
    else{
        //遍历S中的所有独立集
        for(i=0;i<S.length;i++)
            if(S[i]中所有的顶点与V[i]都没有边)
                S[i].Append(V[i]);break;
    }
}

其实本算法很简单，先把第一个顶点A加入到第一个独立集s1中，然后依次遍历每一个顶点，如果当前顶点与集合s1中的顶点有边，就新建一个独立集s2，并把当前顶点加入s2中，照此规则，最终生成的几个独立集将是最少独立集的解。
例如，对于Figure 1.1算法的执行情况是：

• 第一步：    s1={A}, S={s1}
• 遍历B顶点：    s1={A}, s2={B}, S={s1,s2}
• 遍历C顶点：    s1={A}, s2={B,C}, S={s1,s2}
• 遍历D顶点：    s1={A,D}, s2={B,C}, S={s1,s2}
• 遍历E顶点：    s1={A,D}, s2={B,C}, s3={E} S={s1,s2,s3}
• 遍历F顶点：    s1={A,D,F}, s2={B,C}, s3={E} S={s1,s2,s3}
• 遍历G顶点：    s1={A,D,F}, s2={B,C,G}, s3={E} S={s1,s2,s3}
• 遍历H顶点：    s1={A,D,F}, s2={B,C,G}, s3={E}, s4={H} S={s1,s2,s3,s4}
• 遍历I顶点：    s1={A,D,F}, s2={B,C,G,I}, s3={E}, s4={H} S={s1,s2,s3,s4}

说到这里，我想大家都明白本算法是怎么回事了，非常简单不是吗？但是，这里有一个问题，就是通过这种算法形成的解中，会有一些独立集中顶点数量特别多，有些独立集的顶点数量又特别少，我称这种现象为“独立集失衡”，那么怎么生成一个较为“平衡”但又是最少的独立集呢？只需要做小小改进即可。

重新回到上面的算法，当一个顶点与当前解集S中没有边时，应该把该顶点加入S中的哪一个独立集中呢？s1,s2还是s3，这就是造就“独立集失衡”的罪魁祸首，上面的算法是始终从第一个独立集开始，如果当前顶点与该独立集没有边，就加入到该集中，也就是说，我们每一次都“关照”排名考前的独立集，好了，说到这里，解决“独立集失衡”问题的方法迎刃而解，我们增加一个计数器，记录最后添加顶点的独立集的索引，下一次向独立集添加顶点时从它的下家开始就OK了。下面是伪代码：

//初始化最少集S，当前独立集s1
S={};s1={V[0]};
S.Append(s1);
//失衡计数器
int count=0;
//遍历顶点集V
for(i=1;i<V.length;i++){
    //如果当前顶点与前面所有的独立集有边
    if(V[i]与S中的顶点有边){
        //初始化一个新的独立集
        ns={};
        ns.Append(V[i]);
        S.Append(ns);
    }
    else{
        //遍历S中的所有独立集
        for(i=0;i<S.length;i++){
            int index;
            if((count+i)>S.length)    index=i-count-1;
            else    index=i+count;
            if(S[index]中所有的顶点与V[i]都没有边){
                S[index].Append(V[i]);
                count++;
                break;
            }
        }
    }
}

以上算法的解为：s1={A,D,F}, s2={B,C,G}, s3={E,I}, s4={H}

2.关联顶点最大独立集求解算法

怎么求解包含某个顶点的最大独立集呢？我们当然可以用枚举法产生，因为我们是程序员，所以总会有更好的方法，就像万能的上帝，什么时候都不乏好的想法。

我们先思考一个最大的独立集所具有的特征，我们发现几乎所有的独立集中包含的顶点的“度”都不会太大。度，就是顶点的边数，对于有向图还有入度和出度的概念。假设，某个顶点的度很大，以至于它跟每一个顶点都有一条边，那么包含这个顶点的独立集绝对不会是最大独立集。基于这个想法，我们从顶点的度入手，运用贪心策略，我们每一步都尽量选择度数小的顶点作为最大独立集中的顶点。对于Figure 1.1中的图，它们的度为：

Figure 3.1 Degree of the graph

按照度数小优先的原则，我们可以生成一个包含某顶点的最大独立集。下面是伪代码：

//初始化独立集S和临时集
S={A};cur={};exploed={A}+f(A)
while(exploed!=V){
    //遍历S中“邻居”的“邻居”，即A外2层的节点，并加入cur集合中
    cur={x|x∈f(f(S))}    //f(x)函数表示与x集合中顶点有边的所有顶点
    exploed.Append(cur);
    //按照顶点的度对cur升序排序
    cur.Sort("ASC");
    //遍历cur中的顶点直到cur为空
    for(i=0;cur!=null;i++){
        S.Append(cur[i]);
        //删除cur中与cur[i]有边的顶点
        S.Delete(Disjoin(cur[i]));
    }
}

比如，我们求解包含A的最大独立集，下面是代码的执行过程：

• 第一步：    cur={},exploed={A} S={A}
• 第一次循环：    cur={F,G,H,D},exploed={A,F,G,H,D} S={A,F,H}
• 第二次循环：    cur={I},exploed={A,F,G,H,D,I} S={A,F,H,I}
• 终止：    exploed+f(A)=V    cur={},exploed={A,F,G,H,D,I} S={A,F,H,I}

在算法的执行过程中，临时集合cur是在不断变化的，本算法的执行效率与图的结构有关。我称这种算法为最小度优先加点法。对于大的图，它可能不会生成一个包含某顶点的最大独立集，但是可以近似的最大了，本算法的一些特性还有待研究，希望大家多不吝言辞。

最大独立集求解算法

在独立集的诸多问题中，最大独立集是最重要的也是最常用的一种独立集情形。怎么生成一个图的最大独立集呢？我这有三种算法，一种是网络上的算法，另外两种是我的见解。

1.最小覆盖集算法

图G(V,E)的覆盖集D是顶点集的一个子集,并满足:任意 <vi,vj>属于E,vi属于D或vj属于D  

定义 *，+ 满足交换率，结合率， 
且 *对+分配 (a+b)*c = a*c + b*c 
       
吸收率： 
a+ab = a 
a*a = a 
a+a = a 

这样，求极小覆盖集： 

 M(连乘)(  (v[i]  +  M(所有与v[i]相邻的点)   ) 
i=0 to n         

结果化简后的每个因子项即对应一个极小覆盖集。 

for example: 
a---b---c 
 \ / \ / 
  d   e 

(a+bd)(b+acde)(c+be)(d+ab)(e+bc) 
 = acde+abe+bcd+abc+bde   

acde,abe,bcd,abc,bde 既是G的各个极小覆盖集。 

因为极小覆盖集和极大独立集互补，用abcde 减去各个极小覆盖集， 
既得到极大独立集： 
b dc ae de ac  

其中dc ae de ac是最大独立集。 

2.动态规划法

动态规划算法的普适性很强，以至于什么问题我们都可以进行动态规划一下，但是对于某些问题，动态规划的效果却欠佳。
设P(x)为包含x的最大独立集，L(x)为x的相邻顶点。那么有：

P(x)=x+max(P(y))    y∈{V-x-L(x)}

有了上面的公式，算法便一目了然了。同样，这种方法还适用于关联顶点的独立集问题。它的效率实在太低了，所以大家就不要用了。

3.最大度优先减点法

在上面的关联顶点独立集的问题中我提到了一种算法，叫最小度优先加点法，原理是一样的，对于求最大独立集的问题，我们首先找到度数最大的顶点，然后删除它，直到生成一个独立集，那么得到的就是最大独立集了。对于Figure 1.1中的示例，它的过程为：

• 第一步：删除E
• 第二步：删除D
• 第三步：最后剩下了“环”，删掉A,F,H

在算法执行的最后，会剩下“环”或是“链”状的图，这时就有可能生成多个最大独立集了。

独立集法求解带权请求策略

在上一篇文章中，我提到了使用独立集的方案，在这里就稍作阐述。问题如下图：

Figure 4.1 An instance of weighted interval scheduling with longest path

首先，我们用请求的权值作为图的点，如果请求a,b冲突，就做边ab，于是得到图:

Figure 4.2 General a graph from the interval

得到了图，下一步就是应用我们的“最大度优先减点法”了，首先删除点E，然后是B，最后得到一个偶数链，删除链中的G以得到最大的权数。最终得到A,C,D,F请求，对应图中的：

Figure 4.3 Result we get from idependent set

实际上，独立集法求解带权请求策略所使用的独立集策略为：最大权重独立集算法，而不是最大独立集算法，所以本处产生的结果不是带权请求的最优结果。关于最大权重独立集算法以后可能会涉及到。

总结

独立集的应用非常广，同时它也非常高效，有时候并不是所有的问题都适合用动态规划等方法，恰当的运用图的理论可以大大提高系统的效率。希望大家检验上面的算法，不吝言辞多提意见。

作者：Creason New(Creason's Blog)
出处： http://www.cnblogs.com/niuchenglei
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。