На этом шаге рассмотрим понятие разреза транспортной сети.
В методе Форда-Фалкерсона проводится многократное увеличение потока вдоль увеличивающих путей до тех пор, пока не будет найден максимальный поток. Откуда нам известно, что по завершении алгоритма действительно будет найден максимальный поток? Поток является максимальным тогда и только тогда, когда его остаточная сеть не содержит увеличивающих путей. Введем понятие разреза транспорной сети.
Разрезом (S, T) транспортной сети G = (V, E) назвается разбиение множества вершин V на множества S и T = V - S, такие, что s ∈ S, а t ∈ T. Если f - поток, то чистый поток f(S, T) через разрез (S, T) определяется как
Пропускной способностью разреза (S, T) является
Минимальным разрезом сети является разрез, пропускная способность которого среди всех разрезов сети минимальна.
На рис. 1 показан разрез ({s, v1, v2}, {v3, v4, t}) Транспортной сети, представленной на рис.1 шаг 63.
Рис.1. Разрез транспортной сети
Для разреза (S, T) в транспортной сети, где S = {s, v1, v2}, а T = {v3, v4, t} чистый поток равен f(S, T) = f(v1, v3) + f(v2, v4) - f(v3, v2) = 12+ 11 - 4 = 9, а пропускная способность составляет c(S, T) = c(v1, v3) + c(v2, v4) = 12 + 14 = 26.
Для заданного потока f в транспорной сети G со стоком s и истоком t справедливо утверждение, что чистый поток через любой разрез одинаков и равен величине потока. Величина любого потока орграничена сверху пропускной способностью произвольного разреза.
На следующем шаге рассмотрим базовый алгоритм Форда-Фалкерсона.
