0

如下所示，给出了具有源和汇的二部图。每条边的容量为 1 个单位： 来源：GeeksforGeeks

我试图找到从源到接收器的最大流量。一种方法是使用适用于所有图的最大流量问题的 Ford-Fulkerson 算法。我找到了一种简单的方法来找到最大流量（太简单了，不正确！）我无法在该方法中找到任何错误。

方法 ：

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

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

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

任何帮助，将不胜感激。

4

2 回答 2

1

考虑一个像

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

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

于 2016-01-24T16:36:05.833 回答
0

没有确切的答案，但我有一个有效的迭代算法。对我来说，您显然需要平衡流，以便它分布在可以将其发送到可以接收它的右顶点的左侧顶点之间。假设您使用包含双向链接的矩阵 A 对您的情况进行建模。然后，您可以假设，如果您的矩阵正好包含您想要通过边的流量（0 到 1 之间），那么给出此决定的总流量为 b=A*a，其中 a 是一个向量。如果您从 A 的最大容量开始，将所有边设置为 1，将所有其他边设置为 0，则 b 的某些元素可能大于 1，但您可以减少它们对应的 A 元素，以使它们通过更少的流量。然后你可以恢复流程，看看你的二分部分的最大接收能力是多少，湾。同样，您可能有大于 1 的 a 的元素，这意味着理想流将大于从源到元素的可能容量，并减少 A 流中的这些元素。使用这种乒乓算法并减少更正逐步地，您可以保证收敛到最优矩阵。给定一个最终的 b=A a 和一个向量，你的最大流量将是 sum(b)。请参阅下面的八度代码，我使用 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)
于 2016-01-24T17:12:35.447 回答