双向边图的Ford-Fulkerson算法

Question

我在理解福特-富尔克森算法时遇到了一些问题，希望能得到一些帮助。

如果我们看下面的图，源A和宿F，其中边容量在每条边上列出。

​

您将注意到，节点B和C具有双向边，B-C的容量为8，C-B的容量为3。

现在，假设找到的第一条路径是A-B-C-F，其中瓶颈容量是8。因此，我们在创建此图的路径上推送8流：

​

现在假设下一条路径是A-C-B-D-F。

我的问题是，我们现在能够通过C-B推动多少流量？它是通过使用8个已经推送的流，以及另一个边缘上容量为3的11，还是只有3个，或者可能是8？

谢谢您抽时间见我。

Answer 1

我认为你错误地构建了第二个残差图。这是我从第一张图中准备的版本。

​

​

无论何时将流传递到增强路径中，都需要随之调整容量。因此，当您沿着路径A-B-C-F传递值为8的流时，在将下一个流传递到图中之前，您需要调整相关边的容量。

因此，值8来自边缘B-C或C-F的瓶颈容量。由于您已经在这两条边传递了最大流量，并且不能传递超过8条边，因此您已经最大限度地利用了这些边的容量。这概括了这样一种想法，即每当您使用某些边通过某些流时，您需要使用流量值加上后向边的容量并从前向边中减去来绘制后向边。

你可以从我的第二张图中看到这一点。由于B-C没有更多的容量来承载额外的流(8 -8= 0)，我省略了边缘，并将容量添加到反向边缘(即C-B，其中容量增加到3+8= 11)。同样的事情也发生在C-F上。

现在对于A-B，因为我们已经传递了8以及容量为10的路径，所以我们还剩下2个容量来传递更多的流。因此，我们从A-B中减去该值并得到(10 -8= 2)。我们还添加了正在创建的反向边B-A，并添加了流量值(即0+8= 8)。

现在我们已经正确地构建了残差图，剩下的唯一可以承载来自A-F的流的增加路径是A-B-D-F，流值为2(瓶颈容量为2)。

因此，最大流量值(总流量值)为8+2= 10

希望这能有所帮助！