有关独立集的算法

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

问题描述

图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
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。