Did I find a max-flow min-cut theorem contradiction?

600 Views Asked by At

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 :

Cut

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$.

1

There are 1 best solutions below

2
On BEST ANSWER

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$).