二分图及相关问题整理

计算匹配问题经常需要使用一个可增广路径的概念。

设 M 是二分图的一个匹配，将 M 中的边所关联的节点称为盖点，其余节点称为未盖点。

若一条路径上属于 M 的边和不属于 M 的边交替出现，则称该路径为一条交错轨(交替路)。

若路径 p 是一条起始点和结束点都是未盖点的交错轨，则称 p 为一条关于 M 的增广路经.即“从一个未匹配点出发，走交替路，以另一个未匹配点为结尾”。

若图存在增广路径，则 M 中的匹配边数增加1。为什么？

显然，图中不存在增广路径时匹配边数是最多的。

（摘自 zhq 老师 ppt）

每次找关于 M 的增广路径，然后交替取舍，就可以比原先的匹配多出一条匹配边。

重复此操作，直至二分图中不存在关于 M 的可增广路径为止。此时得到的匹配 M 就是G的一个最大匹配。

int check(int u) { //u它是X集合中的点
for(int i = 0; i < G[u].size(); i++){ //枚举Y中与U相连的点
int v= G[u][i];
if(!vis[v]){ //标记是否访问过
vis[v] = 1;
if(link[v] == -1 || check(link[v])){//找到Y中未盖点，或，
//如果这点被配对过，那么就从这点配对的X中的点进行新一轮的check()
link[v] = u; //深搜回溯时，取反
return 1;
}
}
}
return 0;
}
int get_maxmatch(){
int num = 0;
for(int i = 1; i <= n; i++){
memset(vis, 0, sizeof(vis));
if(check(i)){
num++; //找到增广路径，num+1
}
}
return num;
}



匹配：在 G 中两两没有公共端点的边集合。

边覆盖：G 中的任意顶点都是边集合 F 中某条边的端点。即最小的边能覆盖所有顶点。

独立集：在 G 中两两互不相联（没有直接连接两者的路径）的顶点集合。

顶点覆盖：G 中任意边都有至少一个端点属于顶点集合 S。

最小点覆盖

• |最大独立集|+|最小顶点覆盖|=|V|

  
  



• 对于二分图，|最大匹配|=|最小顶点覆盖|

  
  

例：

在 N* N 的格子中，有一些小行星，Bessie 有一把枪，能一次消灭一行或一列的行星，求最少需要多少子弹。

解：

把每行每列各看成一个节点，把一颗小行星的坐标

(x,y)

\text{(x,y)}

(x,y) 看成一条 x 到 y 的边。建完图后，题目就变成找到最少的点，使得这些点与所有的边相邻，即最小点覆盖问题。

最大独立集

• |最大独立集|+|最小顶点覆盖|=|V|

例：

老师带学生出去旅游，但出于特殊的考虑，带出去的学生至少要满足以下要求之中的一个：1.两人身高相差超过40CM；2.同性别；3.喜欢的音乐风格不同； 4.喜欢的运动相同。问最多可以带出去多少学生？

解：

最大独立集：最大的一个集合，其中的每两点之间都不存在边。

首先，根据性别把学生分成男，女两部分。将身高差少于40CM且喜欢音乐相同且喜欢运动不同的男女连边，那么可以带出去的人数应该等于这个二分图的最大独立集。

最大独立集=顶点数（包括X和Y)-最大匹配(利用匈牙利算法)

最小边覆盖

• 对于不存在孤立点的图，|最大匹配|+|最小边覆盖|=|V|（总点数）

例：

一个地图上有 n 个小镇，以及连接着其中两个小镇的有向边，而且这些边无法形成回路。现在选择一些小镇空降士兵（1 个小镇最多 1 个士兵），士兵能沿着边走到尽头，问最少空降几个士兵，能遍历完所有的小镇。

解：

匈牙利算法求最小路径覆盖：

1. 在一个有向图中，路径覆盖就是在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联。

   
   



2. 如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次。

   
   



3. 解决此类问题可以建立一个二分图模型。把所有顶点i拆成两个：X 结点集中的 i 和 Y 结点集中的 i’,如果有边 i->j，则在二分图中引入边 i->j’，设二分图最大匹配为 m,则结果就是 n-m。

   
   

