图的邻集分解与最大团问题的研究

论文摘要

最大团问题（Maximum clique problem，MCP）是图论中经典的组合优化问题。本文综述了国内外学者对此问题的研究成果，包括该问题的应用背景，界的估计，及各种算法的研究。本文首先对最大团的界进行了论述，并提出了一个新的上界。其次详细探讨了图的邻集分解与最大团。图的分解不仅使问题的规模缩小（其中参数的选择和平均度的应用使得规模再次缩小），同时此方法不会陷入局部最优。本文最后基于图的邻集分解及不同排序策略提出了一种新的精确算法——截支定界法。该算法吸取了分支定界法的优点，先用下界把图中对求解最大团没价值的点删去，再应用图的邻集分解方法对给出的随机图进行分解，使求解最大团的搜索规模大大收缩，从而加快了算法的收敛速度，最后再对团进行搜索。其中在团的搜索阶段对不同类型的图采取不同的搜索策略。对边密度较大的图由于最大团中包含最大度顶点的概率比较大，所以采取贪婪搜索策略；对边密度较小的图由于最大团中包含最小度顶点的概率比较大，所以采取非贪婪的搜索策略；对中等密度的图由于最大团接近平均度顶点的概率比较大，所以采取由导师提出的基于平均度的搜索策略。实算表明，这样做有助于加快搜索速度。该算法在随机图上进行了测试，取得了良好的效果。在研究NP-C问题时，如何对图G进行合理有效的分解是值得重视的。这是本文研究的初衷，也是值得进一步研究的重点。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 最大团问题及其实际意义
• 1.2 最大团问题在图论问题中的重要性
• 1.3 对最大团问题国内外的研究现状概述
• 1.4 本文所用的概念和记号
• 第二章 精确算法在最大团问题中的应用
• 2.1 枚举法在最大团中的应用
• 2.2 分支定界方法在最大团问题中的应用
• 第三章 启发式算法在最大团问题中的应用
• 3.1 顺序贪婪启发式算法在最大团问题中的应用
• 3.2 局部搜索启发式算法在最大团问题中的应用
• 3.3 现代启发式算法在最大团问题中的应用
• 3.3.1 禁忌搜索算法在最大团问题中的应用
• 3.3.2 模拟退火算法（Simulated annealing）在最大团问题中的应用
• 3.3.3 神经网络（Neural networks）方法在最大团问题中的应用
• 3.3.4 遗传算法在最大团问题中的应用
• 3.3.5 基于连续变量的启发式算法（Continuous-based Heuristics）在最大团问题中的应用
• 3.3.6 其他启发式算法在最大团问题中的应用
• 第四章 最大团的界和估计
• 4.1 最大团的上界
• 4.2 最大团的下界
• 4.3 在简单例图上的实验结果
• 第五章 图的邻集分解与最大团
• 5.1 关于最大团问题的定理
• 5.2 求解最大团
• 5.3 举例说明
• 5.4 由两种运算L和R定义得到的结论
• 第六章 截支定界法
• 6.1 截支定界法的基本思路
• 6.2 实验结果及其分析
• 第七章 进一步工作
• 7.1 图的邻集分解与最大团的进一步工作
• 7.2 用截支定界法求最大团的进一步工作
• 参考文献
• 附录
• 致谢
• 发表论文情况