二分图基础

概念

• 二分图定义：

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

• 二分图概念：

  当且仅当图中不含奇数环。

  奇数环概念：长度为奇数的环(循环圈)。

• 二分图的判定方法：染色法

#include <iostream>
#include <cstring>
using namespace std;

const int N = 200000;

int h[N],e[N],ne[N],idx=0;
int m,n;
int group[N];

void add(int x,int y){
    e[idx]=y;ne[idx]=h[x];h[x]=idx++;
}

bool dfs(int x,int y){
    group[x]=y;
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        if(!group[j]){
            if(!dfs(j,3-y))
                return false;
        }
        else{
            if(group[j]==y)
                return false;
        }
    }
    return true;
}

int main(){
    memset(h,-1,sizeof(h));
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }

    bool flag=true;
    for(int i=1;i<=n;i++){
        if(!group[i])
            if(!dfs(i,1)){
                flag=false;
                break;
            }
    }
    if(flag)
        puts("Yes");
    else
        puts("No");
        return 0;
}

• 增广路径：

  增广路径的定义：设M为二分图G已匹配边的集合，若P是图G中一条连通两个未匹配顶点的路径（P的起点在X部，终点在Y部，反之亦可），并且属M的边和不属M的边 (即已匹配和待的边)在P上交替出现，则称P为相对于M的一条增广路径。
  增广路径是一条“交错轨”。也就说 , 它的第一条边是目前还没有参与匹配的 ,第二条边参与了匹配 ,第三条边没有······最后一条边没有参与匹配 ,并且起点和终还没有被选择过，这样交错进行 ,显然 P有奇数条边。

应用

1. 最大匹配数

二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
二分图的完全匹配：如果一个匹配中，图的每个顶点 都和图中某条边相关联，则称此匹配为完全匹配。

2. 最小覆盖点集
3. 最小边覆盖
4. 最大独立集

二分图基础

原文：https://www.cnblogs.com/z-thorn/p/14499065.html