According to the Ford-Fulkerson algorithm, I thought that if there was no path from $s$ to $t$, then the flow would be a max flow. In the flow below, there are two paths between $s$ and $t$. Then, how can this be the max flow?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ How could there be any flow from $s$ to $t$ if there were no paths for it to flow along? $\endgroup$– David RicherbyJun 5, 2015 at 8:37
-
$\begingroup$ Visually this is also easy to see. Notice the links a->b and c->d, these are the only connections from the left side to the right side, and they are fully utilized. I.e. it is a max flow. $\endgroup$– Bjarke Freund-HansenJun 10, 2015 at 8:11
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
You've left out part of the statement. It should be "If there's no path between the source and the sink with unused capacity the flow is a max flow." If you look at your graph you'll see that there is no path with unused capacity all the way from $s$ to $t$. The $s$ to $a$ link has spare capacity but $a$'s lone outbond link is saturated. The $s$ to $c$ link is saturated.
answered Jun 5, 2015 at 3:34
$\begingroup$
$\endgroup$
if there was no path from s to t, then the flow would be a max flow.
The correct statement is,
if there is no path from $s$ to $t$ in the residual network, then the flow is a max flow.
If you build the residual network, you'll see that there is no edge from $a$ to $b$ and none from $c$ to $b$ or $d$, so $s$ and $t$ are disconnected.
$\begingroup$
$\endgroup$
1
The flow is maximum if there is no augmenting(i.e. improving) path between s and t. A path would contribute to the maximum flow if all its edges have strictly positive capacity left. In your case although you have some paths between s and t, all of them will have at least one edge that has used its whole capacity. Thus you can't improve the current flow and it is maximum.
-
$\begingroup$ It adds at least one term and it touches on the intuitive part of the theorem. I believe my answer makes it more clear why the theorem is true, not just what is the theorem $\endgroup$ Jun 5, 2015 at 12:27
$\begingroup$
$\endgroup$
You need to draw the residual network for this.The augmented path finding procedure should be done in the residual network.
There are no augmented path from S to t here. So this is a max flow.
$\begingroup$
$\endgroup$
3
There is another way to see it that might help you:
if you cut the net in two subnets, i.e. s,a,c and b,d,t you can see that the net flow from the source subnet to the sink subnet is maximized: there are two saturated paths and one empty one. In any net, if you can find such a bipartition that highlights such a property then you know you've found a max flow. That works even if there is some returning path that is not empty, as per this answer: Kyle's bipartition is s,a and c,b,d,t. It works because if you have some non empty return path you can argue that emptying it would increase net flow towards the sink, but to decrease it you will certainly need to decrease also a going path thus keeping net total flow the same.
For my cut net flow is 5+3-0=8 while Kyle's leads to 5+6-3=8, and of course that's the same.
-
$\begingroup$ Welcome to Computer Science! What you say is correct but I don't really see how this answers the question, since it doesn't address the asker's misconception about Ford-Fulkerson. $\endgroup$ Jun 5, 2015 at 8:35
-
$\begingroup$ I thought it could help intuitively understand when a flow is max... The other answers are formally better but when I had to study these topics I always struggled to find some shortcuts that helped me better understand, and that's one of them. $\endgroup$ Jun 5, 2015 at 8:54
-
$\begingroup$ OK. A variety of approaches can't hurt. :-) $\endgroup$ Jun 5, 2015 at 9:39