Постановка задачи о максимальном потоке

Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW.

60 лет назад, эта задача решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкерсон предложили рассматривать для решения задачи о максимальном потоке ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе. В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы. На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также можно отнести к фундаментальным. Этот метод был разработан Голдбергом и Таряном, и получил название Push-Relabel метода. Для нахождения максимального потока, он использует предпотоки и метки, изменяемые во время работы алгоритма. Push-Relabel алгоритмы очень эффективны и исследуются до сих пор. Также в 1997г. Голдберг и Рао предложили алгоритм, присваивающий дугам неединичную длину. Это самый современный из всех известных алгоритмов. Асимптотическая оценка его быстродействия превзошла O(nm).

В России, в настоящее время, передовые алгоритмы освещаются слабо, кроме метода пометок Форда-Фалкерсона 60-летней давности. В то время как в зарубежной литературе им редко ограничиваются [1].

Теория потоков возникла первоначально в связи с разработкой методов решения задач, связанных с рациональной перевозкой грузов. Схема доставки груза представлялась в виде графа, по ребрам которого проходит подлежащий максимизации поток этого груза. Позднее обнаружилось, что к задаче о максимальном потоке сводятся и другие важные оптимизационные практические задачи. Такие, например, как задача отыскания минимального по стоимости плана выполнения комплекса работ при заданной его продолжительности; задача об определение максимального количества информации, которая может быть передана по разветвленной сети каналов связи из одного пункта в другой; задача об оптимальных назначениях; различные задачи организации снабжения; задачи автоматизации проектирования узлов вычислительных машин; задачи связанные с наиболее экономным строительством энергетических сетей, нефти- и газопроводов, железнодорожных и шоссейных дорог, ирригационных систем и много других прикладных задач.

Основным в теории потоков является понятие сети. Сеть – это взвешенный конечный граф без циклов и петель, ориентированный в одном общем направление от вершины I, являющейся входом (истоком), к вершине S, являющейся выходом (стоком) графа. Пример сети показан на рисунке 1. Для наглядности будем представлять, что по ребрам (i, j) сети из истока I в сток S направляется некоторый ресурс (груз, нефть, информация и т. п.). В теории потоков предполагается, что если ребро (i, j) входит в сеть, то в сеть входит и ребро (j, i). Ребрам сети присваивается одна или несколько числовых характеристик.

Общее количество вершин сети будем обозначать через n. На рисунке 8.1 истоком I является вершина 1, стоком S вершина 5.

Рисунок 8.1 – Пример сетевого графика с пятью вершинами

Максимальное количество r_ij ресурса, которое может пропустить за единицу времени ребро (i, j), называется его пропускной способностью. В общем случае r_ij ≠ r_ji. Если вершины k и l на сети не соединены, то r_kl = r_lk =0. На сети (рисунок 8.1) пропускные способности ребер указаны на ребрах числами. При этом первое число (оно ближе к вершине i) – это пропускная способность в направление от вершины i к вершине j, второе (оно ближе к вершине j)– в противоположном направлении. Пропускные способности сети можно задать квадратной матрицей R n -го порядка. Поскольку r_ii =0, на главной диагонали стоят нули. В таблице 8.1 приведена матрица R пропускных способностей сети, изображенной на рисунке 8.1. Здесь n =5, и поэтому матрица R -5-го порядка.

Таблица 8.1 – Матрица смежности

Количество х _ij ресурса, проходящего через ребро (i, j) в единицу времени, называется потоком по ребру (i, j).

Произвольно задать n ² чисел x_ij (i, ) нельзя. Они должны подчиняться определенным ограничениям, о которых речь пойдет дальше. А пока будем считать, что если поток из вершины i в вершину j равен x_ij, то поток из вершины j в вершину i будет равен - x_ij, т. е.:

Если поток x_ij по ребру (i, j) меньше его пропускной способности, т.е. x_ij < r_ij, то ребро (i, j) называется ненасыщенным, в противном случае оно называется насыщенным.

Совокупность X ={ x_ij } потоков по всем ребрам (i, j) сети называют потоком по сети или просто потоком.

Из физического смысла грузопотока следует, что поток по каждому ребру (i, j) не может превышать его пропускную способность, т. е.:

xij≤rij (i, ).

(8.2)

Понятно так же, что для любой вершины, кроме истока I и стока S, количество вещества, поступающего в эту вершину, равно количеству вещества, вытекающего из нее. С учетом соглашения (1) это требование можно выразить записью:

(i≠I,S).

(8.3)

Это ограничение называют условием сохранения потока: в промежуточных вершинах потоки не создаются и не исчезают. Отсюда следует, что общее количество вещества, вытекающего из истока I, совпадает с общим количеством ресурса, поступающим в сток S, т. е.:

,

(8.4)

где j – конечные вершины ребер, исходящих из I;

       i – начальные вершины ребер, входящих в S.

Линейную функцию f называют мощностью потока на сети. 

Учитывая сказанное, задачу о максимальном потоке можно сформулировать следующим образом: найти совокупность X ={ x_ij } потоков x_ij ≥0 по всем ребрам (i, j) сети, которая удовлетворяет условиям (8.1) – (8.3) и максимизирует линейную функцию (8.4). Это типичная задача линейного программирования.