Понятие разреза. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке

Пусть дана некоторая сеть. Разобьём множество вершин сети на два непересекающихся множества А и В так, чтобы исток I попал в А, а сток S – в В. В этом случае на сети задан разрез. Совокупность ребер (i,j), начальные вершины которых принадлежат А, а конечные – В, называется разрезом сети (А/B).

Пропускной способностью разреза называют сумму пропускных способностей всех рёбер разреза R (A/B) = r_ij.

Сумма всех потоков x_ij по всем рёбрам разреза называется потоком через разрез

X(A/B) =x_ij.

Теорема Форда-Фалкерсона: на любой сети максимальная величина потока равна

минимальной пропускной способности разреза.

Теорема позволяет определить максимальный поток для относительно простых сетей. В общем случае используют следующий алгоритм.

Дата добавления: 2014-01-04