6
$\begingroup$

In the flow network below, an S-T cut is made.

a busy cat

The net flow across the cut is $12-4+11=19$.

The capacity of the cut is $12+14=26$. The "backwards" edge $(v_3,v_2)$ is not counted when calculating capacity.

Why isn't the capacity of a cut defined to be $(\text{capacity of forward edges}) - (\text{capacity of backwards edges})$? This is more intuitive.

$\endgroup$
2
$\begingroup$

The "capacity" of a cut is used as an upper bound on the flow from the source to the sink. The "capacity" of the cut is therefore equal to maximal flow that can cross the cut from the source to the sink.

For this graph, that is at most 26. If you would subtract the backward edges, you no longer have an upper bound (you could even end up with a negative number).

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