一般图最大独立集

一、定义:

独立集:在一个图中,找到一个集合包含的所有点相互之间都不存在连边

最大独立集:在所有独立集中包含元素个数最多的独立集

二、处理问题的第一步:问题转化:

需要用最大团来求最大点独立集,因此先引入最大团的概念

最大团问题
一般图最大独立集
tips:最大团和强连通分量有区别,最大团U要求U成为最大的点集,且点集内任意两点都连通,而强连通分量U要求U成为最大的点集,且满足点集内任意两点都有一条互相到达的路径。
最大的区别在于是否关注连接两点的路径的方向,最大团不关注路径的方向,只要有路径连接即可,而强连通分量关注路径的方向,既要能从一个点到另一个点,又能从另一个点回到该点。

最大团的求法
一般图最大独立集

最大团问题与最大独立集问题的关系
求解一个图中的最大独立集等价于求解其补图的最大团。

补图就是把原图中所有边都删去,把所有原本没有边直接连接的两个点之间都连上边。(字面意思,很好理解)

独立集的条件是任意两个点互不连通,那么如果把原图中连通的点之间的边删除,不连通点连接,即转化为求个数最多的两两连通点集,也即求最大团。

问题现在已经转化为了求最大团,用一般的最大团算法完成就可以

三、处理问题的第二步:去学最大团的求法 模版来源

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

Bron-Kerbosch 算法

1、算法原理:

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

<1>初始化集合 R、X 分别为空,集合 P 为所有顶点的集合
<2>每次从集合 P 中取顶点 {vi},当集合中没有顶点时,有两种情况:
······1)集合 R 是最大团,此时集合 X 为空
······2)无最大团,此时回溯
<3>对于每一个从集合 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 中任意顶点间都两两相邻
2、算法优化

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

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

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

Code

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;
}

上一篇:VI编辑器基础命令


下一篇:Linux系统概述和编程基础