• 欢迎光临~

二分图

开发技术 开发技术 2022-10-07 次浏览

二分图的判定

不存在奇数环。
可以通过匈牙利算法,染色判定。

bool dfs(int x,int t)
{
	st[x]=t;
	for(int i=head[x];i;i=ne[i])
	{
		int y=ver[i];
		if(!st[y])
		{
			if(!dfs(y,3-t)) return 0;
		}
		else if(st[y]==st[x]) return 0;
	}
	return 1;
}

最大匹配 最坏O(N^2 M)

任意两条边都没有公共点的边的集合。

for(int i=1;i<=n;i++)
{
	memset(st,0,sizeof(st));
	if(find(i)) res++;
}

bool find(int x)
{
	for(int i=1;i<=n;i++)
	{
		if(!st[i]&&g[x][i])
		{
			st[i]=1;
			int t=match[i];
			if(t==0||find(t))
			{
				match[i]=x;
				return 1;
			}
		}
	}
	return 0;
}

最小点覆盖

定义:给定一张二分图用最少的点覆盖所有边。
定理:二分图的最小点覆盖等于最大匹配边数。


证明:最大匹配的边是二分图边集的一个子集,所以至少从匹配点中选择一个,只需要构造一组点覆盖,使得等于匹配边数即可。

从左边所有非匹配点出发,寻找增广路径并标记经过的点(必然失败,否则必然有更大的点匹配,即不可能经过右边的非匹配点),其到达的必然是右边的匹配点,并且一定能到达对应的左边的匹配点。

匹配点要么都经过,要么都不经过。

然后验证覆盖所有边。

取左边未标记的匹配点和右边标记过的匹配点,即可得到最大匹配。
所有匹配边都经过。我们从左边非匹配点出发,到达右边的匹配点,右边的非匹配点必然不能到达,所以非匹配边都被经过。

证毕。


最大独立集

定义:任意两点不能互相到达的点的最大集合
定理:最大独立集=n-最小点覆盖=n-最大匹配
最大独立集=删去最少的点,使得剩余的点没有边=删除最小点覆盖


有向无环图的最小路径点覆盖

定义:用最少的边覆盖所有点
定理:最小路径点覆盖=n-最小点覆盖=n-最大匹配

将有向无环图的点进行拆分,分为入点和出点,显然每个点的入度出度不超过1,最小路径点覆盖=图的出度为0的点最多

程序员灯塔
转载请注明原文链接:二分图
喜欢 (0)