How to correctly Min-Cut this network?

116 Views Asked by At

I'm trying to understand the right procedure for making cuts in max-flow min-cut problems.

In this network here https://i.stack.imgur.com/SornO.png with the dashed cut through the middle, when working out the capacity of this cut, you would not include the capacity 9 of the $v_3$ to $v_2$ edge, because it is going backwards towards S (though, if you would count the -4 if you were working out how much actual flow you were interrupting). This I understand.

But, I was told that if you were to make a cut say across edges $(v_3,t), (v_4,v_3), (v_2, v_4)$ you in fact don't count the capacity - and I think not even the flow, though please correct me if I'm wrong - of edge $(v_4, v_3)$ - why? How am I supposed to know which edges that I cut across to exclude from the calculations?

Is it because, if I were to cut all 3 of those edges, because all the edges supplying $v_4$ have been cut (namely $(v_2,v_4)$ ) then all edges leaving v4 are now defacto 'empty'?

If I'm right, then if I were to make a cut along $(s, v_2), (v_2,v_1)$ and $(v_1,v_3)$ then I wouldn't count $(v_2,v_1)$, since all edges supplying $v_2$ are already, so any capacity potentially leaving $v_2$ is already accounted for with another cut? Is this right - if not, what's the understanding behind this/procedure to follow?

Thanks very much, indeed!

Edit for future readers: it was the insightful comments supporting the accepted answer that brought it together for me, so check those out for the full explanation.

1

There are 1 best solutions below

6
On BEST ANSWER

A cut in a network isn't a line drawn through the picture. It is a partition of the vertices into two sets, $S$ and $T$, such that the source is in $S$ and the sink is in $T$. Then the capacity of a cut is the sum of the capacities of all the edges that go from a vertex in $S$ to a vertex in $T$.