『算法-ACM 竞赛-图论』最大团问题

一、定义

一个无向图 G=(V，E)，V 是点集，E 是边集。取 V 的一个子集 U，若对于 U 中任意两个点 u 和 v，有边 (u,v)∈E，那么称 U 是 G 的一个完全子图。 U 是一个团当且仅当 U 不被包含在一个更大的完全子图中。

G 的最大团指的是定点数最多的一个团。

简单来说，极大团是增加任一顶点都不再符合定义的团，最大团是图中含顶点数最多的极大团，最大独立集是除去图中的团后的点集，而最大团问题就是在一个无向图中找出一个点数最多的完全图。

二、常用结论

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

2、二分图中，最大独立集点的数量+最小覆盖点的数量=整个图点的数量

3、二分图中，最小覆盖点的数量=最大匹配的数量

4、图的染色问题中，最少需要的颜色的数量=最大团点的数量

三、算法实现

毕竟是 NP 完全问题，所以具体使用，什么算法，区别不是很大，具体体现在剪枝上！

对于弦图来说，求最大团一般使用 MCS 算法，而对于一般图来说，常使用 Bron-Kerbosch 算法

【Bron-Kerbosch 算法】
Bron-Kerbosch 算法用于计算图中的最大的全连通分量，即计算图的最大团。

1.算法原理
Bron-Kerbosch 算法的基础形式是一个递归回溯的搜索算法，其通过给定三个集合：R、P、X 来递归的进行搜索

初始化集合 R、X 分别为空，集合 P 为所有顶点的集合
每次从集合 P 中取顶点 {vi}，当集合中没有顶点时，有两种情况：
1）集合 R 是最大团，此时集合 X 为空
2）无最大团，此时回溯
对于每一个从集合 P 中取得的顶点 {vi}，有如下处理：
1）将顶点 {vi} 加到集合 R 中，集合 P、X 与顶点 {vi} 得邻接顶点集合 N{vi} 相交，之后递归集合 R、P、X
2）从集合 P 中删除顶点 {vi}，并将顶点 {vi} 添加到集合 X 中
3）若集合 P、X 都为空，则集合 R 即为最大团
总的来看，就是每次从集合 P 中取 vi 后，再从 P∩N{vi} 集合中取相邻结点，保证集合 R 中任意顶点间都两两相邻

伪代码过程

BronKerbosch1(R,P,X):
    if P and X are both empty:
        report R as a maximal clique
    for each vertex v in P:
        BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

2.算法优化
对于基础的算法，由于其递归搜索了所有情况，对其中有些不是最大团的也进行了搜索，效率不高，为了节省时间让算法更快的回溯，可以通过设定关键点来进行搜索。

由于对于任意的最大团，其必须包括顶点 {u} 或 N-N{u}，不然其必然需要通过添加它们来进行扩充，这显然矛盾，所以仅需测试顶点 {u} 以及 N-N{u} 即可。

伪代码过程：

BronKerbosch2(R,P,X):
    if P and X are both empty:
        report R as a maximal clique
    choose a pivot vertex u in P ⋃ X
    for each vertex v in P \ N(u):
       BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
       P := P \ {v}
       X := X ⋃ {v}

由于其是通过选择特殊点，来进行最小化递归调用，一定程度上节省了时间，但还可以与降序的方式结合使用，来保证在线性的时间内求子图的最大团

伪代码过程：

BronKerbosch3(G):
    P = V(G)
    R = X = empty
    for each vertex v in a degeneracy ordering of G:
        BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

3.实现

int n,m;
bool G[N][N];
int cnt[N];//cnt[i]为>=i的最大团点数
int group[N];//最大团的点
int vis[N];//记录点的位置
int res;//最大团的数目
bool dfs(int pos,int num){//num为当前独立集中的点数
    for(int i=pos+1;i<=n;i++){
        if(cnt[i]+num<=res)//剪枝，若取i但cnt[i]+已经取了的点数仍<ans
            return false;

        if(G[pos][i]){//与当前团中元素比较，取Non-N(i)
            int j;
            for(j=0;j<num;j++)
                if(!G[i][vis[j]])
                    break;
            if(j==num){//若为空，则皆与i相邻，则此时将i加入到最大团中
                vis[num]=i;
                if(dfs(i,num+1))
                    return true;
            }
        }
    }

    if(num>res){//每添加一个点最多使最大团数+1,后面的搜索就没有意义了
        for(int i=0;i<num;i++)//最大团的元素
            group[i]=vis[i];
        res=num;//最大团中点的数目
        return true;
    }
    return false;
}
void maxClique(){
    res=-1;
    for(int i=n;i>0;i--){//枚举所有点
        vis[0]=i;
        dfs(i,1);
        cnt[i]=res;
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        memset(G,0,sizeof(G));

        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            G[x][y]=1;
            G[y][x]=1;
        }

        //建立反图
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j)
                    G[i][j]=0;
                else
                    G[i][j]^=1;
            }
        }
        maxClique();

        if(res<0)
            res=0;
        printf("%d\n",res);//最大团的个数
        for(int i=0;i<res;i++)//最大团中的顶点
            printf("%d ",group[i]);
        printf("\n");
    }
    return 0;
}

四、刷题练手

1、裸题：ZOJ 1492 Maximum Clique HDU 1530

2、稍微麻烦点的题：HDU 3585 maximum shortest distance

3、一般无向图最大独立集的题目：POJ 1419 Graph Coloring

4、来一个染色问题：POJ 1129 Channel Allocation