Определение максимального потока сети с помощью метода расстановки пометок

Задачу о максимальном потоке в сети можно сформулировать следующим образом: имеется некоторый произвольный неориентированный граф, например, городская дорожно-уличная сеть, по которой происходит движение транспорта от истока (начало движение транспорта) к стоку (конечная точка движения) [1]. Каждое ребро сети имеет свой вес. В случае с городской дорожно-уличной сетью это может быть ширина дороги или её пропускная способность, т.е. количество транспорта в единицу времени. Задача о максимальном потоке для данной сети состоит в нахождении максимального количества транспорта, перемещающегося от начальной вершины - источника, к конечной вершине графа - стоку. При этом, в подобных задачах необходимо определять интервальные величины потоков рассматриваемой сети [2]. Это дает возможность учесть неопределенность исходных данных, что повышает достоверность принимаемого решения [3, 4].

Эта задача может быть решена общим методом линейного программирования. Существует другой метод, который предложили Лестер Рэндольф Форд и Делберт Рей Фалкерсон и этот метод основан на расстановке пометок. Использование этого методы привело к появлению нескольких эффективных алгоритмов.

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

Такой увеличивающей цепью является цепь из источника в сток, все дуги которой допустимы. Для того, чтобы увеличить величину потока сети на некоторую величину Q , необходимо увеличить на такую же величину Q поток на каждой согласованной дуге цепи и уменьшить на каждой несогласованной. Фордом и Фалкерсоном было доказано, что поток в сети, для которой нельзя построить увеличивающую цепь, является максимальным.

Для нахождения такой увеличивающей цепи используется метод расстановки пометок. Процесс расстановки меток начинается в источнике сети и заканчивается в ее стоке. Увеличивающаяся цепь из источника в сток существует, если сток будет являться помеченным. На вершины сети наносятся метки, содержащие необходимую информацию для восстановления цепи и определения величины, на которую можно изменить поток в сети. При этом вершина может находиться в одном из следующих состояний: непомеченная, помеченная и просмотренная.

Метод расстановки пометок начинается с произвольного потока. Затем предпринимается попытка получить поток с большей величиной. Вычисления заканчиваются, когда получен максимальный поток. Алгоритм заключается в последовательном поиске всех возможных путей из узла N _S в узел N , увеличивающих поток. Узлы получают специальные «пометки», указывающие направление, в котором может быть увеличен некоторый дуговой поток. После того как найден некоторый путь, увеличивающий поток, определяют величину максимальной пропускной способности этого пути; далее поток увеличивают на эту величину, а все пометки на узлах стирают. Затем начинается расстановка новых пометок узлов исходя из только что полученного потока.

Алгоритм состоит из двух этапов. Этап 1 – узлы получают пометки, причем каждый узел находится в одном из трех состояний: помечен и просмотрен, помечен и не просмотрен или не помечен. Вначале все узлы не помечены. Пометка произвольного узла N j всегда состоит из двух частей. Первая часть – индекс j узла N , который указывает, что можно «послать» поток из N в N j . Вторая часть пометки – число, указывающее максимальную вели- чину потока, который можно «послать» из источника NS в N j , не нарушая ограничений на пропускные способности дуг.