1
$\begingroup$

This is not a home work question.

Is that correct to say in a flow network, if min cut is unique then max flow must also be unique?

Assume we have two max flow in a network. Then for each max flow, we can get a min cut and they are surely different.

$\endgroup$
  • 2
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Oct 20 '16 at 20:45
2
$\begingroup$

I do not agree with the downvoters of your question. This questions seems like a legit misunderstanding of the statement of the min-cost-max-flow theorem.

The theorem states that the value of the sum of edge weights in a minimum $s$-$t$ cut of a graph is equal to the value of the maximum $s$-$t$ flow in the graph interpreted as a flow network. It does not establish a one-to-one correspondence between flows and cuts.

In fact, this correspondence cannot be established in general. Here is a counter example of an unweighted undirected graph (all weights/capacities are unit):

Graph

$1$-$5$ max-flow/min-cut is equal to one. While there is a single minimum cut ({1 - 2}). There are a lot of possible maximum flows (take the unit of flow entering 2 and distribute it between 3 and 4 as you like).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.