1. 基本概念

极：其真子集都不满足性质

最：极中包含数目最大

点覆盖、极小点覆盖 minimal vertex covering

边覆盖、极小边覆盖 minimum edge covering

独立集、极大独立集 maximum independent set

团、极大团 maximal clique

边独立集、极大边独立集 maximal edge independent set

边独立集=匹配

支配集、极小支配集 minimal dominating set

边支配集、极小边支配集 minimum edge dominating set

最小路径覆盖 path covering

匹配

匹配(matching)是一个边集，满足边集中的边两两不邻接。匹配又称边独立集(edge independent set)。

在匹配中的点称为匹配点(matched vertex)或饱和点；反之，称为未匹配点(unmatched vertex)或未饱和点。

交错轨(alternating path)是图的一条简单路径，满足任意相邻的两条边，一条在匹配内，一条不在匹配内。

增广轨(augmenting path)：是一个始点与终点都为未匹配点的交错轨。

最大匹配(maximum matching)是具有最多边的匹配。

匹配数(matching number)是最大匹配的大小。

完美匹配(perfect matching)是匹配了所有点的匹配。

完备匹配(complete matching)是匹配了二分图较小集合（二分图X，Y中小的那个）的所有点的匹配。

增广轨定理：一个匹配是最大匹配当且仅当没有增广轨

二分图

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

最大独立集 = 总数-最小点覆盖集

最小路径覆盖=|G|-最大匹配数

最小边覆盖= 最大独立集 = n - 最大匹配，这个是二分图上的一个性质。

匈牙利算法

Hopcroft-Karp算法

Blossom 算法

集合划分的数目 \[ B_{n+1} = \sum_{k=0}^nC(n,k)B_k \]