Блог пользователя furious__

Автор furious__, история, 5 лет назад, По-английски

Lets say an edge in the given graph has a capacity C and it has a current flow F , the residual capacity for this edge is C-F , now what does adding a back edge with capacity F intuitively mean ? I cant understand this , can anyone explain this ?? Thanks in advance :)

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Consider the graph (1->2, 1->3, 2->4, 2->3, 3->4) with capacity for each edge equal to one. If our dfs explore the path (1, 2, 3, 4) (call it A) then you can't flow anything more because the real paths you should actually use are (1, 2, 4) and (1, 3, 4), but instead you used (1, 2, 3, 4).

Now let's try to send the 2nd unit of flow from a new path (call it B) even if we explored the wrong path before (the A path).

Start from node=1. We can only go to node=3. From node=3 we can only go to node=4 but there is no enough space because a wrong path (the A path) used that space. This wrong path came from node=2, so what if we pushed back the wrong flow to node=2 and try to find a new path for that wrong path (the A path) ?

This is what we actually do. We assign the part (3->4) of A path, to our new path (the B path) and we try to find a new way to reach to terminal node from the wrong path A.

So even if in our dfs we are exploring for the case of B path, we are actually doing this job for the A path. This is the reason we need the back-edges. Because we want to know which is the node who "stole" our space. Return back to that "bad" node and continue our dfs from there.