> 
> http://acm.scu.edu.cn/soj/problem.action?id=2294
> 
> SCU上的这一题就是求一无向图的最大独立子集.
> 在网上搜了下,知道了最大全完图与最大独立子集问题是等价的,而且好像都是NP问题.
> 找到一求最大独立子集的算法,如下,可是自己按那算法写的个程序,却一直超时.实在不知道该怎么优化.
> 
> 请教个位牛人,不知还有什么更好的方法?或者如何实现这个算法时间消耗会比较少?
> 
> 
> 如何求图的最大独立集
> 具体程序实现可以通过求最小覆盖集来求最大独立集。 
> 图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是最大独立集
> 算了一下，发现根据式子直接运算就可以得到最简答案，不需要什么技巧。  
> 比如初始化为  a  +  bd。  
> 然后用  b  +  acde分别和上面的式子相乘，相乘时注意运用  a*a=a（可以用集合来实现），相加时注意运用  a+a=a和a+ab=a（如果其它项是该项的子集则取消该项)，一直下去就能得出最终结果了。