I was looking for a cut of the following graph of a problem of maximum flow. Here are its capacities :

enter image description here

As far as the only nodes that have saturated edges are the upper external ones, it would be :


It seems to be strange to be only the top nodes, isn't it ? Yet the more strange is when we apply the max-flow min-cut theorem :

the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the total weight of the edges in the minimum cut, i.e. the smallest total weight of the edges which if removed would disconnect the source from the sink.

Yet, if I sum up all top edges I get $17$, whereas the maximum amount of flow passing from the source to the sink is $18$.

  • 3
    $\begingroup$ The downvote is not understandable. $\endgroup$ – Peter Apr 16 '17 at 18:56
  • $\begingroup$ Which is the source and the sink? What are the numbers on the edges and how do they relate to the capacity of the edge? $\endgroup$ – user7530 Apr 16 '17 at 18:57
  • $\begingroup$ Could you specify which is your flow and which is your cut? If the pairs of numbers mean that arcs have lower as well as upper bound the the MFMC theorem does not apply, at least not in its usual form. $\endgroup$ – A.G. Apr 16 '17 at 19:05
  • $\begingroup$ @user7530 Source is on the left sink is on the right, the number are the capacity on the first graph, the actual weight and the iteration number between parenthesis $\endgroup$ – ThePassenger Apr 16 '17 at 19:06
  • 1
    $\begingroup$ @Peter I didn't downvote, but it is certainly understandable: the question is missing a ton of information, including what type of problem is being solved (apparently, maximum flow with edge demands), what any of the numbers mean, what the cut is and what the "top edges" are, etc. $\endgroup$ – user7530 Apr 16 '17 at 19:43

The orange nodes certainly do not form a cut. A cut is never a set of nodes, but has to be a set of edges. You should be trying to disconnect the source from the sink by removing edges, while leaving all the vertices in. The minimum cut is the cheapest way to do this. In this network the minimum cut consists of the two edges of capacity $4$ from the source, together with the four edges of capacity $3$ leaving $FM_1$ and $FM_2$. These total $18$.

The edges $I\to EM_1$, $EM_1\to 1$ and $1\to O$ do not form a cut because after removing them you can still get from $I$ to $O$ (e.g. via $EM_2$ and $2$).

  • $\begingroup$ Thanks for this answer, yet there is one edge leaving $FM_2$ of capacity $3$ which has a value of $1$ should it be taken into account within the frontier ? $\endgroup$ – ThePassenger Apr 19 '17 at 10:56
  • $\begingroup$ Assuming the capacities are the second numbers in the first diagram, both edges leaving $FM_2$ have capacity $3$. I don't know what you mean by "value", but the size of the cut is the sum of the capacities. $\endgroup$ – Especially Lime Apr 19 '17 at 11:03

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.