定义
二分图 又称作二部图，是图论中的一种特殊模型。 设 ((G=(V,E))) 是一个无向图，如果顶点(V)可分割为两个互不相交的子集((U,V))，并且图中的每条边((i,j))所关联的两个顶点(i)和(j)分别属于这两个不同的顶点集，则称图(G)为一个二分图。
一个无向图为二分图的充要条件是没有奇环。
二分图染色
求解算法
思路
判定一个图是否为二分图，使用dfs进行黑白染色，判定能否满足每条边的两个顶点异色。
实现
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=10050,MAXM=10050;
int n,m,cnt,col[MAXN],head[MAXN],ans;
struct edge
{
int v,next;
}e[MAXM*2];
void addedge(int x,int y)
{
e[++cnt]=(edge){y,head[x]};
head[x]=cnt;
return;
}
bool dfs(int u,int x)
{
if(col[u])
{
if(col[u]==x)return true;
return false;
}
col[u]=x;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(!dfs(v,x==1?2:1))return false;
}
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
bool flag=true;
for(int i=1;i<=n;++i)
if(!col[i])
if(!dfs(i,1))
{
flag=false;
break;
}
flag?puts("Yes"):puts("No");
return 0;
}
二分图最大匹配
定义
又称最大边独立集，即边数最多的匹配。
有关概念
匹配：又称边独立集，一个边集，满足边集中的任两边不邻接。
极大匹配：又称极大边独立集，本身是匹配，加入任何边就不是。
增广路：连接两个未匹配结点的路径，且已匹配边和未匹配边在路径上交替出现，可以发现非匹配边的数量比匹配边的数量多(1)，故将路径上的每一条边取反就能使匹配边的数量(+1)。
求解算法
匈牙利算法
思路
- 在图中找出增广路；
- 对增广路上每一条边取反（即匹配边改为非匹配边，非匹配边改为匹配边）；
- 重复以上两步直到找不到增广路为止。
样例推导
给出二分图：
从(X1)开始，找到增广路(X1-Y1)，标记(X1-Y1)为匹配边；
从(X2)开始，找到增广路(X2-Y1-X1-Y3)；
标记(X1-Y1)为非匹配边，标记(X1-Y3,X2-Y1)为匹配边；
从(X3)开始，找到(X3-Y1-X2)，不是增广路；
找到增广路(X3-Y2)，标记(X3-Y2)为匹配边;
从(X4)开始，找到(X4-Y3-X1-Y1-X2)，不是增广路；
找到增广路(X4-Y4)，标记(X4-Y4)为匹配边。
至此找出最大匹配。
实现
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=,MAXM=;
int n,m,cnt,match[MAXN],head[MAXN],ans;
bool vis[MAXN];
struct edge
{
int v,next;
}e[MAXM*2];
void addedge(int x,int y)
{
e[++cnt]=(edge){y,head[x]};
head[x]=cnt;
return;
}
bool Hungary(int u)
{
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(!vis[v])
{
vis[v]=true;
if(!match[v]||Hungary(match[v]))
{
match[v]=u;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y);
}
for(int i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if(Hungary(i))ans++;
}
printf("%dn",ans);
return 0;
}
网络流解法
思路
建立源点，向(Xi)连边，容量为(1)；
若二分图中有边(i,j)，则从(Xi)向(Yj)连边，容量为(1)；
建立汇点，(Yi)向汇点连边，容量为(1)。
使用最大流算法解决。
二分图最小点覆盖
定义
点数最少的点覆盖。
有关概念
点覆盖：一个点集，满足所有边至少有一个端点在集合里。
极小点覆盖：本身是点覆盖，其所有真子集都不是。
求解算法
König 定理：最小点覆盖大小=最大匹配数。
首先，二分图最大匹配满足图中没有增广路；
假设最大匹配数为(n)，则(X)部和(Y)部都各有(n)个匹配点，覆盖了(n)个匹配边；
对于非匹配边，若它的两个端点都是非匹配点，那么这条非匹配边成一个增广路，和二分图最大匹配的性质不符，故非匹配边的两个顶点一定是一个匹配点和一个非匹配点，于是这个非匹配边会被这个匹配点覆盖；
故(X)部的(n)个匹配点或(Y)部的(n)个匹配点都可以覆盖所有边，故最小点覆盖大小为(n)。
二分图最大独立集
定义
点数最多的独立集。
有关概念
独立集：一个点集，集合中任意两个点不相邻。
极大独立集：本身是独立集，再加入任何点就不是。
求解算法
最大独立集大小=总点数-最大匹配数。
可以用上面的结论：非匹配边的两个顶点一定是一个匹配点和一个非匹配点，故不存在两个非匹配点之间有边，故非匹配点构成独立集；
又有不存在增广路能使最大匹配数变大而使这个独立集变小，故这个独立集是最大独立集。
二分图最大团
定义
点数最多的团。
有关概念
团：一个点集，集合中任意两个点都相邻，对于二分图来说，我们默认(X)部的每个点之间和(Y)部的每个点之间都有边，故二分图的团是在(X)部找一个点集(S_x)，在(Y)部找一个点集(S_y)，使得(S_x)中的每一个结点和(S_y)中的每个结点之间都有边。
补图：包含原图的所有结点，原图中若两个结点(Xi,Yj)之间有边，则补图中没有，否则补图中有。
极大团：本身为团，再加入任何点都不是。
求解算法
最大团=补图的最大独立集。
补图中不相邻的两个结点在原图中一定相邻。
二分图最小边覆盖
定义
边数的最小边覆盖。
有关概念
边覆盖：一个边集，使得所有点都与集合中的边邻接。
极小边覆盖：本身是边覆盖，其所有真子集都不是。
求解算法
最小边覆盖大小=总点数-最大匹配数。
首先设最大匹配数为(n)，总点数为(m)，每个匹配边可以不重复地覆盖(2)个点，故覆盖了(2n)个点；
剩下的每条边最多只能覆盖(1)个点，故剩下(m-2n)个点需要(m-2n)条边来覆盖，故最小边覆盖大小为(m-2n+n=m-n)。
DAG最小路径覆盖
定义
用尽量少的不相交简单路径覆盖DAG的所有顶点。
有关概念
DAG：有向无环图。
链：一个点集，其中任意两点(u)、(v)可以到达，要么(u)能走到(v)，要么(v)能走到(u)。
反链：一个点集，其中任意两点均不可到达。
最大（长）反链：反链中点数最多的一个（=最小路径覆盖数）。
求解算法
思路
由最小路径覆盖数=DAG的点数-最小路径覆盖的边数。
把原图的所有节点拆成(Xi)和(Yi)，如果DAG中存在边(i,j)就在二分图中连有向边(Xi,Yj)，跑二分图匹配。
容易得出最大匹配数就是最小路径覆盖的边数，故最小路径覆盖数=DAG的点数-最大匹配数。
二分图最大权匹配
定义
若二分图的每条边都有一个权值(v[i][j])，求一种完美匹配，使得所有匹配边的权值和最大，记做最优完美匹配。
有关概念
完美匹配：又称完备匹配，匹配了所有点的匹配。
可行顶标：对于二分图的每个点给定一个顶标值，用(lx[i])记录(X)部的顶标，用(ly[i])记录(Y)部的顶标。对于图中任意一条边((Xi,Yj))满足(lx[i]+ly[j]geq v[i][j])。
相等子图：原图的一个生成子图，包含原图的所有点，但是只包含(lx[i]+ly[j]=v[i][j])的边（可行边）。
求解算法
KM算法
思路
定理：如果原图的一个相等子图中包含完美匹配，那么这个匹配就是原图的最佳完美匹配。
初始化(lx[i]=max{v[i][j]},quad 1leq jleq n)，(ly[i]=0)，此时满足(lx[i]+ly[j]geq v[i][j])。
我们通过修改顶标的方式扩大相等子图，寻找完美匹配。
从(X)部的每一个点开始增广，保证增广路径上都是可行边：
若能找到一条增广路，这个点完成配对；
否则在当前增广路径上的所有(X)部结点顶标减去(a)，所有(Y)部顶标加上(a)。
此时有如下四种情况：
-
(Xi)和(Yj)都属于增广路径，(lx[i]+a+ly[j]-a)不变，故((i,j))仍然为可行边。 -
(Xi)和(Yj)都不属于增广路径，(lx[i]+ly[j])不变，故((i,j))可行性不变。 -
(Xi)不属于增广路径，(Yj)属于增广路径，(lx[i]+ly[j]+a)增大，((i,j))仍然不可能加入相等子图。 -
(Xi)属于增广路径，(Yj)不属于增广路径，(lx[i]-a+ly[j])减小，((i,j))有可能会加入相等子图。
所以进行修改操作后，原来的可行边仍然可行，不可行边有可能加入相等子图。
上述四种情况只有第四种可行性可能发生改变，故取所有第四种情况的边，(a=min{lx[i]+ly[i]-v[i][j]})。
这样就能保证每次都有至少一个边加入相等子图。
实现
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=,INF=0x3f3f3f3f;
int n,e[MAXN][MAXN],match[MAXN],lx[MAXN],ly[MAXN],slack[MAXN];
bool visx[MAXN],visy[MAXN];
bool dfs(int x)
{
visx[x]=true;
for(int y=1;y<=n;++y)
{
if(visy[y])continue;
int t=lx[x]+ly[y]-e[x][y];
if(!t)
{
visy[y]=true;
if(!match[y]||dfs(match[y]))
{
match[y]=x;
return true;
}
}
else slack[y]=min(slack[y],t);
}
return false;
}
int KM()
{
memset(match,0,sizeof(match));
memset(ly,0,sizeof(ly));
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
lx[i]=max(lx[i],e[i][j]);
for(int i=1;i<=n;++i)
{
memset(slack,0x3f3f3f3f,sizeof(slack));
while(true)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(dfs(i))break;
int d=INF;
for(int j=1;j<=n;++j)if(!visy[j])d=min(d,slack[j]);
for(int j=1;j<=n;++j)
{
if(visx[j])lx[j]-=d;
if(visy[j])ly[j]+=d;
else slack[j]-=d;
}
}
}
int ret=0;
for(int i=1;i<=n;++i)ret+=e[match[i]][i];
return ret;
}
int main()
{
while(scanf("%d",&n)==1)
{
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&e[i][j]);
printf("%dn",KM());
}
return 0;
}
网络流解法
思路
建立源点，向(Xi)连边，容量为(1)，费用为(0)；
若二分图中有边(i,j)，则从(Xi)向(Yj)连边，容量为(INF)，费用为权值的相反数（由于费用流求出的是最小费用）；
建立汇点，(Yi)向汇点连边，容量为(1)，费用为(0)。
使用费用流算法解决。
