Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have a directed graph, and we want to get the maxflow out of this graph. How can we decide the maxflow of this graph is unique?

I have an idea that after we found a maxflow out of the graph, we compute the residual graph of this graph. If there is a cycle in this residual graph, then we can generate another maxflow by modifying the previous maxflow path along this cycle.

But how can we prove that if there is no cycle in the residual graph, then the maxflow is unique in the graph?

share|improve this question
    
I'm not sure what you mean by "residual graph". Also, in directed graphs, "cycle" usually means "directed cycle", and the original graph may not have any directed cycles, and still have a unique maximal flow. Suppose the capacities of ab, bc, bd, ce, de, and ez are one. Flow 1 in a-b-c-e-z is maximal, so is flow 1 in a-b-d-e-z. –  Gerry Myerson Nov 15 '12 at 5:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.