最大团算法


写在前面,

  1. 补图的最大独立集点数 = 原图的最大团点数。在原图中有的边在补图中都没有,原图的最大团的所有边去掉之后,其就是补图的最大独立集。

最大团

一般图中的最大团问题

写在前面,
求最大团,我们用算法3,最快,极大团数量只能用算法1。

Bron-Kerbosch算法1 $O(3^n)$

朴素算法伪代码

BronKerbosch1(R,P,X):
    if P and X are both empty:
        report R as a maximal clique
    for each vertex v in P:
        // p ∩ N(v): 得到既与v相邻也与v的邻点相邻的点,两两之间有边,团
        BronKerbosch1(R ∪ {v}, P ∩ N(v), X ∩ N(v))
        P := P \ {v} // 回溯看其他邻点能不能构成更大的团 v点不能向外扩展已经被踢出去了
        X := X ∪ {v} // 当我们已知点v无法向外拓展了

实现

int some[maxn][maxn];
int none[maxn][maxn];
int all[maxn][maxn];
int mp[maxn][manx];
void dfs(int d, int an, int sn, int nn)
{
    // !nn: 防止极大团计数的时候,加重 含X中点的极大团已经求过了
    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;
    }
}

带轴算法伪代码 - 缩小了搜索范围
最大团要么包含u,要么包含u的非直接邻居。

  1. 两个都包含的话,两点之间有直接边,那就是直接邻居了,矛盾。
  2. 两个都不包含的话,团中的点无法与其相连,非团。
BronKerbosch1(R,P,X):
    // P为空即当前点的邻点中找不到R的公共邻点
    // 如果P为空,X非空,由于X中的点的最大团已经搜过了,此时v点能到X,那么这个最大团已经被搜过了
    if P and X are both empty:
        report R as a maximal clique
    choose a pivot vertex u in P ∪ X // P ∪ X: 当前团的所有公共邻点
    for each vertex v in P\N(u): // P是会变的,最大团要么包含u,要么包含u的非直接邻居
        // p ∩ N(v): 得到既与v相邻也与v的邻点相邻的点,两两之间有边,团
        BronKerbosch1(R ∪ {v}, P ∩ N(v), X ∩ N(v))
        P := P \ {v} // 回溯看其他邻点能不能构成更大的团 v点不能向外扩展已经被踢出去了
        X := X ∪ {v} // 当我们已知点v无法向外拓展了

实现

const int maxn = 130;
bool mp[maxn][maxn];
// all为已确定的极大团顶点的集合,some为未处理顶点集(初始状态是全部顶点),none为不取的(已搜过的)顶点集。
int some[maxn][maxn], none[maxn][maxn], all[maxn][maxn]; // 第一维范围为点数
int n, m, ans;
void dfs(int d, int an, int sn, int nn) // an为R(all)的数量,sn为some集合中的数量,nn为none的
{
    if(!sn && !nn) ans = max(ans, an); // 最大团点数
    int u = some[d][0];   // 选择piot
    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;
        // P ∩ N(v)
        for(int j = 0; j < sn; ++j)
            if(mp[v][some[d][j]]) // v->0肯定无边
                some[d+1][tsn++] = some[d][j];
        // X ∩ N(v)
        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; // v->0肯定无边
    }
}
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", &n) && n)
    {
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
            {
                int x; scanf("%d", &x);
                mp[i][j] = mp[j][i] = x;
            }
        printf("%d\n", work());
    }
    return 0;
}

有序带轴算法

  • 退化序:每次选择所有点中的度最小的点,然后删去点和他的出边,然后再从剩余的点序列中选出度最小的点,迭代的序列就是图的退化序。
  • 优化有可能退化(就没必要了)
  • 根据退化序,将ver加入R集合,然后出边的节点放到P集合中待选,如果其出边节点已经被遍历过了,那么我们将其加入X集合。

BronKerbosch算法2 O(3^n)

写在前面,
Code1会快一些。

Code 1

