寻找最大独立集的算法-论文.pdf

《寻找最大独立集的算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第13卷第2期太原师范学院学报(自然科学版)Vo1．13No．22014年6月JOURNALOFTAIYUANNORMALUNIVERSITY(NaturalScienceEdition)Jun．2014寻找最大独立集的算法郭廷花(山西金融职业学院基础部，山西太原030008)[摘要]提出两种基于贪婪思想的局部搜索算法寻找给定图的最大独立集，通过测试第二种算法在图密度小时更优与第一种算法．由于局部搜索算法的缺陷，修改邻域函数与顶点的选择是进一步研究的问题；考虑到算法的有效性，时间复杂度和近似算法的比较也是值得进一步研

2、究的方向．[关键词]图密度；最大独立集；局部搜索；贪婪思想[文章编号]1672-2027(2014)02—0026～03(中图分类号]TP39(文献标识码]A1预备知识给定一个无向简单图G一(，E)，其中一(，z，⋯，}表示图G的顶点集，lVl一”，Ec_V×一{e，。，P。⋯，e}表示图G的边集，IEI—。d(v)表示图G中73的顶点度，即与关联的边数．一2m／n(～1)表示图的边密度．子集A，且它的顶点两两互不相邻，则称A是图G的一个独立集，图中基数最大的独立集称为该图的最大独立集，基数为图G的独立数，记为(G)

3、．最大独立集问题在信息检索、移动通信、图象显示、模式识别、电台信息传送等方面有广泛的应用．2算法的思路本文采用局部搜索算法，它是基于贪婪思想并利用邻域函数进行搜索的，搜索中采用递归的方法来寻找图的最大独立集．当图G是零图，即iEI一0，则图的最大独立集就是一{，72。，⋯，}，且a(G)一”；当图G是非零图，则需进一步讨论．第一步：基于贪婪思想在图中选择顶点度最大的顶点72；第二步：利用邻域函数对图进行分解，将图G分解成G一G一{72)，Gz—G一{72}一{N()}，其中N(73)表示73的邻集，即与邻接的顶点．第

4、三步：重复搜索，分别在图G和G中重复执行一、二步，直到所有子图中所有顶点的度为零．第四步：输出结果，在两个分支中得出的独立集进行基数比较，基数最大的为图G的最大独立集MIS．程序如下：递归算法寻找最大独立集Maxset(G)；Begin／toreturnthesizeofthelargestIndependentSetofG*

5、Ifdegree(G)==0thenMaxset==allverticesinGElseChooseaverticesv*inG：nl=Maxset(G～{v*})；n2一Maxset(G一{

6、v*}一N(v*))；Maxset=maximum—of(nl，n2)；End；下面用一例子说明算法的思路：收稿日期：2014-01-18作者简介：郭廷花(1979一)，女，山西忻州人，硕士，山西金融职业学院讲师，主要从事图论和数学建模方面研究第2期郭廷花：寻找最大独立集的算法27在图G中，V一{1，2，3，4，5，6)，E一{(1，2)，(1，6)，(2，3)，(2，5)，(3，4)，(4，5)，(5，6)}．寻找最大独立集的结构图如图1所示．图1寻找独立集结构图图l是在：f一6，一7／15—0．47规模的图上重复

7、执行了4次顶点的选择和图的分解．由于上述算法采用通过贪婪思想和邻域函数来缩小图的规模寻找最大独立集，这样对于图密度小的图来说图的规模并不能明显缩小，所以在上述算法的基础上把邻域函数做了修改，得出另一种思路：第一步：计算顶点度，找出顶点度最大的顶点；第二步：利用邻域函数～N()表示与不邻接的顶点，得出最初解；第三步：局部搜索，在G一{}的图中重复一、二步；第四步：修改最初解；直到所有顶点度为零结束．例如上题：在图G中d(。)一3，且是最大的，与它不关联的顶点是4和6，这样得出独立集的初解{2，4，6)；在去掉顶点。的图

8、中，顶点的度是2，与它不关联的点是1和6，产生{2，4，1，6)是矛盾解，所以当前独立集的解仍是{2，4，6}；在去掉顶点的图中，顶点的度是2，与它不关联的点是3，产生{2，3，4，6)是矛盾解，所以当前独立集的解仍然是{2，4，6)；在去掉顶点。的图中，图中d()一d()一d()一0，整个搜索过程结束，得出最大独立集MIS一{2，4，6}．3测试算法图的规模在顶点数Ivl一20到1VI一200，密度P在0．1～O．6的图上进行两种算法测试．当顶点数小于6O时，两种算法的时间基本相同．当顶点数大于6O，且图的密度≤0

9、．3时，第一种算法的时间快速增长，有时无法计算出结果，如表1中在P一0．1，填#的情况．而第二种算法明显优越第一种算法．从表1看到相同规模的图，第二种算法的运行时间为1．2S，第一种算法的运行时间为55858．5S，表1选取了顶点数为140，160，18O测试结果．4评价算法寻找最大独立集的算法一直在研究，分支定界算法、模拟退火算法、贪婪算法等