graphmax-flowford-fulkerson

Ford-Fulkerson algorithm on graph with Two-Way Edges


Im having some trouble understanding the Ford-Fulkerson algorithm for fidning maximum flow and was hoping for some help.

If we look at the following graph with source A and sink F where the edge capacities are listed on every edge. enter image description here

You will notice that the nodes B and C have a two-way edge, B-C have a capacity of 8 and C-B have a capacity of 3.

Now, lets say that the first path is found is A-B-C-F where the bottleneck capacity is 8. Thus, we push 8 flow on the path creating this graph: enter image description here

Now lets say that the next path is A-C-B-D-F.

My question is how much flow are we now able to push through C-B? Is it 11 by using 8 of the already pushed flow together with capacity of 3 on the other edge or is it only 3 or possibly 8?

Thank you for your time.


Solution

  • I think you have constructed the second residual graph wrongly. Here is the version that I have prepared from the first graph.

    enter image description here

    Whenever you pass a flow into an augmenting path, you need to adjust the capacities along with it. Hence, when you passed the flow with value 8 along the path A-B-C-F, you need to adjust the capacities of the edges associated before passing the next flow into the graph.

    Hence, the value 8 came from the bottleneck capacity of the edge B-C or C-F. As you have passed the maximum flow along in these two edges, and you cannot pass more than 8, hence you have maximized the use of the capacity of these edges. This generalizes to the idea that, whenever you pass some flow using some edges, you need to draw the backward edges with the flow values added with the capacities of the backward edges and subtracted from the forward edges.

    You can see that from my version of your second graph. As B-C has no more capacity to carry additional flow (8 - 8 = 0), I have omitted the edge and added the capacity to the reverse edge (i.e. C-B where the capacity was increased to 3 + 8 = 11). The same thing happened for the C-F as well.

    Now for A-B, as we have passed 8 along with the path with capacity 10, we still have 2 capacity left to pass more flow. Hence we subtract the value from A-B and get (10 - 8 = 2). We add the reverse edge B-A as well which is being created adding the flow value (i.e. 0 + 8 = 8).

    Now as we have constructed our residual graph correctly, the only augmenting path that remains which can carry the flow from A-F is A-B-D-F with flow value 2 (bottleneck capacity is 2).

    Hence the max flow value (total flow value) is 8 + 2 = 10

    Hope that helps!