文章目录
二分图的定义
如果我们能将一个无向图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。
或者说：
如果一个无向图的N个节点(N>=2)可以分成
V
1
V1
V1，
V
2
V2
V2两个非空集合，其中
①
V
1
∩
V
2
=
∅
V1\cap V2 = \empty
V1∩V2=∅
② 同一集合中的两个点之间没有边相连。
那么称这个无向图是一个二分图。
二分图的判定定理
一 张 无 向 图 是 二 分 图 ⟺ 图 中 不 存 在 奇 数 环 （ 长 度 为 奇 数 的 环 一张无向图是二分图\iff 图中不存在奇数环（长度为奇数的环 一张无向图是二分图⟺图中不存在奇数环（长度为奇数的环
二分图的判断准则
-
染色法：
一张无向图是二分图，当且仅当，对图中的每个顶点进行染色， 染成黑色或白色中的一种，如果能够使得没有两个相邻的顶点染成同样的颜色。 -
简单证明
必要性：
如果是二分图，那么对两个独立点集 V 1 , V 2 V1,V2 V1,V2分别染成一种颜色即可。
充分性：
将点根据颜色不同分成两个集合，每个集合中点的颜色相同即可。
算法流程
① 尝试对图中的每个点进行染色，然后尝试对它的所有相连的点染成相反的颜色，如果出现颜色冲突，表明不是二分图。
② 重复进行①步骤，知道所有的点都被染色。
一般用深搜去实现：
void dfs(int x,int color){
vis[x] = color;
扫描x的所有相邻点 y;
if(vis[y] ==0 )
dfs(y,3,color);
else if(vis[y]==color)
算法结束，不是二分图
}
bool check(){
for(int i=1;i<=n;i++){
如果已经判定不为二分图
return false;
if(vis[i]==0){
dfs(x,1);
}
}
return true;
}
二分图的判定还可以使用宽度优先搜索完成，代码暂略。
算法思想如下：
任选一个起点，进行BFS，存在奇数环的充要条件是存在某个层次的节点中至少有两个节点间存在边。
二分图的匹配
二分图的匹配：给定一个二分图 G，在 G 的一个子图 M 中，M 的边集 {E} 中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
参考
二分图的最大匹配 (裸题) 匈牙利算法
这个也戏称为找老婆算法。