Разрез (теория графов)

Разре́з гра́фа в задачах о потоке — такая пара множеств вершин (S,T), что

1. ${\displaystyle S\cup T=V}$, где ${\displaystyle V}$ — множество вершин графа
2. ${\displaystyle S\cap T=\emptyset }$
3. ${\displaystyle s\in S,t\in T}$, где ${\displaystyle s}$ — исток, ${\displaystyle t}$ — сток.

Величиной разреза называется сумма пропускных способностей таких рёбер ${\displaystyle (i,j)}$, что ${\displaystyle i\in S,j\in T}$.