（应用数学专业论文）图的邻集分解与最大团问题的研究.pdf

太原理工大学硕士研究生学位论文 图的邻集分解与最大团问题的研究 摘要 最大团问题( m a x i m u mc l i q u ep r o b l e m ，m c p ) 是图论中经典的组合优 化问题。本文综述了国内外学者对此问题的研究成果，包括该问题的应用 背景，界的估计，及各种算法的研究。 本文首先对最大团的界进行了论述，并提出了一个新的上界。其次详 细探讨了图的邻集分解与最大团。图的分解不仅使问题的规模缩小( 其中 参数的选择和平均度的应用使得规模再次缩小) ，同时此方法不会陷入局部 最优。 本文最后基于图的邻集分解及不同排序策略提出了一种新的精确算法 一截支定界法。该算法吸取了分支定界法的优点，先用下界把图中对 求解最大团没价值的点删去，再应用图的邻集分解方法对给出的随机图进 行分解，使求解最大团的搜索规模大大收缩，从而加快了算法的收敛速度， 最后再对团进行搜索。其中在团的搜索阶段对不同类型的图采取不同的搜 索策略。对边密度较大的图由于最大团中包含最大度顶点的概率比较大， 所以采取贪婪搜索策略；对边密度较小的图由于最大团中包含最小度顶点 的概率比较大，所以采取非贪婪的搜索策略；对中等密度的图由于最大团 接近平均度顶点的概率比较大，所以采取由导师提出的基于平均度的搜索 策略。实算表明，这样做有助于加快搜索速度。该算法在随机图上进行了 测试，取得了良好的效果。 太原理工大学硕士研究生学位论文 在研究n p c 问题时，如何对图g 进行合理有效的分解是值得重视的。 这是本文研究的初衷，也是值得进一步研究的重点。 关键词：最大团，分解，界，截支定界法，搜索 太原理工大学硕士研究生学位论文 t 皿d i v i s i o no fa d j a c e n tv e r t i c e ss e t o fg r a p ha n ds t u d yo nm a x i m u m c l i q u e p r o b l e m a b s t r a c t t h em a x i m u m c l i q u ep r o b l e m ( m c p ) i sac l a s s i c a lp r o b l e mi n c o m b i n a t o r i a lo p t i m i z a t i o n t h i st h e s i ss u m m a r i z e st h er e l a t e d p r e v i o u ss t u d i e s i n c l u d i n gi t sa p p l i c a t i o n ，e s t i m a t i o no fb o u n d s ，a n dr e s e a r c h e so nv a r i o u s a l g o r i t h m s t h et h e s i se l a b o r a t e st h eb o u n do fm c pa n dg e t sag o o du p p e rb o u n da t f i r s t ，t h e nf o c u s e st h ed i v i s i o no fa d j a c e n tv e r t i c e ss e ta n dm c pi nd e t a i l t h e d i v i s i o no fa d j a c e n tv e a i c e ss e tr e d u c e st h ed o m a i no f p r o b l e m ( t h es e l e c t i o no f p a r a m e t e ra n da p p l i c a t i o no fa v e r a g ed e g r e er e d u c et h ed o m a i na g a i n ) ，w h i l ei t i s n ti no p t i m i z a t i o nl o c a l l y b a s e do nt h ed i v i s i o no fa d j a c e n tv e r t i c e ss e ta n dd i f f e r e n t s e q u e n c e t e c h n i q u e ，i tp r o p o s e san e wa l g o r i t h m ：c u tb r a n c ha n db o u n d t h i sm e t h o dh a s s t r o n gp o i n t so ft h eb r a n c ha n db o u n d ：i td e l e t e st h eu n v a l u e dp o i n ti np r o c e s s o fs e a r c h i n gm c p , d e c o m p o s e sr a n d o mg r a p hw i t ht h et h e o r yo fd i v i s i o no f a d j a c e n tv e r t i c e ss e t ，w h i c hr e d u c e st h ed o m a i no nm c p ss o l u t i o na n dq u i c k e n t h e c o n v e r g e n c e o ft h i s a l g o r i t h m s ，s e a r c h e st h ec l i q u ef m a l l y d i f f e r e n t i i i 太原理工大学硕士研究生学位论文 t e c h n i q u e sa r ea p p l i e dt od i f f e r e n tg r a p h so nm c p s e a r c h i n g ：f o rd e n s eg r a p h m c p , g r e e d ys e a r c hi st h eb e s t , b e c a u s eo fh i g hp r o b a b i l i t ya tt h em a x i m u m d e g r e ev e r t e x ；f o rs p a r s eg r a p hm c p , n o n - g r e e d ys e a r c hi st h eb e s t ，b e c a u s eo f h i g hp r o b a b i l i t ya tt h em i n i m u md e g r e ev e r t e x ；f o rm e d i u mg r a p hm c p , w i t h r e g a r d t o h i g hp r o b a b i l i t ya tt h ea v e r a g ev e r t e x ，a v e r a g ed e g r e es e a r c h ， p r o p o s e du n d e rm yt u t o r sg u i d a n c e ，i st h eb e s t ，w h i c hq u i c k e n su ps e a r c h i n g s p e e d h a v i n ga p p l i e dt or a n d o mg r a p h ，f i n er e s u l t sh a v eb e e na c h i e v e d i ti sw o r t hm u c ha t t e n t i o no nh o wt o d e c o m p o s ege f f e c t i v e l yw h i l e s t u d y i n gt h ep r o b l e mo fn p - c i ti sj u s tm yo r i g i n a li n t e n t i o na n de m p h a s i si n t h ef u r t h e rr e s e a r c h k e yw o r d s ：m a x i m u mc l i q u ep r o b l e m ，d i v i s i o n ，b o u n d ，c u tb r a n c ha n d b o u n d ，s e a r c h i v 声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名： 王龋红 日期：q z ! 丞三 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为目的。 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) o 签名：王勉日期：殳21 ： 导师签名： 太原理工大学硕士研究生学位论文 第一章绪论 1 1 最大团问题及其实际意义 给定一个无向简单图g = ( y ，d ，其中v = v ，p 2 ，k 为图g 的顶点集，e 呈v x v 表示图g 的边集。图g = ( 矿，e ) 的补图记为否= ( v ，面) ，其中 云= 静，j ) l f ，v ，i s - ，( f ，) 诺e ) 。 图g 中的一个团c 指顶点集v 的一个子集，其顶点在g 中两两相互邻接。如果一 个团不是其它任何团的真子集，则称该团为图g 的极大团。基数最大的团称为图中的最 大团，其基数称为图g 的团数，记为o ( g ) 。最大团问题( t h e m a x i m u m c l i q u ep r o b l e m ， m c p ) 就是在给定的图中寻找基数最大的团。所谓最大加权团问题( t h e m a x i m u m w e i g h t e d c 1 i q u ep r o b l e m , m w c p ) ，是在图中寻找权和最大的团。显然，最大团问题可以看作最 大加权团问题的特例。本文主要讨论最大团问题。 称v 的一个子集a 互v 为独立集，若它的顶点两两互不相邻。图中基数最大的独立 集称为该图的最大独立集，其基数为图g 的独立数，记为口( g ) 。最大独立集问题( t h e m a x i m u mi n d e p e n d e n ts e tp r o b l e m ，m i s p ) 就是在给定的图中寻找基数最大的独立集。 所谓最大加权独立集问题( t h em a x i m u mw e i g h t e di n d e p e n d e n ts e tp r o b l e m , 唧i s p ) ， 就是在图中寻找权和最大的独立集。 图g 的顶点集v 的一个子集称为顶点覆盖，若图g 的每条边o ，歹) e 都至少有一 个端点在这个子集中。图中基数最小的顶点覆盖称为图g 的最小顶点覆盖。其基数称 为图g 的覆盖数，记为( g ) 。最小顶点覆盖问题( t h em i n i m u mv e r t e xc o v e r p r o b l e m , b i v c p ) 就是要在给定的图中寻找基数最小的顶点覆盖。同理，最小加权顶点覆盖问题( t h e m i n i m u mw e i g h t e dv e r t e xc o v e rp r o b l e m ，m w v c p ) 就是在图g 中寻找权和最小的顶点 覆盖。 太原理工大学硕士研究生学位论文 显然，c 是图g 的团当且仅当c 是其补图8 的独立集，或者叭c 是其补图否的一 个顶点覆盖。即，a ( o ) = ( g ) ，口( g ) + ( g ) = 厅。 理论上，最大团问题很早就被证明为n p 一完全问题之一【2 l ，由于它是“指数爆炸” 特征的计算难题，可在多项式时间内归约为许多知名的难题，如最大独立集闯题 1 ) 。选择邻集时，费用值大的将被选 中，因此求解最大独立集也就是最大化费用函数的过程。 j e r r u m ! 州在随机图上，对模拟退火算法在m e t r o p o l i s 过程( 模拟退火在固定温度 时) 能找到的解效果进行了理论分析。他证明了在期望的时间内，模拟退火算法所需要 的时间比简单的贪婪启发式算法要多。并且，随着顶点个数的增加，所需要的时间增长 速度比任何多项式都要大，因此，他认为模拟退火算法不适合解决最大团问题。 但是，j e r r u m 的结论与实际结果相违背，h o m e r 和p e i n a d o 4 5 把模拟退火算法和 三种启发式算法及j o h n s o n 的贪婪启发式算法、b o p p a n 的随机化( r a n d o m i z e d ) 算法、 h a l l d o r s s o n 的子图排除法( s u b g r a p h e x c l u s i o n ) 进行比较，结果证明比这三种算法好 很多。总之，模拟退火算法在处理最大团问题上是一类非常好的算法。 3 3 3 神经网络( n e u r a in e t w o r k s ) 方法在最大团问题中的应用 人工神经网络就是指为了模拟生物大脑的结构和功能而构成的一种大型的、分布式 系统，它有很强的自组织性、自适应性和学习能力。神经网络由多个非常简单的 处理单元彼此按某种方式相互连接而形成的计算机系统，该系统是靠其状态对外部输入 信息的动态响应来处理信息的。人工神经网络是由人工建立的以有向图为拓扑结构的动 1 3 太原理工大学硕士研究生学位论文 态系统，它通过对连续或断续的输入作状态来相应地进行信息处理。 在上世纪八十年代中期，h o p f i e l d 和t a n k 4 8 1 认为反馈连续的神经网络模型能够有 效地解决难度比较高的组合优化问题，它成功地解决了旅行商问题( t s p ) 等问题，自此， 这个模型被用来解决大量的其他组合优化问题。这种常用的方法通过把客观问题公式化 为能量最小化函数，然后，通过选用适当的松弛网络( r e l a x a t i o nn e t w o r k ) 来最小化 这个函数。这就是用神经网络解决组合优化问题的总体思路。 上世纪八十年代末期，b a l l a r de ta 1 1 2 1 1 ，g o d b e e re ta 1 1 4 9 ，r a m a n u ja m 和 s a d a y a p p a n | 圳等都尝试对最大团和相关问题按人工神经网络进行编码，进而求解该问 题。然而，这些研究只提供了很少的实验结果，有的甚至没有提供实验结果，因此，对 他们的工作很难进行评价。 g r o s s m a n ”1 提出一种离散的，确定性的h o p f i e d 模型来求解最大团问题，这个模 型包含一个用来决定网络是否处于稳定态的临界值参数。g r o s s m a n 建议在这个参数上 使用退火策略，并且使用自适应机制来选则网络的初始状态和临界值。在d i s c s 基准 图上测试，它得到的结果还是比较好的，但是比性能好的启发式算法的结果差，比如比 模拟退火算法就要差。 在1 9 9 5 年j a g o t a | ”1 对h o p f i e l d 模型进行了多处修改来近似求解最大团问题，不 过该模型仍然是离散和不连续的。实验结果表明使用随机急剧下降动态法( s t o c h a s t i c s t e e p e s td e s c e n td y n a m i c s ) 和平均场退火算法( m e a n f i e l da n n e a l i n ga l g o r i t h m ) 得到的结果最好，但是这些算法的速度特别慢。因此j a g o t ae ta l 通过对算法进一步 修改来缩短运行时间。他在平均场退火算法中运用两极温度退火( t w o - t e m p e r a t u r e a n n e a l i n g ) 策略，在随机急剧下降动态法中利用强化学习( r e i n f o r c e m e n tl e a r n i n g ) 策略自动调整内部参数。这样与其它简单的启发式算法相比，他们的算法能够找到更大 的团，但时问稍微长一些，与复杂的启发式算法相比，他们的算法找到的团较小，但速 度特别快i ”j 。 随后，仍然有好多研究者使用h o p f i e l d 神经网络来求解最大团问题，但是效果都 不是很好。 1 4 太原理工大学硕士研究生学位论文 3 3 4 遗传算法在最大团问题中的应用 遗传算法是一种基于自然选择和群体遗传机理的搜索算法，它模拟了自然选择和 自然遗传过程中发生的复制、交叉和变异现象。在利用遗传算法求解问题时，问题的每 个可能的解都被编码成一个“染色体”，即个体解，若干个个体构成了群体( 所有可能解) 。 在遗传算法开始时，总是随机地产生一些个体( 即初始解) ，根据预定的目标函数对每个 个体进行评价，给出一个适应值。基于此适应值，选择个体用来复制下一代。选择操作 体现了“适者生存”原理，“好”的个体被选择用来复制，而“坏”的个体则被淘汰。 然后选择出来的个体经过交叉和变异算子进行再组合，生成新的一代。这一群新个体由 于继承了上一代的一些优良性状，因而在性能上要优于上一代，这样逐步朝着更优解的 方向进化。因此，遗传算法可以看作是一个可行解组成的群体逐代进化的过程。 c a r t e ：和p a r k ”1 ( 1 9 9 3 年) 是最早使用遗传算法来求解最大团问题的两名研究者， 通过他们的初始研究，认为简单遗传算法( s i m p l eg e n e t i ca l g o r i t h m ，简称s g a ) 在解 决大的团( 1 a r g ec l i q u e ) 时表现非常差，即使是处理简单的随机图，效果也不好。为了 能够提高解的质量他们对算法进行了几处调整，然而并没有达到预期的效果。于是，他 们得出了结论：为了能与传统的方法在效果上有比较性，需要做非常大的改动，而且它 的计算量太大。后来他们证明了g a 远不如模拟退火算法( s i m u l a t e da n n e a l i n g ，简称 s a ) 有效。但与此同时，b a c k 和k h u r i 5 4 致力于最大独立集问题的求解，却得到了完 全相反的结论。他们运用直观的多目标遗传算法( s t r a i g h t f o r w a r d ，g e n e r a l p u r p o s e g e n e t i ca l g o r i t h m ) 和一个适当的适应度函数( f i t n e s sf u n c t i o n ) ，这个函数含有对 不可行解的惩罚项，得到了很好的结果，无论是解决随机图还是常规图，并且顶点数可 达到2 0 0 。这就说明在使用g a 来解决最大团问题时，能否选择一个合适的适应度函数 起着非常关键的作用。 1 9 9 5 年，b u i 和e p p l e y ! 圳运用混合策略( h y b r i ds t r a t e g y ) ，该策略在遗传算法中 每一代都结合局部优化算法( 1 0 c a lo p t m i z a t i o n ) 和顶点排序预处理过程 ( v e r t e x o r d e r i n gp r e p o c e s s i n gp h a s e ) ：他们在d i m a c s 基准图上测试该算法，得到了 比较好的结果。 f l e u r e n t 和f e r l a n d 在1 9 9 6 年提出了混合遗传搜索( h y b r i dg e n e t i c s e a r c h ) 方法， 即把禁忌搜索( t a b us e a r c h ) 和别的局部搜索方法( 作为交叉变异算子) 相结合。这种方 】5 太原理工大学硕士研究生学位论文 法得到的解很好，但是运行时间太长。 1 9 9 8 年，m a r c h i o r ip q 给出一种基于遗传算法的简单启发式算法( as i m p l e h e u r i s t i cb a s e dg e n e t i ca l g o r i t h m ，简称为h g a ) 。该算法由两部分组成，简单遗传 算法( s i m p l eg e n e t i ca l g o r i t h m ，简称为s 6 a ) 和一个简单的贪婪启发式程序( n a i v e g r e e d yh e u r i s t i cp r o c e d u r e ) 。m a r c h i o r i 在基准图上对算法h g a 的性能进行测试， 在解的质量和运行时间上都非常令人满意；h g a 极大的提高了前面的遗传算法的性能。 该算法和前面的方法不同，在该算法中有“劳动力合理分工”的机制( a n e a td i v i s i o n o fl a b o r ) ，搜索大的子图( s u b g r a p h ) 和搜索一个团分别被结合进适应度函数和启发式 程序当中。通过实验，证明了该算法在得到的解和速度方面都优于以前基于遗传的算法。 由上述介绍可知，单纯使用遗传算法来求解最大团问题，虽然提出了各种各样的算法， 但是得到的效果比较差，不能仅通过改动变异，杂交，选择等算子而得到好的效果，最 好是能和其他的局部搜索算法相结合。 3 3 5 基于连续变量的启发式算法( c o n t i n u o u s - b a s e dh e u r i s t i c s ) 在最大团问题中的 应用 近年来，研究者们对基于连续变量的启发式算法来求解最大团有非常浓厚的兴趣， 该种算法是围绕m o t z k i n - s t r a u s 和m c p 的连续描述来求解最大团问题的。这种方法把 离散化问题转变为连续化问题来考虑。提出了一种新的解决最大团问题的方法。 p a r d a l o s 和p h i l l i p s ( 圳提出了一种基于m o t z k i n - s t r a u s 规划的全局优化算法， 通过迭代的方法来找最大团中的顶点。然而由于这种方法计算量非常大，当图的顶点数 大于7 5 时，该算法就无法运行了。最近，p e l i l l o t 划使用松弛标签算法( r e l a x a t i o n l a b e l i n g a l g o r i t h m s ) 来近似确定最大团的大小。这是一种并行、分布式的算法，在该 算法中引入了复制方程，取得了相对较好的效果，在处理随机图时，顶点数可达到2 0 0 0 ， 测试结果表明，性能优于人工神经网络方法。 3 3 6 其他启发式算法在最大团问题中的应用 1 9 8 6 年i e b a l a s 和c s y u m l 提出了子图方法( s u b g r a p ha p p r o a c h ) 该方法的依 1 6 太原理工大学硕士研究生学位论文 据是：子图g ( g g ) ，g 中的最大团c 也是图g 的团，首先寻找予图g g ，使得g 的 最大团c 能够在多项式时间( ( p o l y n o m i a lt i m e ) 内找寻找到，然后寻找到最大团c ，并 把找到的这个最大团作为原问题的近似解。 1 9 9 8 年a b b a t t i s t ae ta 1 1 5 8 1 提出一种新的基于群体的优化启发式算法来求解最 大团问题。该算法是根据人类和动物在探索未知领域时的一种侦察( s c o u t ) 本能而设计 的。该算法仅在少量图上进行测试，并且这些测试结果都比反作用局部搜索( r e a c t i v e l o c a ls e a r c h ) 的效果要差。 近年来，d n a 计算也被用来解决最大团问题，q o u y a n gi 跏在1 9 9 7 年运用计算d n a 的方法来求解m e p 。d n a 计算的主要优点是它的高并行性，但是该算法在求解最大团 时，仅限于求解图的顶点数为十位数的图。 现在求解最大团问题的方法有很多，在这里主要介绍了比较经典的和实验结果好的 算法，其它算法就不再介绍了。 1 7 太原理工大学硕士研究生学位论文 第四章最大团的界和估计 对团数( 或独立数) 的界的估计对最大团问题( 或最大独立集问题) 的研究有非常 重要的作用。最重要的原因是由于最大团三问题是n p 一完全问题之，而求解n p 一完 全问题的最大障碍在于巨大的搜索空问，且随着问题规模的增大而呈指数性增长，而对 团数或独立数的界的估计可以直接减少算法的搜索空间，从而提高算法的效力。最直观 的原因是通过求解团数的界可以刻画图的特征。反映出图中边的密集程度等特点，也可 反映图的一些不变量( 阶，边数，度数，平均度等等) 与团数或独立数的关系。本文对 团数或独立数的界的估计进行了较为系统的讨论。我们仅讨论在任意图中的团数的上下 界，并且只关注那些形式较为简单直观的界。虽然这样的界比较粗糙，但计算量却很小， 那些设计精巧的界往往是以牺牲计算量为代价的，来讨论n p 一完全问题常常是顾此失 彼。常常基于图可以最直接获得的不变量，与一些“设计精巧”的界相比，优越性是不 言而喻的。 4 1 最大团的上界 对于没有孤立点的简单连通图g = ( v ，e ) ，由文献【6 0 】知存在一个确定的正整数h ， 使h = mi 甜。( v ) ，即图 中每一顶点都有度不大于| l ，的邻接顶点，记作, a x m i n d ( u ) g 。一， g 日( 厅) 。把图g 中度不大于h 的顶点集记为r ( g ) ；把图g 中度大于h 的顶点集记为 k ( g ) 。由下面的定理可得出最大团的界。 定理1 - 图g 的阶为n ，r ( g ) 中的顶点在图g 中的平均度为岛，则图g 的最大团 不大于栉一旦 p 1 证明：设曰( g ) e ( g ) ，且满足每条边一端在圈犯) 中，另一端在t ( g ) 中。 g ( 向) k ( 6 0 中每一顶点都在t ( g ) 中有邻接顶点， j 曰( g ) 到k ( g ) i 不妨设丁( 6 ) 的顶点数为开。，又由于r ( g ) 中每一个顶点在，( g ) 中也有邻接顶点，且 1 8 太原理工大学硕士研究生学位论文 有i ( 7 1 ( g ) ) 一r ( g ) 匿( p ，”。一t t 。) i k ( g ) l ，进而 | b ( g ) l 户l f i - - n 1 由( 1 ) 式和( 2 ) 式得i k ( g ) 峰( 岛一1 ) n l ，设k ( g ) 的顶点数为n 2 ，显然疗。+ 雄：= ”， 所以一2 ( 岛一1 ) ( n - n 2 ) ，所以得： 玎2 n 一旦 ( 4 一1 ) 证毕。 另外在文献 6 0 中得，图g 的最大团不大于甩一冬( 4 2 ) 。因为r ( g ) 为图g 中 ，l + 一 度不大于h 的顶点集，n 是丁( g ) 中的顶点在图g 中的平均度，所以p 。 h ，进而 万一旦 2 所以, a x , j m i n d ( i gh2 k ( g 88 ， 2 4 太原理工大学硕士研究生学位论文 先求由 中的最大团记为m 。 为图5 - 2 。 f b h 图5 2 f i g u r e5 - 2 下面求 中的最大团，记为m 对图5 2 列表： 表5 - 2 t a b l e5 - 2 见 v ，度 b ，c ，f ，g a d ，e ，h 3 a ，e ，g ，h b c ，d ，f 3 a ec b ，d ，f ，g ，h 5 hd a ，b ，c ，e ，f ，g 6 b ，c ，f ，h e a ，d ，g 3 a e f b ，c ，d ，g ，h 5 a ，bgc ，d ，e ，f ，h 5 b ，d ，e ，h a ，c ，f ，g 4 则m 。= 工( 口，b ，c ，d ，e ，f ，g ，厅) ) 基于平均度的思想，由上面的定理得： m t = 上( 口，6 ，c ，d ，e , f ，g ，厅 ) = 月( 口) ) u ( 6 ，c ，f ，g ) ) = r ( 口 ) u 月( 6 ) u ( 上( c ，f ，g ) ) n 上( ( 口，e ，g ，居 ) ) = r ( 口) ) u 月( 6 ) u ( r ( c ) u ( l ( f ，g ) ) n ( 口，p ) ) ) ) n 三( 口，p ，g ，厅) ) 2 5 太原理工大学硕士研究生学位论文 = r ( 口) ) u r ( 6 ) u ( r ( c ) u ( r ( 力) u ( r ( g ) n 三( 口，p ”n 上( 口，e ) ) ) ) n 三( 口，e ，g ，胁) 下面算r ( c ) ) n ( 口，e ，g ，j ，) ) = r ( p ) 再算r ( 力) f l 三( 盯，e ，) f l ( 口，e ，g ，矗) ) = 异( n ) n 工( 口，砖) ( 力n 口，口) = 矿 r ( ) ) n l ( a ，e ，) ) n ( 口，e ，g ，厅 ) = 再算r ( g ) n l ( a ，p ，) n 三( 口，0 ) n 三( 口，e , g ， ) = 犬( g ) n ( 口，p ) ) 三( c ，d ，p ，f ，矗) ) n 上( ( 口，p ) ) = 三( p ) ) 胄( g ) n 工( 口，p n 三( 口，已) ) n 上( 口，p ，g ，胁) = r ( g ) ) 所以 毛= 矗( 口 ) u r ( 6 ) ) u r ( c ) ) u r ( g ) 从而得i mi 为m a x i r ( 口) l ， r ( 6 ) l ，| r ( c ) f ，i r ( g ) 1 ) ，经计算得i m 。i 4 ，且 m ，= 晨( c ) 。因为4 2 ，所以图g 的最大团l m i _ 4 ，且材= r ( c ) 。 5 4 由两种运算三和r 定义得到的结论 ( 1 ) ( v ) ) = r ( v ) ) 。 ( 2 ) 尺( s 。) n r ( s 2 ) _ r ( 墨u 最) 证明；当r ( 墨) n r ( s 2 ) 矿时，等式的左边表示包含s 中的所有顶点及其邻集 在图g 中形成的最大团与包含s ，中的所有顶点及其邻集在图g 中形成的最大团有相同 的最大团。则s ：s ，u n g ( s ) ，由算子r 定义得j r ( s 、) f l g ( s 2 ) = e ( s ，u s 2 ) ； 当r ( s 。) n g ( s ：) = 时，等式的左边表示包含s 中的所有顶点及其邻集在图g 中形 成的最大团与包含& 中的所有顶点及其邻集在图g 中形成的最大团没有相同的最大 2 6 太原理工大学硕士研究生学位论文 团。则s ：中至少有一个顶点不属于su n 。( s ) 中，则包含s 。u s ：中的所有顶点及其邻 集在图g 中形成的最大团不存在，r ( s 。u s ：) = ，8 ( s 。) n r ( s 2 ) 、r ( s ，u s ：) ( 3 ) 如果s l s 2 ，则有l ( s 。) n l ( s 2 ) = l ( s i ) ( 4 ) 当v s 时胄( v ) n 三( s ) = 只( 嵋) ；当v 盛s 时， r ( v ) ) n 三( $ = r ( 1 ，) ) n l ( s n ，) ( 5 ) 胄( v ) n ( ( s 。) n l ( s ：) ) = 月( v ) n ( 三( sn n ) n l ( s 2n m ) ) ；可以推广到有限 个。 本章通过对图g 的邻集的分解，求出图g 的最大团。这种方法不仅使得问题的规 模缩小( 其中h 的选择和平均度的应用也使得规模再次缩小) ，而且此方法不会陷入局 部最优。在研究n p c 问题时，如何对图g 进行合理有效的分解是非常值得重视的。 2 7 太原理工大学硕士研究生学位论文 第六章截支定界法 本章我们提出了一种新的精确算法：截支定界法。首先介绍此算法的基本思想，接 着应用此算法在随机图上求解最大团，最后对计算结果进行分析。 8 1 截支定界法的基本思路 基于图的分解及不同排序策略的截支定界法的思想较简单，主要是对给出的顶点数 一定的随机图的分解及不同策略的排序，这里体现新算法的核心思想；其次是团的搜索。 根据本文第五部分对图的分解算出h = m 罂 i 甜 ，把图 中度不大, m i n a ( u ) n o ( v ) g r 一，一， 于 的顶点集记为r ( g ) 记其顶点数为m ；把图g 中度大于厅的顶点集记为置( g ) 记其顶 点数为胛：；再根据第二部分算出随机图的下界口：1 1 其中肌：堕等尘一所；删去 玎一一mz 艺d ( 咋) 度小于口- 1 ( 这样可以加快下面的搜索速度) ；计算岛= 旦一；计算h = h + l 和 行2 = 疗2 - 1 ；( 显然h s p 2 即：) 经过大量的实验得出，对于一般的随机图g 而言 若见靠近，则图中含有最大团所包含顶点的度接近( g ) 的概率比较大，把足( g ) 中的顶点依贪婪的思想排序。( 岛靠近或厅数学上用矧的范围来表示。具体 讨论见下部分中的实验结果。) 若p ：靠近 ，则图中含有最大团所包含顶点的度接近艿( g ) 的概率比较大，把k ( g ) 婪的思想排序。 若段介于h 与他。之间，则把足( g ) 中的顶点依平均度的思想排序。因为图中含有 最大团d ( g ) 一团的概率要明显大于j ( 9 ) 一团或( g ) 团，对k ( g ) 中对顶点进行排 序，排序后的顶点序列若记为：v 1 ，v ：，v ，其中v l 满足 2 8 太原理工大学硕士研究生学位论文 d ( v ，) 一( ，( g ) m i n d ( v ) 一d ( g ) | | v ，y ( g ) ) ， v 2 满足 i d ( v ：) 一d ( g h ) m i n o d ( v ) 一d ( g v 。) | | v ，v ( g v 。) ， 一般地，满足 l d ( v i ) 一d ( g 一( v l ，1 一1 ) ) i - r a i n i d ( h ) 一d ( g 一( v l ，k 1 ) ) 0 h v ( g 一( v l ，1 一i ) ) ) k 即