浅析最大团问题
一 最大团的定义
团：一个每两个点都有边相互连接的点集，也就是完全图。
最大团：图中点数最多的团。
极大团：不被另一个团所包含的团
独立集：与团相反，也就是两两直接都没有边的点集。
最大团中顶点数量 = 补图的最大独立集中顶点数量
这个是非常显然的。
举个例子 图中有三个最大团，是(1,3,4),(1,2,3),(3,4,5)
但有四个极大团，是(1,3,4),(1,2,3),(3,4,5),(2,6)
例题 POJ2989 极大团计数 HDU1530 最大团计数
二 Bron–Kerbosch算法
这种方法基本就是爆搜。
设有三个集合。
R表示当前最大团中已包含的点集。
P集合记录的是和R集合中所有点都有连边的点。
X集合表示已经加入过R集合的点。
每次把P集合中的一个点加入R。
若P和X集合都为空，R集合就为最大团。
进行搜索，更新P集合。
其伪代码十分简单
BronKerbosch1(R, P, X):
if P and X are both empty://所有点已选完，且没有不能选的点,累加答案
report R as a maximal clique
for each vertex v in P: //枚举Some中的每一个元素
BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v)) //显然，只有与V连边的节点才可以有可能加入答案
P = P \ {v} //已经搜过了，从P中删除
X = X ⋃ {v} //加入不选的集合换一个例子
一开始P是1,2,3,4,5其他都为空
然后取1加入R，枚举
就很简单得到了代码
void dfs(int d, int an, int sn, int nn)
{
if(!sn && !nn) return;
for(int i = 0; i < sn; ++i)
{
int v = some[d][i];
for(int j = 0; j < an; ++j)
all[d+1][j] = all[d][j];
all[d+1][an] = v;
int tsn = 0, tnn = 0;
for(int j = 0; j < sn; ++j)
if(mp[v][some[d][j]])
some[d+1][tsn++] = some[d][j];
for(int j = 0; j < nn; ++j)
if(mp[v][none[d][j]])
none[d+1][tnn++] = none[d][j];
dfs(d+1, an+1, tsn, tnn);
some[d][i] = 0, none[d][nn++] = v;
}
}优化
显然，这个算法计算了大量不可能成为最大团的点集。
为了节省时间和让算法更快的回溯,我们可以通过设定关键点pivot vertex u进行优化。
我们知道在上述的算法中必然有许多重复计算之前计算过的极大团然后回溯的过程。
取集合P∪X中的一个点u，要与R集合构成极大团，那么取的点必然是P∩N(u)中一个点（N(u)代表与u相邻的点）。
简单地说就是如果取完u之后我们再取与u相邻的点v也能加入到极大团，那么只取u就好了。从而剪掉了之后对再v的搜索，所以之后就只能取与u不相邻的点，这样我们照样可以重复不漏的计算所有极大团，从而减少许多不必要的计算。而我们要想进一步减少计算，我们就可以取邻居尽可能多的u，即使我们要遍历的点尽可能减少，但是其实没必要写，寻找合适的u也会减少一定的效率。
伪代码如下
BronKerbosch2(R, P, X) is
if P and X are both empty then//同上
report R as a maximal clique
choose a pivot vertex u in P ⋃ X//选取一个关键点
for each vertex v in P \ N(u) do//选取P
BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
P := P \ {v}
X := X ⋃ {v}
void dfs(int d, int an, int sn, int nn)
{
if(!sn && !nn) ans = max(ans, an);
int u = some[d][0];
for(int i = 0; i < sn; ++i)
{
int v = some[d][i];
if(mp[u][v]) continue;
for(int j = 0; j < an; ++j)
all[d+1][j] = all[d][j];
all[d+1][an] = v;
int tsn = 0, tnn = 0;
for(int j = 0; j < sn; ++j)
if(mp[v][some[d][j]])
some[d+1][tsn++] = some[d][j];
for(int j = 0; j < nn; ++j)
if(mp[v][none[d][j]])
none[d+1][tnn++] = none[d][j];
dfs(d+1, an+1, tsn, tnn);
some[d][i] = 0, none[d][nn++] = v;
}
}