图论：最大二分匹配

二分图是其顶点可以分为两个独立的集合L和R的图, 这样每个边（u, v）要么连接从L到R的顶点, 要么连接从R到L的顶点。换句话说, 对于每个边（u, v）u∈L和v∈L。我们也可以说不存在连接相同集合的顶点的边。

匹配是一个二部图, 它是一组边的选择, 没有两个边共享端点。给定无向图G =（V, E）, “匹配”是边M⊆E的子集, 使得对于所有顶点v∈V, M的最多一个边入射在v上。

最大匹配是最大基数的匹配, 即匹配M, 对于任何匹配M’, 我们都有| M |> | M’|。

寻找最大的二分匹配

我们可以使用Ford-Fulkerson方法在| V |的时间多项式中在无向二分图G =（V, E）中找到最大匹配。和| 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。