二分图

二分图的判定

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

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的点最多