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

讲解的博客:https://blog.csdn.net/SparkFucker/article/details/83051133

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

定义 (*):

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

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

定义(*):

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

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

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

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

求解方法:

一.暴力法求最大团的点集---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;
   }
}

  

Bron-Kerbosch 算法

 

上一篇:PCL采样一致性算法


下一篇:基于遗传算法的多种运输工具或带时间窗的路径优化问题(VRP)的求解(MATLAB)