I'm having trouble solving this one and would really appreciate any help. thank you in advance!
so, the problem is:
given a flow network with integer capacities on the edges and a max flow f on that network, I need to write an algorithm (efficient one) that determine whether there are at least 4 more different max flows on that given network.
I have seen people suggesting to check for cycles in the residual network. so if there is a cycle, the max flow is not unique, hence, there is another max flow "f2" and than we can choose every 0 < x < 1 and set infinite max flows such as (1-x)(|f|) + x|f2|.but, I cant seem to understand why the cycles in the residual network means that the max flow is not unique and also have a really hard time proving the second part is legal. (the infinite max flows)
thanks again!