Question

I posted it twice a day. One gave me a code while the question is not asking about code and is asking to give a graph solution and the other gave a wrong answer for the graph.

Is anyone knowledgeable of this topic and can answer this question?

PLEASE, don't give me a code for irrelevant question.

3. The following flow graph G has some flow assignments already made. Use the Ford-Fulkersoin method to continue the process of deriving the maximum flow from s to t. Show the residual graph Gf, find an augmenting path in Gf, and then update the flow in G. One step should be enough to find the max-flow. 10/10 0/10 10/10 10/1 0/10 10/10 10/10 0/10 10/10

Answer 1

For the given flow graph G, let us create a residual graph G_f  by following process :-

For every edge (u,v) in G with capacity c(u,v) and flow f(u,v) create edge (u,v) in G_f with capacity c(u,v) - f(u,v) and create backward edge (v,u) with capacity f(u,v). Do not show the edge it its capacity become zero.

Thus below is the image of residual graph G_f of above given flow graph:-

ro al (O 1o 10 iO lO IO ( e ΙΟ 10 io

Now in the above graph G_f there is still a path from s to t which is scfbeadt and the capacity of this path which is equal to minimum capacity of edge in this path is 10. Hence using ford-fulkerson algorithm, we can augment flow of 10 unit in this path. This will give create below residual graph.

l O to 1o Lo 10 10 1O Mo

Now we can see that there is no more path from s to t in this residual graph, hence max-flow is attained with total flow value = flow leaving s = flow reaching t = 10+10+10 = 30 unit

Please comment for any clarification.