Validate a cut and calculate its capacity

Cut capacity

A cut separates the source from the sink by placing the vertices into a source side and a sink side. Its capacity is the sum of capacities on edges directed from the source side to the sink side

1. Separate the source and sink The source is in the source side and the sink is in the other side \(\displaystyle s\in S,\quad t\in T\)
2. Inspect every crossing edge A crossing edge can point from the source side to the sink side or in the reverse direction \(\displaystyle u\in S,\ v\in T\Rightarrow u\to v\text{ or }v\to u\)
3. Include only forward arrows Count an edge only when its arrow leaves the source side and enters the sink side \(\displaystyle u\to v,\quad u\in S,\ v\in T\Rightarrow c(u,v)\text{ is included}\)
4. Add each included capacity once The cut total is the sum of all included forward crossing capacities \(\displaystyle 7+5+4=16\)

Worked example

For the directed network and cut below, find the cut capacity

1. \(\displaystyle S=\{s,a\},\quad T=\{b,t\}\)The source is on S and the sink is on T, so the partition separates them
2. \(\displaystyle a\to b,\quad s\to b,\quad a\to t\)These are the crossing edges whose arrows leave S and enter T
3. \(\displaystyle 9+6+8=23\)The cut capacity is 23 because the reverse edge b to a is not counted

Common mistakes

Difficulty levels

Questions about this topic

In this chapter