匹配

匹配(matching)是一个边集，满足边集中的边两两不邻接。匹配又称边独立集(edge independent set)。 在匹配中的点称为匹配点(matched vertex)或饱和点；反之，称为未匹配点(unmatched vertex)或未饱和点。

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

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

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

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

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

完备匹配(complete matching)是匹配了二分图较小部份的所有点的匹配。

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

综上，在二分图中，最小覆盖数=最大匹配数。边覆盖数=最大独立数=|V|-最大匹配数。