一、一些相关概念
1、二分图的概念：
二分图又称作二部图，是图论中的一种特殊模型。
设G=(V,E)是一个无向图。
如果顶点集V可分割为两个互不相交的子集X和Y，并且图中每条边连接的两个顶点一个在X中，另一个在Y中，则称图G为二分图。
2、判断二分图的方法：
一个图是连通的，可以用如下的方法判定是否是二分图：
（1）在图中任选一顶点v，定义其距离标号为0，然后把它的邻接点的距离标号均设为1，接着把所有标号为1的邻接点均标号为2（如果该点未标号的话），以此类推。
（2）标号过程可以用一次BFS实现。标号后，所有标号为奇数的点归为X部，标号为偶数的点归为Y部。
（3）接下来，二分图的判定就是依次检查每条边，看两个端点是否是一个在X部，一个在Y部。
如果一个图不连通，则在每个连通块中作判定。
3、二分图匹配的概念：
图中所示为一个最大匹配，也是完备匹配，但不是完美匹配。
给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
图中红色的边是数量为2的匹配。
4、最大匹配的概念：
选择边数最大的子图M称为图的最大匹配问题
若二分图X部的每一个顶点都与Y中的一个顶点匹配，并且Y部中的每一个顶点也与X部中的一个顶点匹配，则该匹配为完美匹配。
如果一个二分图，X部中的每一个顶点都与Y部中的一个顶点匹配，
或者
Y部中的每一个顶点也与X部中的一个顶点匹配，则该匹配为完备匹配。
5、增广路径的概念：
设M为二分图G已匹配边的集合，若P是图G中一条连通两个未匹配顶点的路径（P的起点在X部，终点在Y部，反之亦可），并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。
增广路径是一条“交错轨”。也就是说,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有参与匹配......最后一条边没有参与匹配,并且起点和终点还没有被选择过。
如图，增广路径为C->I->E->F->A->H。
那么，增广路径有什么用呢？我们发现，把增广路径的所有边取反（即匹配的变成未匹配，未匹配的边成匹配），
则子图M的边数会加1，当找不到增广路径时，这就是最大匹配了。
6、增广路径的性质：
(1)增广路径的长度必定为奇数，第一条边和最后一条边都不属于M，因为两个端点分属两个集合，且未匹配。
(2)把一条增广路径经过取反操作可以得到一个更大的匹配M’。
(3)M为G的最大匹配当且仅当不存在相对于M的增广路径。
7、匈牙利算法：
算*廓：
(1)置M为空
(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M
(3)重复(2)操作直到找不出增广路径为止
我们采用DFS的办法找一条增广路径：
从X部一个未匹配的顶点u开始，找一个未访问的邻接点v（v一定是Y部顶点）。对于v，分两种情况：
(1)如果v未匹配，则已经找到一条增广路
(2)如果v已经匹配，则取出v的匹配顶点w(w一定是X部顶点)，边(w,v)目前是匹配的，根据“取反”的想法，要将(w,v)改为未匹配，(u,v)设为匹配，能实现这一点的条件是看从w为起点能否新找到一条增广路径P’。如果行，则u-v-P’就是一条以u为起点的增广路径。
代码：（有许多写法）int w[202][202],cx[202],cy[202],nx,ny;
bool visit[202];
bool dfs(int u)
{
for(int i=1;i<=w[u][0];i++){
int v=w[u][i];
if(visit[v]==0){
visit[v]=1;
if(cy[v]==-1||dfs(cy[v])){
cx[u]=v;cy[v]=u;
return true;
}
}
}
return false;
}
int maxmatch()
{
int ans=0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
for(int i=0;i<=nx;i++){
if(cx[i]==-1){
memset(visit,0,sizeof(visit));
ans+=dfs(i);
}
}
return ans;
}
8、匈牙利算法的时空分析：
时间复杂度：
找一次增广路径的时间为：
邻接矩阵： O(n^2)
邻接表：O(n+m)
总时间：
邻接矩阵：O(n^3)
邻接表：O(n*m)
空间复杂度：
邻接矩阵：O(n^2)
邻接表： O(m+n)
二、几个有关结论
1、最少点覆盖集的点数就是最大匹配数M。
2、最少边
覆盖集的边数=总边数-最大匹配数
3、最大独立集点数=总点数-最大匹配数