Разрез сети

Разрезом сети называется множество дуг, разрывая которые мы уничтожаем поток между истоком и стоком.

Рисунок 16. Варианты разрезов сети

 Вариантов разрезов может быть много. Разные разрезы будут иметь разную пропускную способность. Суммарная пропускная способность дуг разреза SC_ij-характеризует разрез.

Из всех разрезов можно выделить разрез С(U_B) с наименьшей пропускной способностью. Для него доказана теорема Форда-Фалкерсона, которая гласит-

Наибольшая величина потока в сети равна минимальной величине разреза в сети.

Фmax=C(Uв)min_j