Definition of a cut

69 Views Asked by At

This is going to be obvious but the correction of an exercise made me doubt about the definition of the capacity of a cut in a flow:

Exercise

I though that the capacity of a cut was the sum over the ingoing and outgoing edges of the capacity, where we multiply the capacity of ingoing edges by $-1$ and outgoing by $1$. So this would produce $1\cdot 2-1\cdot1+1\cdot 2$ for this cut=3.

I must be doing something wrong...

1

There are 1 best solutions below

0
On

The capacity of the cut is the maximum possible total flow from red vertices to black vertices, ignoring what happens internally in each part.

Even tough it is allowed to send 1 unit of flow along the back edge, doing so is not required. And doing it would just reduce the total net flow, so when we're maximizing that flow we'll assume that the back edge is not utilized.

Thus that capacity of the cut is just the sum of the forward edges across the cut, ignoring backwards ones.