Lesson 2: Cuts and their capacity

The capacity of a cut with an edge pointing back

SkillsCapacity of a cutIdentifying cuts

Worked example

  • Simple familiar

The figure shows a cut through a network of gas pipes. Capacities are in terajoules per day (TJ/day).

(a) List the vertices on each side of the cut.

(b) Find the capacity of the cut.

1 of 4 steps
  1. Step 1: Name the two sides

    The cut puts SS and AA on one side. Source side: {S,A}\{S, A\}. Sink side: {B,C,T}\{B, C, T\}.

    {S,A}∣{B,C,T}\{S, A\} \mid \{B, C, T\}

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Name the source side and the sink side.

  2. Find every edge with one end on each side.

  3. Add the capacities of those pointing from the source side to the sink side only.

Watch out for

  • Adding BABA: 11+4+7=2211 + 4 + 7 = 22 is wrong.

  • Subtracting BABA: 11+7−4=1411 + 7 - 4 = 14 is also wrong. A backward edge counts as 0.

Save your progress with a free account