最大二分匹配方法中的错误

Question

具有源和汇的二分图如下所示。每条边的容量为 1 个单位： Source : GeeksforGeeks

我试图找到从源到汇的最大流量。一种方法是使用 Ford-Fulkerson 算法解决最大流问题，该算法适用于所有图形。我找到了一种找到最大流量的简单方法（太简单了，不可能正确！）但我无法在该方法中发现任何错误。

方法：

c1 = 在具有出边的顶点列表中计算具有非零边数的顶点的数量。

c2 = 在具有传入边的顶点列表中计算具有非零边数的顶点的数量。

最大流量将是这两个数字中的最小值，即 min(c1,c2)。[因为任何路径都需要传出顶点列表中的一个顶点，以及传入顶点列表中的其他顶点。]

如有任何帮助，我们将不胜感激。

Answer 1

考虑像这样的图表

*--*
  /
 /
*  *
  /
 /
*--*

（连接组件工作的补丁不能解决问题；连接左下角到右上角。）

Answer 2

没有确切答案，但我有一个有效的迭代算法。对我来说，你显然需要平衡流，以便它分布在可以将它发送到可以接收它的右顶点的左顶点中。假设您使用包含二分链接的矩阵 A 对您的情况进行建模。然后，您可以假设，如果您的矩阵恰好包含您想要通过边的流量（介于 0 和 1 之间），那么给出此决定的总流量为 b=A*a，其中 a 是一个向量。如果您从 A 的最大容量开始，将所有边设为 1，将所有其他边设为 0，则 b 中的某些元素可能大于 1，但您可以减少 A 中它们对应的元素，使它们通过较少的流量。然后你可以逆流看看你的二分体最大接收能力是多少，用a=A'b测试一下。同样，您可能拥有大于 1 的 a 元素，这意味着理想流将大于从源到元素的可能容量，并减少 A 流中的这些元素。使用此 ping-pong 算法并逐步减少校正，您可以保证收敛于最佳矩阵。给定一个最终的 b=Aa 和一个向量，你的最大流量将是 sum(b)。看下面的octave代码，我用B作为收敛矩阵，大家有意见可以留言。

A=[0 1 0 1;1 0 0 1;1 1 0 0;0 0 1 0];
B=A;
repeat
  b=B*ones(4,1);
  B=B.*([.8 .8 .8 1]'*ones(1,4));
  a=B'*ones(4,1)
  B=B.*(ones(4,1)*[.9 .9 1 .9]);
until converge
maxflow=sum(b)

最大二分匹配方法中的错误

Error in an approach to Maximum Bipartite matching

algorithm

graph

bipartite

max-flow