二分图

二分图定义

二分图的几种定义 ：

1. 不含奇环的图
2. 用两种颜色给每个顶点染色，可以保证相邻的顶点颜色不同
3. 可以分成两堆，所有的边都是从一堆连到另一堆的

二分图判定

判定方法 ： 染色法

vector<int> G[maxn];
int color[maxn];

// 把顶点染成1或-1
bool dfs(int u,int c){
    color[u] = c;   //把u点染成颜色c
    for(auto v : G[u]){
        if(color[v] == c) return false;
        if(color[v] == 0 && !dfs(v,-c)) return false;
    }
    return true;
}

void solve(int n){
    memset(color,0,sizeof(color));
    for(int i=0;i<n;i++){
        if(color[i] == 0){
            if(!dfs(i,1)){
                cout << "No" << '\n';
                return ;
            }
        }
    }
    cout << "Yes" << '\n';
}

二分图上最大匹配和最小点覆盖的关系

最大匹配数 = 最小点覆盖数

证明： 采用反证法。

首先，最小点覆盖的数量一定大于等于最大匹配数。
若现在有一条边没有被覆盖，这与最大匹配数相矛盾。得证。

与最小边覆盖的关系

最小边覆盖数 = 顶点数 - 最大匹配数

证明：

设最大匹配数为n，顶点数为V。 我们可以先选n条边，这样只剩 $V - 2\times n$ 个点了。 接下来只能一条边搞一个点，所以还需要 $V - 2\times n$条边。

于是，最小边覆盖数 $= V - 2\times n + n = V - n$

与最大独立集的关系

独立集：
给定图$G=(V,E)$,$V’$ 是$V$的一个非空子集。若$V’$的任何两个顶点$u,v$都不是同一条边的两个端点，则称$V’$是$G$的一个空子图。设$V’$是G的空子图，若$V’$任意增加一个$G$中不在$V’$中的点后都不是空子图，则称$V’$是$G$的独立集。$G$中所含顶点数最多的独立集$V’$称为$G$的最大独立集。

最大独立集中的顶点数 = 最小边覆盖数 = 总顶点数 - 最大匹配数(最小顶点覆盖)

总顶点数再去最小顶点覆盖数就是孤立点的数目。这些点相互之间都没有边。

与最小支配集的关系

支配集：
设$G=(V,E)$是无向简单图，$S$是$V$的一个非空子集。若对于不在$S$中的$G$的点$u$，$u$与$S$里至少一个顶点$v$相关联，则称$S$是图$G$的支配集。设$S$是图$G$的支配集，若$S$的任何真子集都不是$G$的支配集，则称$S$为图$G$的极小支配集。$G$中含顶点数最少的支配集$S$，称为$G$的最小支配集，其顶点个数$|S|$称为图$G$的支配数。

设$G$是无孤立顶点的图，则$G$的极大独立集必为极小支配集，其逆不真。