一、基本概念
二分图：二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
二分图判断： 当且仅当无向图G的每一个回路的次数均是偶数时，G才是一个二分图。如果无回路，相当于任一回路的次数为0，故也视为二分图。
二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
极大匹配(Maximal Matching)：是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
交替路径：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
增广路径：设M为二分图G已匹配边的集合，若P是图G中一条连通两个未匹配顶点的路径（P的起点在X部，终点在Y部，反之亦可），并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。
性质：
- P的路径长度必定为奇数，第一条边和最后一条边都不属于M，因为两个端点分属两个集合，且未匹配。
- P经过取反操作可以得到一个更大的匹配M’。
- M为G的最大匹配当且仅当不存在相对于M的增广路径。
完美匹配：如果一个二分图，X部和Y部的顶点数相等，若存在一个匹配包含X部与Y部的所有顶点，则称为完美匹配。
完备匹配：如果一个二分图，X部中的每一个顶点都与Y部中的一个顶点匹配，**或者**Y部中的每一个顶点也与X部中的一个顶点匹配，则该匹配为完备匹配。
最佳匹配：带权二分图的权值最大的完备匹配称为最佳匹配。二分图的最佳匹配不一定是二分图的最大权匹配。
最小点覆盖：对于图G=(V,E)中的一个点覆盖是一个集合S⊆V使得每一条边至少有一个端点在S中。
最小边覆盖：边覆盖是图的一个边子集，使该图上每一节点都与这个边子集中的一条边关联，只有含孤立点的图没有边覆盖，边覆盖也称为边覆盖集，图G的最小边覆盖就是指边数最少的覆盖，图G的最小边覆盖的边数称为G的边覆盖数。
最大独立集：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边的点中，m的最大值。
最小路径覆盖：在一个有向图中，找出最少的路径，使得这些路径经过了所有的点。
二、性质
定理：当且仅当无向图G的每一个回路的次数均是偶数时，G才是一个二分图。如果无回路，相当于任一回路的次数为0，故也视为二分图。
Konig 定理：一个二分图中的最大匹配数等于这个图中的最小点覆盖数。
证明：首先，我们要抓住二分图最大匹配后的特点，此时，不存在增广路。如上图所示，该图为不完整的最大匹配后二分图。
红点为匹配点，蓝点未匹配。
对于一个点而言，他所连接的有这三种情况：
1、只连接了红点；
2、只连接了蓝点；
3、连接了红点和蓝。
在上面的图中，x与y所连接的边是匹配边。x连接了红点和蓝点， 这个时候y所连接的点一 所连接的点一定没有蓝点，如果有，就是一条新的增广路那么该图就不是最大匹配了。
在最大匹配图中不会出现一条边同时连接着两个蓝点。那么，对于一条边而言只有两种情况：1、两端的点是红点；
2、两端的点一个红色，一个蓝色。
可知，一条边上，一定有红点，那么我们就选择红点作为覆盖点。
对于上面的匹配边xy，我们无论是选择x还是y都可以覆盖xy这条边， 但是对于图中的蓝点而言这条边， 但是对于图中的蓝点而言这条边， 但是对于图中的蓝点而言这条边， 但是对于图中的蓝点而言这条边，只能选择x作为覆盖点去覆盖那条边，这样，我们就选择x作为覆盖点，它所覆盖的边中既包括了与他相连的那些蓝点的边，也包括了xy这条匹配边。因为y点没有蓝色连接点，所以y不是必须选择的覆盖点，它与那些红点相连的边都可以选择那些红点来覆盖。所以，对于一条匹配边而言，我们只需要选择其中一个点就可以覆盖完整个二分图里的边了。
所以最小覆盖点数等于大匹配数。
三、基本问题
（1）二分图判断
如果一个图是连通的，可以用如下的方法判定是否是二分图：
在图中任选一顶点v，定义其距离标号为0，然后把它的邻接点的距离标号均设为1，接着把所有标号为1的邻接点均标号为2（如果该点未标号的话），如图所示，以此类推。
标号过程可以用一次BFS实现。标号后，所有标号为奇数的点归为X部，标号为偶数的点归为Y部。
接下来，二分图的判定就是依次检查每条边，看两个端点是否是一个在X部，一个在Y部。
如果一个图不连通，则在每个连通块中作判定。
（2）二分图的最大匹配
选择边数最大的子图称为图的最大匹配问题(maximal matching problem) 。如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
图中所示为一个最大匹配，但不是完全匹配。
算法：匈牙利算法
匈牙利算法
用增广路求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出)
算***廓：
- 置M为空
- 找出一条增广路径P，通过取反操作获得更大的匹配M’代替M
- 重复2操作直到找不出增广路径为止
找增广路径的算法
我们采用DFS的办法找一条增广路径：
从X部一个未匹配的顶点u开始，找一个未访问的邻接点v（v一定是Y部顶点）。对于v，分两种情况：
- 如果v未匹配，则已经找到一条增广路
- 如果v已经匹配，则取出v的匹配顶点w(w一定是X部顶点)，边(w,v)目前是匹配的，根据“取反”的想法，要将(w,v)改为未匹配，(u,v)设为匹配，能实现这一点的条件是看从w为起点能否新找到一条增广路径P’。如果行，则u-v-P’就是一条以u为起点的增广路径。
//伪代码
//cx[i]表示与X部i点匹配的Y部顶点编号
//cy[i]表示与Y部i点匹配的X部顶点编号
bool dfs(int u)//寻找从u出发的增广路径
{
for each v∈u的邻接点
if(v未访问){
标记v已访问;
if(v未匹配||dfs(cy[v])){
cx[u]=v;
cy[v]=u;
return true;//有从u出发的增广路径
}
}
return false;//无法找到从u出发的增广路径
}
//代码
bool dfs(int u){
for(int v=1;v<=m;v++)
if(t[u][v]&&!vis[v]){
vis[v]=1;
if(cy[v]==-1||dfs(cy[v])){
cx[u]=v;cy[v]=u;
return 1;
}
}
return 0;
}
void maxmatch()//匈牙利算法主函数
{
int ans=0;
memset(cx,0xff,sizeof cx);
memset(cy,0xff,sizeof cy);
for(int i=0;i<=nx;i++)
if(cx[i]==-1)//如果i未匹配
{
memset(visit,false,sizeof(visit)) ;
ans += dfs(i);
}
return ans ;
}
算法分析
算法的核心是找增广路径的过程DFS
对于每个可以与u匹配的顶点v，假如它未被匹配，可以直接用v与u匹配；
如果v已与顶点w匹配，那么只需调用dfs(w)来求证w是否可以与其它顶点匹配，如果dfs(w)返回true的话，仍可以使v与u匹配；如果dfs(w)返回false,则检查u的下一个邻接点…….
在dfs时，要标记访问过的顶点（visit[j]=true），以防死循环和重复计算；每次在主过程中开始一次dfs前，所有的顶点都是未标记的。
主过程只需对每个X部的顶点调用dfs，如果返回一次true，就对最大匹配数加一；一个简单的循环就求出了最大匹配的数目。
时空分析
时间复杂度：
- 找一次增广路径的时间为：
邻接矩阵： O(n^2)
邻接表：O(n+m)
- 总时间：
邻接矩阵：O(n^3)
邻接表：O(nm)
- 空间复杂度：
邻接矩阵：O(n^2)
邻接表： O(m+n)
（3）二分图的最佳匹配（二分图的带权最大匹配）
算法：KM算法。（可以用最小费用最大流做）
KM算法
求二分图的最佳匹配有一个非常优秀的算法,可以做到O(N^3),这就是KM算法。该算法描述如下：
1.首先选择顶点数较少的为X部，初始时对X部的每一个顶点设置顶标，顶标的值为该点关联的最大边的权值，Y部的顶点顶标为0。
2.对于X部中的每个顶点，在相等子图中利用匈牙利算法找一条增广路径，如果没有找到，则修改顶标，扩大相等子图，继续找增广路径。当每个点都找到增广路径时，此时意味着每个点都在匹配中，即找到了二分图的完备匹配。该完备匹配即为二分图的最佳匹配。
什么是相等子图呢？因为每个顶点有一个顶标，如果我们选择边权等于两端点的顶标之和的边，它们组成的图称为相等子图。
如果从X部中的某个点Xi出发在相等子图中没有找到增广路径，我们是如何修改顶标的呢？如果我们没有找到增广路径，则我们一定找到了许多条从Xi出发并结束于X部的匹配边与未匹配边交替出现的路径，姑且称之为交错树。我们将交错树中X部的顶点顶标减去一个值d，交错树中属于Y部的顶点顶标加上一个值d。这个值后面要讲它如何计算。那么我们会发现：
两端都在交错树中的边(i,j)，其顶标和没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。
两端都不在交错树中的边(i,j)，其顶标也没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。
X端不在交错树中，Y端在交错树中的边(i,j)，它的顶标和会增大。它原来不属于相等子图，现在仍不属于相等子图。
X端在交错树中，Y端不在交错树中的边(i,j),它的顶标和会减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。
我们修改顶标的目的就是要扩大相等子图。为了保证至少有一条边进入相等子图，我们可以在交错树的边中寻找顶标和与边权之差最小的边,这就是前面说的d值。将交错树中属于X部的顶点减去d，交错树中属于Y部的顶点加上d。则可以保证至少有一条边扩充进入相等子图。
3.当X部的所有顶点都找到了增广路径后，则找到了完备匹配，此完备匹配即为最佳匹配。
相等子图的若干性质
- 在任意时刻，相等子图上的最大权匹配一定小于等于相等子图的顶标和。
- 在任意时刻，相等子图的顶标和即为所有顶点的顶标和。
- 扩充相等子图后，相等子图的顶标和将会减小。
- 当相等子图的最大匹配为原图的完备匹配时，匹配边的权值和等于所有顶点的顶标和，此匹配即为最佳匹配。
bool dfs(int s) //匈牙利算法找增广路径
{
visx[s]=1;
for(int i=1;i<=cnty;i++)
if(!visy[i]){
int t=wx[s]+wy[i]-dis[s][i];
if(t==0) {
visy[i]=1;
if(linky[i]==0||dfs(linky[i])){
linkx[s]=i,linky[i]=s;
return true;
}
}
else if(t>0) //找出边权与顶标和的最小的差值
{
if(t<minz)minz=t;
}
}
return false;
}
void km()
{
memset(linkx,0,sizeof linkx); //linkx[i]表示与X部中点i匹配的点
memset(linky,0,sizeof linky);
for(int i=1;i<=cntx;i++){
while(1){
minz=INF;
memset(visx,0,sizeof visx);
memset(visy,0,sizeof visy);
if(dfs(i))break;
for(int j=1;j<=cntx;j++) //将交错树中X部的点的顶标减去minz
if(visx[j])wx[j]-=minz;
for(int j=1;j<=cnty;j++) //将交错树中Y部的点的顶标加上minz
if(visy[j])wy[j]+=minz;
}
}
}
（4）二分图的最小点覆盖
二分图的最小点覆盖 = 二分图的最大匹配
证明：
按照定义所说，就是最大匹配中的每个匹配的一个节点就是最小点集。
如果有一条边的两个端点都不在EM中，那最大匹配就会变成|M|+1，产生矛盾。所以又|最小点集|<=|最大匹配|
我们现在只看最大匹配M，如果最小点集小于M，那么肯定有边无法涉及到，因此|最小点集|>=|最大匹配|
所以有|最小点集|=|最大匹配|
对于一个一般图是NP Hard的问题，对于二分图可能就是多项式可解的问题咯
（5）二分图的最少边覆盖
二分图的最少边覆盖 = 点数 - 二分图的最大匹配
（6）二分图的最大独立集
二分图的最大独立集 = 点数 - 二分图的最大匹配
证明：
设最大独立集数为U，最大匹配数为M，M覆盖的顶点集合为EM。
为了证明|U|=|V|-|M|，我们分两步证明|U|<=|V|-|M|和|U|>=|V|-|M|
1 先证明 |U|<=|V|-|M|
M中的两个端点是连接的，所有M中必有一个点不在|U|集合中，所以|M|<=|V|-|U|
2 再证明|U|>=|V|-|M|
假设(x,y)属于M
首先我们知道一定有|U|>=|V|-|EM|，那么我们将M集合中的一个端点放入U中可以吗？
假设存在(a,x)，(b,y)，(a,b)不在EM集合中
如果(a,b)连接，则有一个更大的匹配存在，矛盾
如果(a,b)不连接，a->x->y->b有一个新的增广路，因此有一个更大的匹配，矛盾
所以我们可以了解到取M中的一个端点放入U中肯定不会和U中的任何一个点相连，所以|U|>=|V|-|EM|+|M|=|V|-|M|
所以，|U|=|V|-|M|
（7）有向无环图的最小路径覆盖
在一个有向图中，找出最少的路径，使得这些路径经过了所有的点。
最小路径覆盖分为最小不相交路径覆盖和最小可相交路径覆盖。
1、有向无环图的最小不相交路径覆盖
每一条路径经过的顶点各不相同。
算法：我们把原图中的点V拆成两个点Vx和Vy，对于原图中的边A−>B，我们在新图中连Ax−>By。
那么最小不相交路径覆盖=原图的点数-新图的最大匹配
证明：一开始每个点都是独立的为一条路径，总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了1。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。
//
// main.cpp
// POJ1422最小不想交路径覆盖
//
// Created by beMaster on 16/4/8.
// Copyright © 2016年 beMaster. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
const int N = 200 + 10;
vector<int> g[N];
int cy[N];
bool vis[N];
bool dfs(int u){
for(int i=0; i<g[u].size(); ++i){
int v = g[u][i];
if(vis[v]) continue;
vis[v] = true;
if(cy[v]==-1 || dfs(cy[v])){
cy[v] = u;
return true;
}
}
return false;
}
int solve(int n){
int ret = 0;
memset(cy, -1, sizeof(cy));
for(int i=1;i<=n;++i){
memset(vis, 0, sizeof(vis));
ret += dfs(i);
}
return n - ret;
}
int main(int argc, const char * argv[]) {
int t,n,m;
int u,v;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
g[i].clear();
for(int i=0;i<m;++i){
scanf("%d%d",&u,&v);
g[u].push_back(v);
}
int ans = solve(n);
printf("%d\n",ans);
}
return 0;
} 2、有向无环图的最小可相交路径覆盖
每一条路径经过的顶点可以相同。
算法：先用floyd求出原图的传递闭包， 如果a到b有路， 那么就加边a->b。 然后就转化成了最小不相交路径覆盖问题。
证明：为了连通两个点，某条路径可能经过其它路径的中间点。比如1->3->4，2->4->5。但是如果两个点a和b是连通的，只不过中间需要经过其它的点，那么可以在这两个点之间加边，那么a就可以直达b，不必经过中点的，那么就转化成了最小不相交路径覆盖。
//
// main.cpp
// POJ2594最小可相交路径覆盖
//
// Created by beMaster on 16/4/8.
// Copyright © 2016年 beMaster. All rights reserved.
//
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
const int N = 500 + 10;
bool dis[N][N];
bool vis[N];
int cy[N];
void floyd(int n){
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int k=1;k<=n;++k)
if(dis[i][k] && dis[k][j])//传递可达性
dis[i][j] = true;
}
bool dfs(int u, int n){
for(int i=1;i<=n;++i){
if(!vis[i] && dis[u][i]){
vis[i] = true;
if(cy[i]==-1 || dfs(cy[i], n)){
cy[i] = u;
return true;
}
}
}
return false;
}
int solve(int n){
int cnt = 0;
memset(cy,-1,sizeof(cy));
for(int i=1;i<=n;++i){
memset(vis,0,sizeof(vis));
cnt += dfs(i, n);
}
return n - cnt;
}
int main(int argc, const char * argv[]) {
int n,m;
int a,b;
while(scanf("%d%d",&n,&m),n+m){
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dis[i][j] = false;
for(int i=1;i<=m;++i){
scanf("%d%d",&a,&b);
dis[a][b] = true;
}
floyd(n);
int ans = solve(n);
printf("%d\n",ans);
}
return 0;
} 特别的，每个点自己也可以称为是路径覆盖，只不过路径的长度是0。
（8）有向无环图中最少不相交路径覆盖和最大独立集的相互转化
用偏序集，一般可以抽象为有向无环图。建议先看看这篇博客
Dilworth定理：有向无环图的最大独立集=有向无环图最少不相交路径覆盖
四、例题
http://acm.hdu.edu.cn/showproblem.php?pid=3478
http://acm.hdu.edu.cn/showproblem.php?pid=1083
http://acm.hdu.edu.cn/showproblem.php?pid=1150
http://acm.hdu.edu.cn/showproblem.php?pid=1151
http://poj.org/problem?id=1466
http://poj.org/problem?id=2594
https://www.lydsy.com/JudgeOnline/problem.php?id=1433
五、参考文章
https://blog.csdn.net/qq_38956769/article/details/80238896
https://blog.csdn.net/c20180630/article/details/70175814
https://blog.csdn.net/c20180630/article/details/71080521
https://blog.csdn.net/vocaloid01/article/details/81083071
京公网安备 11010502036488号