求二分图权值和最大（小）完美匹配

• 完美匹配

  若二分图 X 部的每一个顶点都与 Y 中的一个顶点匹配，并且 Y 部中的每一个顶点也与 X 部中的一个顶点匹配，则该匹配为完美匹配。

  一对一，所有顶点都匹配，并且 X 部和 Y 部顶点数一样。

  
  



• 完备匹配

  若二分图 X 部的每一个顶点都与 Y 中的一个顶点匹配，或者 Y 部中的每一个顶点与 X 部中的一个顶点匹配，则该匹配为完备匹配。

  匹配数 = min(|X|,|Y|), |X| 表示 X 部的点数，|Y| 表示 Y 部的点数。

  X 部和 Y 部顶点数可能不一样。

  
  



• 最佳匹配

  带权二分图的权值和最大的匹配称为最佳匹配。

  
  

KM 算法

对于每个左部点

i

i

i，右部点

j

j

j，都有

l

x

i

lx_i

lxi​ 和

l

y

j

ly_j

lyj​，表示它们的顶标，保证对于所有的

i

∈

l

e

f

t

,

j

∈

r

i

g

h

t

i \in left,\ j \in right

i∈left, j∈right，都有

l

x

i

+

l

y

j

>

=

w

i

,

j

lx_i+ly_j>=w_{i,j}

lxi​+lyj​>=wi,j​。

而 KM 算法就是，每次都选取

l

x

i

+

l

y

j

=

w

i

,

j

lx_i + ly_j=w_{i,j}

lxi​+lyj​=wi,j​ 的左部点和右部点，构成相等子图，然后看当前子图是否有增广路径，即每个当前左部点都有对应的匹配的右部点。

若有，那么接着去匹配下一个左部点；若没有，则更改顶标。

每次对于遍历过的左部点，都加上更新值，右部点则减去。

更新值的获取方式见代码，作用就是让尽可能少地让新的边可以加入匹配，尝试是否可行。

#include
using namespace std;
#define int long long
#define maxn 105
#define maxm 20005
#define rep(i, a, b) for(int i = a; i <= b; ++i)
int n, c[maxn][maxn];
bool s[maxn], t[maxn];
int lx[maxn], ly[maxn], mtc[maxn];
int ans1, ans2;
inline bool dfs(int u)
{
s[u] = 1;//将遍历过的左部点记录下
rep(v, 1, n) if(!t[v]/*没有遍历过该右部点*/ and lx[u] + ly[v] == c[u][v]/*能够匹配*/)
{
t[v] = 1;//标记
if(!mtc[v] or dfs(mtc[v]))
{
mtc[v] = u;
return true;
}
}
return false;
}
inline void updt()
{
int d = 2147483647;
rep(i, 1, n) if(s[i])
rep(j, 1, n) if(!t[j]) d = min(d, lx[i] + ly[j] - c[i][j]);//寻找最小更新值
rep(i, 1, n)
{
if(s[i]) lx[i] -= d;//左部点顶标值减去更新值
if(t[i]) ly[i] += d;//右部点顶标值加上更新值
}
}
inline void KM()
{
rep(i, 1, n) mtc[i] = lx[i] = ly[i] = 0;//初始清空
rep(i, 1, n) rep(j, 1, n)
lx[i] = max(lx[i], c[i][j]);//初始顶标
rep(i, 1, n) while(1)
{
rep(i, 1, n) s[i] = t[i] = 0;//清空记录路径的数组
if(dfs(i)) break;//如果找到当前图的增广路径，或当前点有匹配
else updt();//没有匹配则更新顶标，重新尝试匹配
}
}
signed main()
{
scanf("%lld", &n);
rep(i, 1, n) rep(j, 1, n)
scanf("%lld", &c[i][j]);
KM();
rep(i, 1, n) ans1 += lx[i] + ly[i];//答案即为所有的顶标值之和
rep(i, 1, n) rep(j, 1, n) c[i][j] *= -1;//取反求最小值
KM();
rep(i, 1, n) ans2 += lx[i] + ly[i];
printf("%lld\n%lld\n", -ans2, ans1);
return 0;
}


以上内容整理自 zhq 老师《二分图》PPT，并作补充。