无向图的最大团/最大独立集

心已赠人 2023-08-17 16:26 119阅读 0赞

讲解的博客：[https://blog.csdn.net/SparkFucker/article/details/83051133][https_blog.csdn.net_SparkFucker_article_details_83051133]

![1445562-20190831152852173-382571914.png][]

还没写完的代码：

#include<iostream>
    #include<algorithm>
    #include<vector>
    using namespace std;
    typedef long long ll;
    //const int N = 100005;
    #define maxn 300050
    vector<int> g[maxn];
    vector<int> res;
    int clolr[maxn];
    int pre[maxn];//记录前一个节点
    bool flag;
    int root; 
    
    void Init(){
        memset(color,-1,sizeof(color));
        memset(pre,-1,sizeof(pre));
        res.clear();
        flag=true;
        for(int i=0;i<N;i++){
            g[i].clear();
        }
    }
    
    void dfs(int v,int val){
        if(!flag)   return;
        color[v]=val;
        for(int i=0;i<g[v].size();i++){
            if(!flag)   return;
            pre[g[v][i]]=v;
            
            if(color[g[v][i]]==-1){   //二分图 
                dfs(g[v][i],val^1);
            }
            else{   //说明不是二分图 
                if(color[g[v][i]]==val){
        //说明奇环就出现在这里
                    flag=false;
                    root=g[v][i];
                    return; 
                }
            }
        }
    }
    
    int main(){
        init();
        int n,m;
        
    }

最大团其实就是最大完全子图的点集，同理极大团也就是极大完全子图的点集，点集内所有的点两两之间都有边相连。

定义 （维基百科）：

在图论领域的一个无向图中，满足两两之间有边连接的顶点的集合，被称为该无向图的团。

最大独立集其实就是补图的最大团，因为和最大团相反，最大独立集合内的点两两之间都没有边相连。

定义（维基百科）：

一个独立集（也称为稳定集）是一个图中一些两两不相邻的顶点的集合。

**最大团的个数 = 补图的最大独立数**

**最小覆盖数+最大独立数 = 顶点数。**

**在二分图中，最小覆盖数 等于 最大匹配数， 而最大独立数又等于 顶点数减去最小覆盖数**

# 无向图的几个基本算法应用：**[https://blog.csdn.net/yafeichang/article/details/53888866][https_blog.csdn.net_yafeichang_article_details_53888866]** #

**有向图的几个算法[https://blog.csdn.net/yafeichang/article/details/53893120][https_blog.csdn.net_yafeichang_article_details_53893120]**

**[https://blog.csdn.net/pi9nc/article/details/9632621][https_blog.csdn.net_pi9nc_article_details_9632621]**

**[https://blog.csdn.net/qq\_40859951/article/details/88540146][https_blog.csdn.net_qq_40859951_article_details_88540146]**

[https://blog.csdn.net/westbrook1998/article/details/82933263][https_blog.csdn.net_westbrook1998_article_details_82933263]   ！！！

求解方法：

一.暴力法求最大团的点集---dfs

例题：hdu 1530

#include<bits/stdc++.h>
    using namespace std;
    const int masn=2e6+10;
    int mp[55][55],n;
    vector<int> best;
    vector<int> a;
    void dfs(int pos)//下标 
    {
    	if(pos>=n+1)
    	{
    		if(best.size()<=a.size())
    		best=a;
    		return;
    	}
    	//判断是否可以在团内 
    	int flag=0;//表示可以 
    	for(int i=0;i<a.size();i++){
    		if(!mp[pos][a[i]])//注意：第二个方括号里面是a[i]
    		{
    			flag=1;//表示不可以 
    			break;
    		}
    	}
    	if(a.size()+(n-pos)>=best.size()){//剪枝操作  有可能a元素比best多就进行
    		if(!flag){
    			a.push_back(pos);
    			dfs(pos+1);//尝试插入该点 
    			a.pop_back();
    		}
    		dfs(pos+1);//尝试不插入该点 
    	}
    }
    int main()
    {
    	while(~scanf("%d",&n)&&n){
    	a.clear();
    	best.clear();
    	for(int i=1;i<=n;i++)
    	for(int j=1;j<=n;j++)
    	{
    		scanf("%d",&mp[i][j]);
    	}
    	dfs(1);
    	cout<<best.size()<<endl;
       }
    }

[https://blog.csdn.net/westbrook1998/article/details/82933263][https_blog.csdn.net_westbrook1998_article_details_82933263]

[https://blog.csdn.net/SparkFucker/article/details/83051133][https_blog.csdn.net_SparkFucker_article_details_83051133]

[https://www.cnblogs.com/yefeng1627/archive/2013/03/31/2991592.html][https_www.cnblogs.com_yefeng1627_archive_2013_03_31_2991592.html]

[https://ac.nowcoder.com/acm/problem/19790][https_ac.nowcoder.com_acm_problem_19790]

## Bron-Kerbosch 算法 ##

讲解的非常好：[https://www.cnblogs.com/yefeng1627/archive/2013/03/31/2991592.html][https_www.cnblogs.com_yefeng1627_archive_2013_03_31_2991592.html]

转载于:https://www.cnblogs.com/Aiahtwo/p/11437031.html

[https_blog.csdn.net_SparkFucker_article_details_83051133]: https://blog.csdn.net/SparkFucker/article/details/83051133
[1445562-20190831152852173-382571914.png]: /images/20230810/a25de32bc285414795dcc4b91c97a2aa.png
[https_blog.csdn.net_yafeichang_article_details_53888866]: https://blog.csdn.net/yafeichang/article/details/53888866
[https_blog.csdn.net_yafeichang_article_details_53893120]: https://blog.csdn.net/yafeichang/article/details/53893120
[https_blog.csdn.net_pi9nc_article_details_9632621]: https://blog.csdn.net/pi9nc/article/details/9632621
[https_blog.csdn.net_qq_40859951_article_details_88540146]: https://blog.csdn.net/qq_40859951/article/details/88540146
[https_blog.csdn.net_westbrook1998_article_details_82933263]: https://blog.csdn.net/westbrook1998/article/details/82933263
[https_www.cnblogs.com_yefeng1627_archive_2013_03_31_2991592.html]: https://www.cnblogs.com/yefeng1627/archive/2013/03/31/2991592.html
[https_ac.nowcoder.com_acm_problem_19790]: https://ac.nowcoder.com/acm/problem/19790