浅析最大团算法

[关键词] 团 图论 NP问题

[摘要]
最大团问题(Maximum Clique Problem, MCP)是图论中一个经典的组合优化问题,也是一类NP完全问题,在国际上已有广泛的研究。其确定性算法有回溯法、分支限界法等,启发式算法有蚁群算法、顺序贪婪算法、DLS-MC算法和智能搜索算法等等。本文主要介绍Bron–Kerbosch算法及其优化

[正文]

1.问题背景

1.1 问题描述

团:一个每两个点都有边相互连接的点集,也就是完全子图。
最大团:图中点数最多的团。
极大团:简单的说就是不被另一个团所包围的团独立集:与团相反,也就是两两直接都没有边的点集。

最大团中顶点数量 = 补图的最大独立集中顶点数量

1.2 例子

graph.png 图中有三个最大团,是(1,3,4),(1,2,3),(3,4,5)

但有四个极大团,是(1,3,4),(1,2,3),(3,4,5),(2,6)

1.3 研究历史

最大团问题又称为最大独立集问题,它是一类NP完全问题,所以并没有多项式时间算法。Bron–Kerbosch 算法是由荷兰科学家 Coenraad Bron 和 Joep Kerbosch 设计的,他们于1973年发表了论文《Algorithm 457: finding all cliques of an undirected graph》。
另一位科学家 Akkoyunlu 在同时代提出的算法虽然用不同的术语表示,但由于它生成相同的递归搜索树,因此可以看作与 Bron-Kerbosch 算法相同。

1.4 NPC问题简介

NP就是多项式复杂程度的非确定性问题。而如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题,那么这个NP问题就称为NP完全问题。

填字游戏是一种常见的益智纸上游戏,也是NP完全问题之一。

填字游戏

2 Bron–Kerbosch算法

2.1算法描述

这种方法是一种回溯法。

设有三个集合。

R表示当前最大团中已包含的点集。
P集合记录的是和R集合中所有点都有连边的点。
X集合表示已经完成极大团计数的点。
每次把P集合中的一个点加入R。
若P和X集合都为空,R集合就为最大团。
进行搜索,更新P集合。
其伪代码十分简单

1
2
3
4
5
6
7
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)) //N(v)表示与v连边的点 显然,只有与V连边的节点才可以有可能加入答案
P = P \ {v} //已经搜过了,从P中删除
X = X ∪ {v} //加入不选的集合

2.2举例

graph.png
1
2
3
4
5
6
7
8
9
10
11
12
13
14
({},{1,2,3,4,5},{}) 枚举P中的每个点
({1},{3},{}) 取1加入R
({1,3},{},{}) 回溯,得到一个最大团
将1加入X
将1从P删除
({2},{3,5,4},{}) 取2加入R,虽然此时X集合中有1节点,但1不与2节点连边,所以调用的X集合为空
({2,5},{},{}) 回溯,得到一个最大团
({2,3},{},{}) 回溯,得到一个最大团
({2,4},{},{}) 回溯,得到一个最大团
将2加入X
将2从p删除
({3},{},{1,2}) 此时虽P为空,但X不为空,所以不计入答案
({4},{},{2}) 同上
({5},{},{2}) 同上

2.3优化

为了节省时间和让算法更快的回溯,我们可以通过设定关键点pivot vertex u进行优化。

我们知道在上述的算法中必然有许多重复计算之前计算过的极大团然后回溯的过程。

取集合P∪X中的一个点u,要与R集合构成极大团,那么取的点必然是P∩N(u)中一个点(N(u)代表与u相邻的点)。

简单地说就是如果取完u之后我们再取与u相邻的点v也能加入到极大团,那么只取u就好了。从而剪掉了之后对再v的搜索,所以之后就只能取与u不相邻的点,这样我们照样可以重复不漏的计算所有极大团,从而减少许多不必要的计算。而我们要想进一步减少计算,我们就可以取邻居尽可能多的u,即使我们要遍历的点尽可能减少,但是其实没必要写,寻找合适的u也会减少一定的效率。

伪代码如下

1
2
3
4
5
6
7
8
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}

2.4优化举例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
({},{1,2,3,4,5},{}) 枚举P中的每个点
({1},{3},{}) 取1加入R
取1作为关键点
({1,3},{},{}) 回溯,得到一个最大团
将1加入X
将1从P删除

({2},{3,5,4},{}) 取2加入R,虽然此时X集合中有1节点,但1不与2节点连边,所以调用的X集合为空
({2,5},{},{}) 回溯,得到一个最大团
({2,3},{},{}) 回溯,得到一个最大团
({2,4},{},{}) 回溯,得到一个最大团
将2加入X
将2从p删除
({3},{},{1,2}) 此时虽P为空,但X不为空,所以不计入答案
({4},{},{2}) 同上
({5},{},{2}) 同上

2.5核心代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}
}

2.6实测性能对比

加入优化后在120个点,8000条边的较为稠密的随机图中耗时0.3秒左右

不加入优化超时。

加入优化在120个点的稀疏图中非常快,最多10ms

不加入优化超时。

3.例题

3.1 All Friends

题意描述:极大团计数模板。

数据规模:n<128,多组数据

很明显,就是让你求一个图中的极大团的个数,需要注意多组数据。

这里直接使用bron-Kerbosch算法。

由于n最大达120左右此处需要加上优化,否则会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include<bits/stdc++.h>
using namespace std;
const int maxn = 130;
bool mp[maxn][maxn];
int some[maxn][maxn], none[maxn][maxn], all[maxn][maxn];
int n, m, ans;
void dfs(int d, int an, int sn, int nn){
if(!sn && !nn) ++ans;
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;
if(ans > 1000) return;
}
}
int work(){
ans = 0;
for(int i = 0; i < n; ++i) some[1][i] = i+1;
dfs(1, 0, n, 0);
return ans;
}
int main(){
while(~scanf("%d %d", &n, &m)){
memset(mp, 0, sizeof(mp));
for(int i = 1; i <= m; ++i){
int u, v;
scanf("%d %d", &u, &v);
mp[u][v] = mp[v][u] = 1;
}
int tmp = work();
if(tmp > 1000) puts("Too many maximal sets of friends.");
else printf("%d\n", tmp);
}
return 0;
}

4.特殊图上最大团问题

4.1 弦图上的最大团问题

一个点的序列v[1], v[2], …, v[n]满足v[i]在{v[i], v[i+1], …, v[n]}的诱导子图中为一个单纯点称作完美消除序列

考虑按完美消除序列从后往前,每个点贪心选择最小可染颜色,

那么他会产生的颜色种类<=所在团大小,

而一个团由于两两连边,每个点颜色都不同,所以产生的颜色种类又>=团的大小,

所以弦图点色数就是弦图最大团的大小。

此处只需逆序寻找完美消除序列,然后染成能染的最小颜色即可,本质上是一个贪心算法,证明过程较为冗长,不多叙述。

5.参考文献

[1]Coen Bron,Joep Kerbosch.finding all cliques of an undirected graph

[2]cdq.弦图与区间图