const int maxn = 55;
bool mp[maxn][maxn];
int best, n, num[maxn];
bool dfs(int *adj, int total, int cnt)
{
    int t[maxn], k;
    if(total == 0)
    {
        if(cnt > best)
        {
            best = cnt;
            return true; // 由于num[i]最大可能为num[i+1]+1,因为总点集就多了一个,要么和num[i]相等,要么就多一个, 所以在枚举顶点i时,只要一更新best,可知此时的num[i]就为num[i+1]+1了,不需要再去尝试找其他的方案了,所以应立即返回剪枝。
        }
        return false;
    }
    for(int i = 0; i < total; ++i)
    {
        // 此时返回false的话,是有可能其不为极大团的,所以无法对极大团计数,注意!
        if(cnt+total-i <= best) return false;    //剪枝1 可要可不要
        if(cnt+num[adj[i]] <= best) return false;    //剪枝3 
        k = 0;
        for(int j = i+1; j < total; ++j) // 注意这里是团的公共邻点集合
            if(mp[adj[i]][adj[j]]) t[k++] = adj[j]; // 能到adj[i]的点和团的公共邻点的交集
        if(dfs(t, k, cnt+1)) return true;
    }
    return false;
}
int MaximumClique()
{
    int adj[maxn], k;
    best = 0;
    for(int i = n; i >= 1; --i)
    {
        k = 0;
        for(int j = i+1; j <= n; ++j)
        if(mp[i][j]) adj[k++] = j;
        //得到当前点i的所有相邻点存入adj 
        dfs(adj, k, 1);    //每次dfs相当于必选当前i点看是否能更新best 
        num[i] = best;
    }
    return best;
}
int main()
{
    while(cin >> n && n)
    {
        for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            int x; cin >> x;
            mp[i][j] = x;
        }
        cout << MaximumClique() << endl;
    }
    return 0;
}

Code 2

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++){
        // 我们从i点延伸如果延伸的是非i所在最大团的点的话,那么必然无法形成团,或者说形成的团一定不是最大的
        // 如果此时加入的点,我们都假设其所在的最大团与当前团中的所有点都能两两有边(是最大的了),点数依然小于res,那么我们直接剪枝
        if(cnt[i]+num<=res)
            return false;
        // 如果当前点能到i点,我们就查询i是否都能与当前团中的所有点有边,如果可以,就将i加入最大团,然后继续递归
        if(G[pos][i]){
            int j;
            for(j=0;j<num;j++)
                if(!G[i][vis[j]])
                    break;
            if(j==num){
                vis[num]=i; // 回溯时无需清除,会覆盖
                if(dfs(i,num+1))
                    return true;
            }
        }
    }

    if(num>res){
        for(int i=0;i<num;i++)//最大团的元素
            group[i]=vis[i];
        res=num;//最大团中点的数目
        return true; // 由于num[i]最大可能为num[i+1]+1,因为总点集就多了一个,要么和num[i]相等,要么就多一个, 所以在枚举顶点i时,只要一更新best,可知此时的num[i]就为num[i+1]+1了,不需要再去尝试找其他的方案了,所以应立即返回剪枝。
    }
    return false;
}
void maxClique(){
    res=0;
    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;
        }
        maxClique();

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

随机化算法

弦图


参考资料:

  1. https://blog.csdn.net/yo_bc/article/details/77453478
  2. https://wenku.baidu.com/view/65972e184693daef5ff73d2c.html
  3. https://blog.csdn.net/u011815404/article/details/86609798?spm=1001.2014.3001.5506

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Current
最大团算法 最大团算法
写在前面, 补图的最大独立集点数 = 原图的最大团点数。在原图中有的边在补图中都没有,原图的最大团的所有边去掉之后,其就是补图的最大独立集。 最大团一般图中的最大团问题写在前面,求最大团,我们用算法3,最快,极大团数量只能用算法1。
2021-04-15
Next 
Codeforces-1486B Eastern Exhibition Codeforces-1486B Eastern Exhibition
ProblemPortal Thoughts这个就是货仓选址那个题的经典结论:取所有x的中位数,如果n是奇数那么中位数唯一;反之可以选中间两个数之间的任何一个位置.那么由于两个子问题相互独立,直接乘法原理统计方案数就可以了. Accep
  TOC