二分图

二分图

二分图定义

二分图的几种定义 :

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

二分图判定

判定方法 : 染色法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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$的极大独立集必为极小支配集,其逆不真。

Thank you for your support!