algorithm - 为什么我们使用最大流方法来解决最大二分匹配？

Question

例如

有A[0]和A[1]和B[0]和B[1]

链接(A[0], B[0])

链接(A[0], B[1])

链接(A[1], B[0])

最大匹配为(A[0].B[1])和(A[1],B[0])

但是对于最大流寻找方法，我们在 A 后面建立一个 source，在 B 之后建立一个 sink

每次尝试路径时，该方法都会找到一条路径

即:它首先得到 A[0] 和 B[0] 对

然后对于路径B[0]使用下沉，即A[1]对B[0]没有路径

它肯定不能解决这个问题，但我发现教科书、维基、博客和网站都说它的结果与最大二分匹配相同

附言

令 C(x,y) 为 x->y 的值，

通过应用算法，

第一次迭代:设置 C(s,A[0]) = 0 ； set C(A[0],s) = 1(逆流)

还有，A[0] 和 B[0]，B[0] 和 t

第二次迭代:找到从 s 到 t 的路径，只有 C(B[1],t) = 1

所以，第二次迭代找不到连接 B[1] 的点

Answer 1

实际上 max-flow 将能够正确链接这些东西。将进行第二次迭代，其中来自 A[1] 的流可以流向 B[0]，同时反向流从 A[0] 流向 B[0]。

您可以查看它可以做到这一点的 Ford-Fulkerson 算法。

编辑:

假设您从源节点 S(LINK(S,A0) 和 LINK(S,A1))(以及结束节点 F)开始，如果您在第一次迭代中应用该算法，您将以 A0-> 结束就像你说的B0。我将详细介绍第二次迭代。

1) "S"; T = {S} ; E = {}

• 标签(A1) = {S+, 1}, T = {S A1}
• E = {S}

2) "A1"; T = {S A1} ; E = {S}

• 标签(B0) = {A1+, 1}, T = {S A1 B0}
• E = {S A1}

3) "B0"; T = {S A1 B0} ; E = {S A1}

• 标签(A0) = {B0-, 1} ; T = {S A1 B0 A0}
• E = {S A1 B0}

4) "A0"; T = {S A1 B0 A0} ; E = {S A1 B0}

• 标签(B1) = {A0+, 1} ; T = {S A1 B0 A0 B1}
• E = {S A1 B0 A0}
• 不要检查“S”，因为它已经在 T 中了!

5) "B1"; T = {S A1 B0 A0 B1}

• 标签(F) = {B1+, 1} ; T = {S A1 B0 A0 B1 F}
• E = {S A1 B0 A0 B1}

一切都结束了，流量现在已经最大化了。