Решение задачи о максимальном потоке методом расстановки пометок на графе (алгоритм Форда-Фалкерсона)

 

Граф, элементам которого поставлены в соответствие некоторые параметры, называется сетью. В зависимости от приложений различают транспортные, электрические, информационные и т.п. сети.

Поскольку в теории графов рассматриваются общие методы исследования графов и сетей, независимо от их природы, то для характеристики сетей вводятся некоторые общие понятия. Рассмотрим их, проводя для наглядности аналогию с транспортной сетью.

Каждая вершина I характеризуется интенсивностью d(i). Те вершины, для которых D(i) > 0, называются источниками, вершины, для которых D(i) < 0 – стоками, остальные – нейтральными. Так, для транспортной сети источниками являются пункты-поставщики, стоками – пункты-получатели, нейтральными – пункты, где отсутствует как производство, так и потребление данного продукта.

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

Если в сети с одним источником S и одним стоком t задана функция пропускной способности {r_ij}, то в ней может быть задана также функция, называемая потоком.

Потоком в сети называется функция, сопоставляющая с каждой дугой целое число d_ij и обладающая свойствами:

0 £ d_ij £ r_ij, {x_i, x_j}Î X; (3.1)

(3.2)

(3.3)

Для транспортной сети величина d_ij характеризует интенсивность потока по дуге . Эта величина означает количество вещества, проходящего через дугу в единицу времени.

Таким образом, потоком в сети или просто потоком называется совокупность {a_ij} по всем дугам сети.

Условия (3.1) означают, что поток по каждой дуге неотрицателен и не превышает ее пропускной способности; условия (3.2) показывают, что количество вещества, протекающего в любую нейтральную вершину, равно количеству вещества, вытекающего из нее. Следовательно, общее количество вещества, вытекающего из источника, совпадает с общим количеством вещества, притекающего в сток, что и отражается в условии (3.3).

Линейная форма V в (3.3) есть величина потока в сети. Одна из основных задач на сетях состоит в определении величины наибольшего потока, допустимого в сети при заданных ограничениях на интенсивности потоков дуг. Математически она формулируется так: найти значения переменных d_ij, максимизирующие линейную форму (3.3) при ограничениях (3.1)-(3.2).

Рассмотрим решение поставленной задачи методом расстановки пометок непосредственно на графе (алгоритм Форда-Фалкерсона). Решение проводится путем многократного повторения двух шагов алгоритма.

Первый шаг. Пометим вершину-исток S меткой (0,¥) и отнесем вершину S к множеству R, а остальные вершины графа к множеству . Далее расстановка меток осуществляется последовательно. Рассмотрим правило формирования меток. Выберем любую помеченную вершину i (первоначально это единственная вершина S) (в дальнейшем для упрощения записи формул, относящихся к одному графу, вместо «вершина x_i» будем писать просто номер вершины «i». Отмеченные вершины относятся к множеству R, непомеченные к множеству . Рассмотрим все непомеченные вершины j, связанные дугами с вершиной i. Вершину j относят к множеству R, если выполняется одно из условий:

i Î R и d_ij < r_ij; (3.4)

i Î R и d_ji > 0. (3.5)

Тем вершинам j, для которых выполняется условие (3.4), припишем метку (i⁺, e_j), где e_j = min{e_i, r_ij – d_ij}. Тем вершинам j, для которых выполняется условие (3.5), припишем метку (i^-, e_j), где e_j = min{e_i, d_ji}.

Изложенное правило формирования меток для наглядности представим графически с помощью рис. 3.1 и 3.2 соответственно для случаев (3.4) и (3.5).

 

 

(K,e_i) r_ij>d_{ij ( ,}e_j)

i Î R j

e_j=min{ e_i , r_ij-d_ij }

Рис. 3.1

(K,e_i) d_ji>0 _{( ,}e_j)

 

i Î R j

e_j=min{ e_i , d_ji }

Рис. 3.2

После помечивания вершины j, ближайшей к S, аналогично производим помечивание других вершин. Эту процедуру помечивания повторяем до тех пор, пока не пометим вершину t, или до тех пор, пока нельзя будет сделать новых пометок.

В первом случае (помечена вершина t) перейдем ко второму шагу, во втором случае исходный поток максимален.

Второй шаг. Вершина t имеет пометку (j⁺, e_t) или (j^-, e_t). Если пометка вида (j⁺, e_t), заменяем d_jt на (d_jt + e_t), если пометка вида (j^-, e_t), то заменяем d_tj на (d_tj - e_t). Затем в любом случае переходим к вершине j. В отношении любой вершины j поступаем аналогично: если ее пометка вида (i⁺, e_j), то заменяем d_ij на (d_jt + e_t), если ее пометка вида (j^-, e_j), то заменяем d_ji на (d_ji - e_t) и переходим к вершине i. Так поступаем, пока не достигнем источника S. После этого стираем все пометки и вновь переходим к первому шагу.

Таким образом, процесс расстановки пометок представляет собой систематический поиск цепи из S в t, на которой поток может быть увеличен. Если в результате первого шага сток оказался непомеченным, то вдоль найденной цепи можно увеличить поток. Если, с другой стороны, первый шаг закончился, а сток остался непомеченным, то достигнутый поток максимален. Изложенный алгоритм может использоваться для решения задачи и в более общем случае.