最大团问题是图论中的经典组合优化问题，虽然描述简单，但是非常复杂难解，属于一类NP-完全问题。最大团问题与图论中许多经典问题有十分密切的关系，可以在多项式时间内转换成最大独立集问题、最小顶点覆盖问题、最小着色问题、背包问题以及货郎担问题等经典问题。最大团问题的研究对于解决图论中的众多问题有着重要意义。作为图论中经典的组合优化问题，最大团问题与人们的现实生活关系十分密切，在实践生活中广泛应用于人员活动的安排、市场分析方案的选择，机器故障的诊断以及信号传输等许多应用领域。因此，最大团问题的研究有着巨大的实际应用价值。最大团的问题的算法分为确定性算法和非确定性算法两类。确定性算法要求程序在有效的时间内给出最大团问题的最优解，而非确定性的算法并不保证最终程序给出的是最优解。最大团问题是NP-完全问题，当无向图规模较大时在有效时间内可能无法计算出最优解，非确定性算法可以在有限时间内给出无向图的最大团问题最优解的一个近似解。本文首先对最大团问题的应用背景进行了简单的介绍。描述了当前对于无向图中查找最大团问题的研究成果，并对当前关于最大团问题的主流解法进行了论述。对最大团问题确定性算法中的分支搜索算法做了详细的分析和研究。关于分支搜索算法求解最大团问题的关键在于对无向图的划分和对划分后生成的子图中存在的团上界以及下界的估计。无向图划分目的是将规模大的无向图划分成尽可能小的子图，最大化的降低最大团问题的规模。对于划分子图的上界估计可以提高剪枝效率，缩小在无向图中查找最大团时的搜索空间，从而提高搜索的速率。本文对无向图进行了仔细的分析，根据无向图本身结构特性及图论中MaxSAT问题的求解技巧对最大团问题的上界估计函数进行了优化，改进了关于最大团问题的分支搜索算法，并对优化后的关于最大团问题的分支搜索算法进行了对比测试，测试结果表明算法速率得了很大的提高。