Show that there is a flow network with a bottleneck of 1 where the mac flow is greater than 1.

172 Views Asked by At

Using a Ford-Fulkerson algortihm with the restriction that it cannot decrease the flow on an edge, find a flow network with $f>1$ where this algorithm terminates after finding a flow of $ 1 $.


It's pretty easy to find a flow network where the algorithm terminates after finding a suboptimal flow, but is it even possible for it terminate after finding a flow of $ 1 $?

1

There are 1 best solutions below

0
On

enter image description here

If the first augmenting path picked by the algorithm happens to be S-A-B-T then the algorithm will terminate with a suboptimal flow of 1.

This is because the residual graph will only have edges A-T and S-B since you are not allowed to decrease the flow on an edge.