二分图(Bipartite Graph)

2023-05-30

int col 最大

一、简介二分图の定义        二分图又叫二部图，是图论中的一种特殊模型。    假设S=(V,E)是一个无向图。如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条

一、简介

二分图の定义

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

假设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;
}