• 二分图

  • 定义：设G=(V, E)是一个无向图，如果顶点V可分割为两个互不相交的子集（A , B），且图中的每条边（i, j）所关联的两个定点分别属于这两个不同的顶点集，则称图G为一个二分图。

  • 性质：定理：当且仅当无向图G的每一个环的结点数均是偶数时，图G才是一个二分图。如果无环，相当于每的结点数为 0，故也视为二分图。

  • 问题1，判定一个图是否是二分图？如果一个图是连通的，可以用如下的染色法判定是否二分图：我们把X部的结点颜色设为0，Y部的颜色设为1。从某个未染色的结点u开始，做BFS或者DFS 。把u染为0，枚举u的儿子v。如果v未染色，就染为与u相反的颜色，如果已染色，则判断u与v的颜色是否相同，相同则不是二分图。如果一个图不连通，则在每个连通块中作判定。

  • 问题2，二分图的最大匹配。给定一个二分图G，在G的一个子图M中， M的边集{E}中的任意两条边都不交汇于同一个结点，则称M是一个匹配。选择边数最大的子图称为最大匹配问题。如图，加粗的就是这个二分图的最大匹配

  • 问题3，二分图的最小顶点覆盖。假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。方法：最小顶点覆盖等于二分图的最大匹配。

  • 问题4，二分图的最大独立集合。定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。
    方法：最大独立集=所有顶点数 - 最小顶点覆盖

图片说明

  • 问题1代码：

    #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
int vis[maxn],color[maxn];
int flag = 0;
vector<int> v[maxn];
queue<int> q;
void bfs(int x)
{
  q.push(x);
  color[x] = 0;
  while(!q.empty()){
      int now = q.front();
      q.pop();
      for(int i=0;i<v[now].size();i++){
          if(color[v[now][i]] == color[x])
              flag = 1;
          else if(color[v[now][i]] == -1)
              color[i] = (!color[x]),q.push(v[now][i]);
      }
  }
}
int main()
{
  int n , m;
  scanf("%d %d",&n,&m);
  for(int i=1;i<=m;i++){
      int x,y;
      scanf("%d%d",&x,&y);
      v[x].push_back(y);
      v[y].push_back(x);
  }
  memset(vis,-1,sizeof(vis));
  for(int i=1;i<=n;i++)
      if(vis[i] == 0)
          bfs(i);
  if(!flag)
      cout<<"yes"<<endl;
  else
      cout<<"no"<<endl;
  return 0;
}

  • 问题2，3，4代码（匈牙利算法）：模板-二分图最大匹配

    #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
int n, m , t;
int vis[maxn],mch[maxn];
vector<int> v[maxn];
bool dfs(int x,int y)
{
if(vis[x] == y)
  return false;
vis[x] = y;
for(int i=0;i<v[x].size();i++){
  if((mch[v[x][i]] == 0 ) || dfs( mch[v[x][i]], y)){
      mch[v[x][i]] = x;
      return true;
  }
}
return false ;
}
int main()
{
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=t;i++){
  int x,y;
  scanf("%d%d",&x,&y);
  v[x].push_back(y);
}
int ans = 0;
for(int i=1;i<=n;i++)
  if(dfs(i , i))
      ans++;
printf("%d\n",ans);
return 0;
}

```