3
$\begingroup$

I'm looking for the max flow in this graph but something is going wrong.

enter image description here

First I take the path : 1-2-4-6. So the flow ie $F=1$

Then : 1-3-2-5-4-6 and the flow updates to $F=2+1=3$

If i take the path : 1-3-5-6 my flow is $F=3+2=5$

And the graph is disconnected now. I can't reach 6 starting in 1. I know the maximum flow should be 6 but I think the algorithm stops when there's not path joining the source and the target.

What's the extra condition I'm missing? How can i find the maximum flow?

$\endgroup$
1
  • $\begingroup$ "If i take the path : 1-3-5-6 my flow is $F=3+2=5$": Shouldn't it be $F=3+3=6$? $\endgroup$ – Khue Jun 9 '15 at 12:23
1
$\begingroup$

Hint

So you just proved (by counterexample) that maximum flow is not the same as maximal flow.

To construct the maximum flow, look at the graph and note that minimum cut of size $6$ occurs in $\{(2,4),(2,5),(3,5)\}$, so all of these have to be used to maximum capacity, and in your flow they are not.

If you need more hints, ask questions...

$\endgroup$
2
  • $\begingroup$ Yeah I was looking for a minimum cut when i realized there was a problem. That's the reason i thought the maximum flow should be 6. In theory Ford-Fulkerson's algorithm should end with the maximum flow so.. what was my mistake? I can give more information if needed. $\endgroup$ – Abellan Jun 8 '15 at 21:13
  • $\begingroup$ @Abellan you need another iteration I think, or the other ones come in the wrong order... $\endgroup$ – gt6989b Jun 9 '15 at 4:06
1
$\begingroup$

There are two flows, 1) forward flow (directed edge) 2) reverse flow (opposite to edge direction)

0 <= forward flow - reverse flow <= capacity of edge

so in residual network, there will be reverse capacity available for every forward flow

available reverse capacity = forward flow - reverse flow

In above case, there is reverse capacity of 2 available from node (2) to node (3), so there is one more path possible 1->2->3->5->6 F = 5 + 1 = 6.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.