二分图

发表于 更新于 分类于 ， ， 阅读次数： 本文字数： 367 阅读时长 ≈ 1 分钟

二分图

若一张无向图 GG，可以将所有的点分成 22 个点集，且 22 个点集内部没有连边，那么称 GG 可以划分为一张二分图。

  • 注意：二分图的划分不一定唯一，且不一定连通。有向图在实际问题中，也可以划分一分图

二分图存在的充要条件

  • 没有奇环

二分图的判定

染色法，任意选择没有访问的点开始 dfs，并且 0,10,1 交替染色，只要出现一条边的 22 个端点颜色相同，那么就不是二分图。

1
2
3
4
5
6
7
8
9
10
11
bool dfs(int x, int c)
{
	color[x] = c;
	for (auto& [nxt, w] : nbr[x])
		if (color[nxt] == c)
			return false;
		else if (!color[nxt])
			if (!dfs(nxt, 3 - c))
				return false;
	return true;
}

二分图最大匹配

对于一张无向图 GG，且 GG 可以划分为二分图，我们将 11 条边称为 11 组“匹配”，在 GG 中选出最多的匹配且所有选出的边不共点，那么这一组边集，就是一组 GG 的最大匹配。

匈牙利算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool hungary(int x)
{
	for (auto& [nxt, w] : nbr[x])
		if (!vis[nxt])
		{
			vis[nxt] = true;
			if (!match[nxt] || hungary(match[nxt]))
			{
				match[nxt] = x;
				return true;
			}
		}
	return false;
}

二分图最小点覆盖

对于一张二分图 GG，选取最小的点集 SS，使得点集内的点能覆盖所有的边。（在任意一条边至少有 11 个端点在 SS 中）

性质：

  • 二分图最大匹配=二分图最小点覆盖