最大二分匹配

二分图是一个图，其顶点可以分成两个独立的集合 L 和 R，这样每条边 (u, v) 都会连接 L 中的一个顶点到 R 中的一个顶点，或者 R 中的一个顶点到 L 中的一个顶点。 换句话说，对于每条边 (u, v)，要么 u ∈ L 且 v ∈ R，要么 u ∈ R 且 v ∈ L。我们也可以说不存在连接同一集合中的顶点的边。

二分图的匹配是一组边，其选择方式是任何两条边都不共享一个端点。 给定一个无向图 G = (V, E)，一个匹配是边 M ⊆ E 的一个子集，使得对于所有顶点 v ∈ V，最多只有一条边 M 与 v 相连。

最大匹配是基数最大的匹配，也就是说，匹配 M 使得对于任何匹配 M'，我们有|M| > |M'|。

找到一个最大二分匹配

我们可以使用 Ford-Fulkerson 方法在 |V| 和 |E| 的多项式时间内找到无向二分图 G = (V, E) 中的最大匹配。诀窍是为二分图 G 构造一个流网络 G' = (V',E')，如下所示。我们让源 s 和汇 t 成为 V 中不存在的新顶点，并且我们让 V'=V ∪{s,t}。 如果 G 的顶点分区是 V = L∪R，则 G' 的有向边是 E 的边，从 L 指向 R，以及 |V| 个新的有向边。

图：一个二分图 G = (V, E)，其顶点分区为 V = L ∪ R。