网络流量 - 福特Fulkerson算法 [英] Network flow- Ford Fulkerson Algorithm

问题描述

要找到最大流量的曲线图，为什么没有足够仅与饱和在这条道路的最小边的容量都增广路径不考虑回边缘？我的意思是，什么是点称这是一个背边缘，如果我们假设从中流？

To find the Maximum Flow in a graph,why doesn't it suffice to only saturate all augmenting paths with the minimum edge capacity in that path without considering the back-edges? I mean,what is the point calling it a back-edge if we assume flow from it ?

推荐答案

回到边做福特Fulkerson算法的情况下，你选择最终不是整体流的一部分的路径时，是必要的。

Back edges are necessary when doing the Ford-Fulkerson algorithm in case the path that you choose ends up not being a part of the overall flow.

作为一个例子，后沿是必要的，考虑这个流网络：

As an example where back edges are necessary, consider this flow network:

    s
   / \
  a   b
   \ / \
    c   d
     \ /
      t

假设所有的边点下来，所有边缘都有能力1，而要找到从s的流量吨。假设在福特Fulkerson增的，你走的路径S中的第一次迭代 - > B - >ç - > T。在这一点上，你已经把流程的一个单元从S到T。如果你没有任何背边添加，你离开了这一点：

Assume that all edges point down and that all edges have capacity 1 and that you want to find a flow from s to t. Suppose on the first iteration of Ford-Fulkerson that you take the path s -> b -> c -> t. At this point, you've pushed one unit of flow from s to t. If you don't add in any back edges, you're left with this:

    s
   / 
  a   b
   \   \
    c   d
       /
      t

有没有更多的ST路径，但是，这并不意味着你有一个最大流。你可以把两个单位流量从s通过发送1沿着路径S到T - >一 - >ç - > t和其它沿路径s - > B - >ð - >吨。如果没有剩余流量网络中的任何背部的边缘，你永远不会发现这个其他的路径。

There are no more s-t paths, but that doesn't mean you have a max flow. You can push two units of flow from s to t by sending one along the path s -> a -> c -> t and the other along the path s -> b -> d -> t. Without any back edges in the residual flow network, you would never discover this other path.

希望这有助于！

这篇关于网络流量 - 福特Fulkerson算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！