二分图
Darkness_
2018-03-07 13:24:30
### 二分图的概念
二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。（源自[百度-二分图](https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E5%9B%BE/9089095?fr=aladdin)）
如上图就是一个标准的二分图。
### 最大匹配与增广路的概念
给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。(源自[百度-二分图匹配](https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E5%9B%BE%E5%8C%B9%E9%85%8D/9089174?fr=aladdin))
最大匹配即是选择其中边数最大的子集的图。
完全匹配，也叫做完备匹配，即某个匹配中，每个顶点都和某条边相关联。
好的，现在介绍完一个基本概念，我们就要着手解决如何求解最大匹配的问题了。
若要找出二分图中的最大匹配，最朴素的方法就是找出所有的匹配并一一比较，但这种方法的时间复杂度是边数的指数级的，不能满足数据范围较大的问题。因此，我们需要找出一个更优的方法求解。
在寻找这更优的方法前，我们需要先了解增广路的概念：增广路，也称增广轨或交错轨。若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径(举例来说，有A、B集合，增广路由A中一个点通向B中一个点，再由B中这个点通向A中一个点……交替进行)。（源自[百度-增广路](https://baike.baidu.com/item/%E5%A2%9E%E5%B9%BF%E8%B7%AF/1332250?fr=aladdin)）
由增广路的定义我们可以推出下述三个结论：
1. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
2. 经过取反操作可以得到一个更大的匹配M’，边数为M的边数+1。
3. M为G的最大匹配当且仅当不存在相对于M的增广路径。
如图为一个二分图增广路集合。
### 匈牙利算法
匈牙利算法就是用增广路求最大匹配问题(由匈牙利数学家Edmonds于1965年提出)
算法的主要步骤为：
1. 将M设置为空；
2. 找出一条增广路径P，通过取反操作获得更大的匹配M’代替M；
3. 重复2操作直到找不出增广路径为止；
如上图，A-a,a-B,B-b,b-D是一个增广路集合。
那么如果在执行2操作时发现有冲突了怎么办？算法所采取的是一种称作“协商”的手段。关于“协商”这一部分的详解可以查看[匈牙利算法](http://blog.csdn.net/dark_scope/article/details/8880547)
下面给出匈牙利算法([洛谷P3386](https://www.luogu.org/problemnew/show/P3386))的代码
```cpp
/****************
Keep your dreams.
by Darkness_
****************/
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 1005
#define INF 0X3F3F3F3F
#define MOD 1000000007
#define QWQ puts("QWQ")
int read(int &x) {
x=0;
int f=1;
char ch=getchar();
while (ch<'0'||ch>'9') {
if (ch=='-')
f=-f;
if (ch==EOF)
return -1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
x=x*10+ch-48;
ch=getchar();
}
x*=f;
return 0;
}
int n,m,e,x,y,ans;
int con_x[MAXN],con_y[MAXN];
bool vis[MAXN],flag[MAXN][MAXN];
bool dfs(int x) {
for (int y=1;y<=m;y++)
if (flag[x][y]&&!vis[y]) {
vis[y]=true;
if (con_y[y]==-1||dfs(con_y[y])) {
con_x[x]=y;
con_y[y]=x;
return true;
}
}
return false;
}
void Maxmatch() {
memset(con_x,-1,sizeof(con_x));
memset(con_y,-1,sizeof(con_y));
for (int i=1;i<=n;i++)
//if (con_x[i]==-1)//此句应去除，不知道为什么会错（逃
{
memset(vis,false,sizeof(vis));
ans+=dfs(i);
}
}
int main() {
read(n);
read(m);
read(e);
for (int i=1;i<=e;i++) {
read(x);
read(y);
if (x>=1&&y>=1&&x<=n&&y<=m)
flag[x][y]=true;
}
Maxmatch();
printf("%d\n",ans);
return 0;
}
```
### 二分图中的其他性质
关于二分图中其他的性质有：
1. 二分图的最小顶点覆盖
最小顶点覆盖要求用最少的点(U或V中都行)，让每条边都至少和其中一个点关联。
Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。
2. DAG图的最小路径覆盖
用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点。
引理：DAG图的最小路径覆盖数=节点数(n)-最大匹配数(m)
3. 二分图的最大独立集
在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值。
引理：二分图的最大独立集数 = 节点数(n)—最大匹配数(m)
关于二分图匈利亚算法的介绍就到这里告一段落了，但其实更重要的是建立模型，而这就需要多做题目来找到感觉了。
祝大家Rp++！
--------
在HDU上做一道二分图的题目时[here](http://acm.hdu.edu.cn/showproblem.php?pid=5943)，出现了莫名奇妙的错误，在经过对拍之后，发现此模板对于某一些奇怪的数据存在一定的差错，Maxmatch函数中的一句语句应去除，具体已在代码中注释（顺便改了一下代码格式hhhh）。
P.S.:我把两种写法的二分图对拍了一下，发现没有什么错误。不知道是为什么……痛苦万分
不过以后还是去掉吧……也许就有什么毒瘤数据呢了……