3
$\begingroup$

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?

  • 0
    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.2012-11-15

0 Answers 0