二分图
二分图定义
二分图的几种定义 :
- 不含奇环的图
- 用两种颜色给每个顶点染色,可以保证相邻的顶点颜色不同
- 可以分成两堆,所有的边都是从一堆连到另一堆的
二分图判定
判定方法 : 染色法
1 | vector<int> G[maxn]; |
二分图上最大匹配和最小点覆盖的关系
最大匹配数 = 最小点覆盖数
证明: 采用反证法。
首先,最小点覆盖的数量一定大于等于最大匹配数。
若现在有一条边没有被覆盖,这与最大匹配数相矛盾。得证。
与最小边覆盖的关系
最小边覆盖数 = 顶点数 - 最大匹配数
证明:
设最大匹配数为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$的极大独立集必为极小支配集,其逆不真。