二分图(Bipartite Graph)

大家好，我是讯享网，很高兴认识大家。

一、简介

二分图の定义

二分图又叫二部图，是图论中的一种特殊模型。

假设S=(V,E)是一个无向图。如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，就可以称图S为一个二分图。简单来说，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

二分图の匹配

给定一个二分图S，在S的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

极大匹配是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。

最大匹配是所有极大匹配当中边数最大的一个匹配。

讯享网

二分图の判断

对于二分图的判断方法最常见的是染色法，就是对每一个点进行染色操作，只用黑白两种颜色，能不能使所有的点都染上了色且相邻两个点的颜色不同？如果可以那么这个图就是一个二分图，对于判断是否是一个二分图的方法可以用dfs和bfs两种方式去实现。代码参见“代码实现”部分。

二分图の最大匹配

给定一个二分图S，在S的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

首先要了解两个概念：

|交替路|从一个未匹配的点出发，依次经过未匹配边、匹配边、未匹配边....

|增广路|从一个未匹配的点出发，走交替路，到达了一个未匹配过的点。

对于求二分图最大匹配的算法可以用网络流去跑一个最大流求解，还可以用二分图的常见算法匈牙利算法，这个算法的核心就是去找未匹配的点，然后从这个点出发去寻找增广路，因为增广路有几个主要的特点：

增广路有奇数条边。
路径上的点一定是一个在X边，一个在Y边，交错出现。
起点和终点都是目前还没有配对的点。
未匹配边的数量比匹配边的数量多1。

重点是第4点，我们可以根据此特性，把这条增广路中的匹配边改为未匹配边，把未匹配边改为匹配边，这样我们就可以使总匹配边数+1了，根据上面的图得出下图，很显然匹配边多了一条。

代码见“代码实现”部分。

二、代码实现

“二分图の判断”配套代码：

BFS判断二分图

vector<int>G[maxn];//存边 int col[maxn];//标记顶点颜色 int n,m;//点和边的个数 bool bfs() { queue<int>q; q.push(1);//放入第一个点 memset(col,0,sizeof(col)); col[1]=1;//先标记第一个点为1 while(!q.empty()) { int v=q.front(); q.pop(); for(int i=0; i<G[v].size(); i++) { int xx=G[v][i]; if(col[xx]==0)//判断这个点是否标记过 { col[xx]=-col[v];//没有标记过就标记上与v相反的颜色 q.push(xx); } else { if(col[v]==col[xx])//如果颜色冲突说明不是二分图 { return false; } } } } return true; }

讯享网

“二分图の最大匹配”配套代码

匈牙利算法代码

讯享网vector<int> G[maxn];//存边 int pre[maxn];//记录匹配点 bool vis[maxn];//标记是否匹配过 int n,m;//n个点 m条边 bool dfs(int x) { for(int i=0; i<G[x].size(); i++) { int v=G[x][i]; if(vis[v]==false)//判断是否标记过 { vis[v]=true; if(pre[v]==-1||dfs(pre[v]))// 判断当前点是否匹配过 dfs为判断这个点能不能和其他的点匹配 { pre[v]=x; return true; } } } return false; } int Fun() { int sum=0; memset(pre,-1,sizeof(pre)); for(int i=1; i<=n; i++) { memset(vis,false,sizeof(vis));//每次遍历都需要初始化 if(dfs(i)) { sum++; } } return sum; }

参考文献：

干货｜二分图详解https://www.zhihu.com/tardis/landing/m/360/art/以上内容就是本文的全部内容啦！感谢阅读！

一、简介

二、代码实现

相关推荐