解决方案

我们将二部图匹配问题归约成为一个最大流问题,而不是重新设计一个算法来解决问题。在二部图匹配中,从元素集S和参与者T中选择了一个匹配(si,tj)之后,si或者tj就不能被其他的匹配选择了。在一个流网络图G=(V,E)中得到这样的性质的话,我们应该这样构建图G。

V包含n+m+2个顶点

每个元素si映射为顶点i,每个参与者映射为顶点n+j。创建一个新的源点src(标记为0)和一个新的汇点tgt(标记为n+m+1)。

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元

E包含n+m+k条边

首先会构建n条边,连接源点src和从S映射过来的顶点。然后再构建m条边,连接汇点tgt和从T映射过来的顶点T。每个匹配pk=(si,tj)会映射成边(i,n+j)。每条边的流容量为1。

我们在流网络图G中计算出的最大流就是原始二部图匹配问题中的最大匹配集合,证明见(Cormen等,2001)。例如,考虑图8-6a中两个匹配(a,z)和(b,y)的组成最大匹配集合,依照上述过程构造的流网络如图8-6b。我们可以将其扩展到三对:(a,z)、(c,y)和(b,x)。在找到一条增广路<0,3,5,2,4,7>之后,会对流网络进行相应的调整。

阅读 ‧ 电子书库
图 8-6 小规模的二部图匹配归约成最大流问题

一旦找到最大流,我们将要将最大流问题的输出转换成二部图匹配问题的输出。也就是说,对于每一条流为1的边(si,tj),输出选中了匹配(si,tj)∈P。为了简化表述,例8-5的代码中删除了错误检测[1]

例8-5:使用Ford-Fulkerson的二部图匹配

阅读 ‧ 电子书库
阅读 ‧ 电子书库
[1]要了解更多的细节,请参见代码库中的algs.model.network.matching.Bipartite-Matching。