一个团(clique)是一个任何两个顶点都相邻的完全图。在社交网络中,完全图代表着最为紧密的社交关系,因此在网络中挖掘出最大的一个团非常有现实意义,也成为了社会计算、数据挖掘等领域中的一个经典问题。但是由于团的要求非常严格,为了更好地刻画密集子群结构,各种松弛团模型被提出。这些模型常通过对团的某一方面性质进行松弛得到,比如对顶点度数进行松弛得到的模型有k-core,k-plex等;对路由长度进行松弛得到的模型有k-clique,k-club等;对连通度进行松弛得到模型有k-block,k-bundle等。其中k均是模型固有的参数。最大松弛团问题,即从给定的图中提取基数最大的满足松弛团定义的子图,是著名的组合优化问题最大团的推广。本文将研究三个与最大松弛团相关的问题,一是最大k-plex问题,二是最大k-bundle问题,三是最小染色和(Minimum Sum Coloring)问题。本文首先研究了最大k-plex问题,并提出了一个基于分支定界的精确求解算法。相较于已有的最大k-plex问题的精确算法,本文从理论上分析证明了我们的算法具有更低的时间复杂度上界,是第一个突破2~n时间复杂度的精确算法,其中n是图中的顶点数量。实验表明我们的算法在标准测试集上的表现也更优秀。接着本文研究了基于连通度松弛的模型k-bundle。针对最大k-bundle问题,我们分析了k-plex与k-bundle在结构上的异同,借鉴并改进了我们在最大k-plex问题的精确算法中提出的分支规则。同时本文还设计了更多基于直径,图染色等方法的剪枝规则用于加速我们的算法。在标准测试集上的实验对比表明,我们的算法相较于该问题已有的精确算法更高效,特别是在大规模的社交网络算例上。最后,本文给出了最大松弛团问题在最小染色和问题上的一个应用。最小染色和问题是在超大规模集成电路设计以及资源分配调度等领域有广泛应用一个的组合优化问题,本文给出了一个利用最大团和最大松弛团来构造最小染色和理论下界的方法。