最大团问题分支限界法

01问题与模型

最大团问题的定义子集树模型最大团问题可以建模为子集选取问题。解空间是一棵高度为n的完全二叉树，每个叶结点对应一个候选顶点子集。通过遍历这棵树，可以找到最大团。在无向图中，团是一组顶点，其中任意两个顶点之间都存在边。最大团是指顶点数最多的团。团的定义要求顶点之间两两相邻，形成一个紧密的子图。无向图中的团

暴力搜索需要遍历2^n个叶结点，随着顶点数n的增加，计算量呈指数级增长，导致计算不可行。这种穷举策略在大规模问题上效率低下。暴力搜索的复杂度为了避免无效搜索，需要引入剪枝策略。通过提前判断某些分支不可能产生最优解，可以减少搜索空间，提高算法效率。剪枝的必要性