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