一、简介
二分图の定义
二分图又叫二部图,是图论中的一种特殊模型。
假设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.toymoban.com/news/detail-413962.html
干货|二分图详解https://www.zhihu.com/tardis/landing/m/360/art/89972891以上内容就是本文的全部内容啦!感谢阅读!文章来源地址https://www.toymoban.com/news/detail-413962.html
到了这里,关于二分图(Bipartite Graph)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!