Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I'm looking for the max flow in this graph but something is going wrong.
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?
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...
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.
