二分图

图论

---

概念

数学符号难打死了= =所以就不打了，概念不清楚的还是看书吧

支配
支配集
极小支配集
最小支配集
点支配数

点支配集性质

性质1
若G 中无孤立顶点，则存在一个支配集V*，使得G 中除V*外的所有顶点也组成一个支配集（即V–V*也是一个支配集）。
性质2
若G 中无孤立顶点，V*为极小支配集，则G 中除V*外的所有顶点也组成一个支配集（即V–V*也是一个支配集）

点覆盖边
点覆盖集
点覆盖数
极小点覆盖
最小点覆盖

点独立集
点独立数
极大点独立集
最大点独立集
点独立数

点支配集、点覆盖集、点独立集之间的联系

定理1
设无向图G(V, E)中无孤立顶点，则G的极大点独立集都是G 的极小支配集。逆命题不成立（即，极小支配集未必是极大独立集）。

定理2
一个独立集是极大独立集，当且仅当它是一个支配集。

定理3
设无向图G(V, E)中无孤立顶点，顶点集合V*⊆V，则V*是G 的点覆盖，当且仅当V–V*是G 的点独立集。

推论
设G 是n 阶无孤立点的图，则V*是G 的极小（最小）点覆盖集，当且仅当V–V*是G的极大（最大）点独立集，从而有：α0 ＋β0 ＝ n （n 为顶点个数）。

极小点支配集的求解

设无向图为G(V,E)，顶点集合V={v1,v2,...,vn}，则求所有极小支配集的公式为：

$$γ(v1,v2,...,vn) = \prod_{i=1}^{n}(vi + \sum_{u∈N(vi)}^{}u)$$
其中，N(vi)为顶点vi的邻接顶点集合，也称vi的为领域(neighborhood)

极小点覆盖集、极大点独立集的求解

设无向连通图为G(V,E)，顶点集合V={v1,v2,...,vn}，则求所有极小覆盖集的公式为：

$$α(v1,v2,...,vn) = \prod_{i=1}^{n}(vi + \prod_{u∈N(vi))}^{}u)$$

边覆盖点
边覆盖集(edge covering set)
边覆盖数
极小边覆盖
最小边覆盖

边独立集(匹配)
极大匹配
最大匹配
边独立数(匹配数)
盖点(饱和点)与未盖点(非饱和点)

最大边独立集(最大匹配)与最小边覆盖集之间的联系

从最大匹配出发可以构造最小边覆盖，从最小边覆盖出发也可以构造最大匹配。通常，可以这样进行：
1. 从最大匹配出发，通过增加关联未盖点的边获得最小边覆盖；
2. 从最小边覆盖出发，通过移去相邻的一条边获得最大匹配。

定理

设无向图G 的顶点个数为n，且G 中无孤立点。
1. 设M 为G 的一个最大匹配，对于G 中M 的每个未盖点v，选取一条与v 关联的边所
组成的边的集合为N，则W = M∪N 为G 中的最小边覆盖；
2. 设W1 为G 的最小边覆盖，若G 中存在相邻的边就移去其中的一条，设移去的边集为
N1，则M1 = W1 - N1 为G 中一个最大匹配；
3. G中边覆盖数α1 与匹配数β1，满足：α1 +β1 ＝ n，即：边覆盖数 + 边独立数 = n。

匹配

最大匹配
完美匹配
完备匹配
加权二分图的最佳匹配

Tips

二分图最小点覆盖 == 最大匹配