二分图

二分图匹配的模型有两个要素
1.节点能分成独立的两个集合,每个集合内部有$0$条边
2.每个节点只能与一条匹配边相连

定义

如果一张无向图的$N$个节点$(N \ge 2)$可以分成$A,B$两个非空集合,其中$A \bigcap B = \emptyset$,并且在统一集合内的点之间没有边相连,那么称这张无向图为一张二分图.

判定

一张无向图是二分图,当且仅当图中不存在奇环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//伪代码
//尝试用黑白两色标记每个点
//一个点相邻的所有点的颜色都与其相反
//如果搜索时产生冲突,则图不为二分图
void dfs(int node, int col){
color[node] = col;
for(int i = head[node]; i; i = ne[i]){
if(color[To = to[i]] == 0){
color[To] = 3 - col;
dfs(To);
}else if(color[To] == col){
printf("False");
exit(0);
}
}
}
int main(){
...
for(int i = 1; i <= n; ++ i){
if(! color[i]) dfs(i);//注意图不连通的可能性
}
}

具体用法见关押罪犯

最大匹配

满足任意两条边都没有公共端点的边的集合被称为图的一组匹配
其中,包含边数最多的一组匹配被称为二分图最大匹配
如果在二分图中存在一条连接两个非匹配点的路径,使得非匹配边和匹配边在路径上交替出现,那么称这条路径为增广路
可以看出,如果把一条增广路上的所有边的状态取反,那么新得到的边集仍然是一组匹配,并且匹配边数增加了1
进一步得到推论:

二分图的一组匹配$S$是最大匹配,当且仅当图中不存在$S$的增广路

二分图匹配的模型有两个要素
1.节点能分成独立的两个集合,每个集合内部有$0$条边
2.每个节点只能与一条匹配边相连

  • 匈牙利算法

主要思想是在图中不断寻找增广路,直至不存在增广路为止
依次尝试给每一个左部节点$x$寻找一个匹配的右部节点$y$
匹配的条件有两个,满足其一即可
①$y$是非匹配点
②$y$是匹配点,但从$y$的匹配点$x’$能找到一个$y’$与之相匹配

程序

1
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
bool dfs(int node){
for(int i = head[node]; i; i = ne[i]){
int To = to[i];
if(!vis[To]){
vis[To] = 1;
if(!match[To] || dfs(match[To])){
match[To] = node;
return true;
}
}
}
return false;
}

int main(){
n = read(), m = read(), e = read();
for(int i = 1, u, v; i <= e; ++ i){
u = read(), v = read();
add(u, v);//要记得是单向边,因为右边点的匹配是被动的啊
}
for(int i = 1; i <= n; ++ i){
memset(vis, 0, sizeof(vis));//每一次都要初始化vis数组
if(dfs(i)) ++ ans;//一点最多连一边
}
printf("%d", ans);
return 0;
}
多重匹配 & 带权匹配

详见网络流