二分图
二分图
一张无向图的节点可以分成两个集合,同一个集合的节点直接相互没有边,只有不同集合的节点之间才有边,则这张图被称为二分图
在一些特别的模型中,图是否是二分图决定了这张图是否有一些良好的性质
一个小定理:一个图是二分图当且仅当不存在长度为奇数的环
如果一张图存在奇环,那这个环上的点一定不能分成两个集合,每个集合之间都没有边
如果一张图不存在奇环,任选一个点染黑,黑点相邻的点都染白,白点周围的点都染黑,最后黑点和白点就可以构成二分图的两个点集。
用这种染色的方法,可以判断一张图是否是二分图。
给定一张
对每个连通块分别考虑:
总结一下,选出来的点相互之间不能有连边,不妨将选出来的点作为一个集合,其他点作为另一个集合,可以发现这是一个二分图。
先用染色法判断这个连通块是不是二分图
bool dfs(int now,int c)//当前点是now 颜色是c
{
col[now]=c;
for(int t:eg[now])
{
if(col[t])
{
if(col[t]==col[now]) return 0;//相邻的两个点同色
continue;
}
dfs(t,c^1)//相邻点换一个颜色
}
}
2
3
4
5
6
7
8
9
10
11
12
13
如果它是二分图,那么在黑色点和白色点中选择数量较少的那个颜色。
二分图最大匹配
匹配
从图
选出的边数最多的一个集合叫做最大匹配
二分图最大匹配:从二分图中选出一个匹配,边的数量最多。
交错路
由于匹配要满足任意选中的两条边之间都没有公共端点,所以不可能有相邻两条边一同被选中为匹配边,但是为了匹配的数量尽可能大,选择匹配边时,在一条路径上(或者一个偶环)中,一个隔一条边有一条匹配边。
即在二分图中任意选择一条路径,一定是匹配边与非匹配边交错形成的。
这样形成的路径被称为交错路。
交错路要么奇数编号的路径全都是匹配边,要么偶数编号的路径全是匹配边。
增广路
如果一条交错路有奇数条边,但是所有偶数编号的边是匹配边,这就会导致匹配边比非匹配边少一条。
如果把所有匹配边和非匹配边翻转(奇数编号变成匹配边,偶数编号变成非匹配边),这样就会多一条匹配边。
这样的路径,称为增广路,你也可以认为他叫可以增广的交错路。
现在最经典的求二分图最大匹配的算法,就是增广路算法。
因为一个端点只能在一个匹配里,所以也肯定只能让匹配增加一。
从左侧每一个端点出发,寻找是否存在增广路,若找到,则令匹配
两个定理
如果你想要更严谨的证明,看下面,否则可以跳过这两个定理
定理一:
若二分图未达到最大匹配,则一定存在增广路
证明:
设当前匹配集合为
(
则
那么点的度数只能是一或者二。
连通块要么是一个长度为偶数的环,要么是一条链,且
因为
定理二:
从某一个点
证明:
设
增广路要求结尾为
增广路算法
设左侧节点集合为
以每个未匹配的左侧节点为起点寻找增广路(保证了第一条是非匹配边),同时记录每个右侧节点有没有被匹配上。
如果没有被匹配上,则找到了
否则进行与右侧节点相匹配的左侧节点继续寻找
int tim=0;
int vis[N];
bool find(int now)
{
if(vis[now]==tim) return 0;//在这一轮寻找中来过这个点,且没找到,就不用再来了
vis[now]=tim;
for(int t:eg[now])
{
if(!f[t]||find(f[t]))//没有匹配边或者
{
f[t]=now;
return 1;
}
}
return 0;
}
for(int i=1;i<=n;++i)
{
++tim;
if(find(i)) ++ans;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
增广路算法在一般图上的应用
给定一张图,有
给每条边规定一个方向,使得定向之后,节点
最小化
设每条边连接节点
先默认边从
若
将这条路径上的所有边调转反向,就可以令
它虽然不叫增广路,但是和二分图增广路算法的实现有异曲同工之妙
bool dfs(int now)
{
if(vis[now]) return 0;
if(d[now]<a[now]) return 1;
vis[now]=1;
for(int t:eg[now]) //遍历now为起点,t为终点的边
{
if(dfs(t))//如果找到了一条路径
{
--d[now];
++d[t];
return 1;
}
}
return 0;
}
for(int i=1;i<=m;++i)
{
int u,v;cin>>u>>v;
eg[v].push_back(u);//实际上应该插入u到v的边,但是为了操作将v到u的反向边插入
++d[v];
memset(vis,0,sizeof(vis));
if(d[v]>a[v])
{
dfs(v);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
棋盘问题
问这张棋盘能否用
将棋盘视为黑白相间的格子
那么一张
其实这张棋盘就可以看作二分图染色后的结果,所以它一定是二分图,黑格子和白格子是两个点集,相邻的两个格子之间有一条边。
那么完全覆盖需要两个条件:
1、黑格子和白色格子数量相等
2、二分图最大匹配数量等于黑格子数
二分图最小点覆盖
覆盖
选择一些节点,使得在图上每条边都至少有一个端点被选中,则这个点集被称为覆盖
最小点覆盖:点数最少的覆盖
König 定理
二分图中,最小点覆盖数量=最大匹配
构造证明:
先跑一个二分图最大匹配
匹配边的两个端点被称为匹配点。
首先最小点覆盖数量至少 >= 最大匹配,因为每条匹配边都需要选至少一个端点去覆盖。
从左侧的每一个非匹配点出发走交错路,将访问过的所有点打标记,将这个集合称为
所以在这些连通块中,任意一条边都连接着右侧的标记点,所以右侧所有的标记点可以覆盖所有的边。
左侧不属于
即左侧所有未标记点和右侧所有标记点组成二分图的一个匹配。
这些点都恰好是一条匹配边的端点,所以数量上恰好等于最大匹配。
P7368 [USACO05NOV] Asteroids G
二分图最大独立集
独立集
在图中选最多的点出来,使得点两两之间没有连边
二分图最大独立集=n-最小点覆盖
在最小点覆盖中,任意一条边都至少有一个点被选中,在它的补集中,没有两个点共享一条边,且数量最多
霍尔定理
一个二分图,左侧有
二分图最大匹配数为
必要性:显然,如果右侧小于
充分性:当
当