Задача о максимальном потоке

↑

⇐ ПредыдущаяСтр 4 из 11Следующая ⇒

Задача о максимальном потоке состоит в нахождении для  данной сети стационарного потока максимально возможной величины.

Назовем цепь из s в t увеличивающей поток, если на всех ее дугах (x, y) совпадающих по направлению от s к t (прямые дуги), выполняется неравенство , а на всех дугах, не совпадающих по направлению от s к t (обратные дуги) – неравенство .

Поток является максимальным, тогда и только тогда, когда в сети не существует цепи, увеличивающей поток.

Пусть SÌV , . Разрезом   назовем множество . Если , то говорим, что разрез  отделяет источник s от стока t. Пропускная способность разреза  определяется следующим образом . Разрез, отделяющий источник от стока, с минимальной пропускной способностью называют миннимальным разрезом. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе устанавливает, что в сети величина максимального потока равна пропускной способности минимального разреза.

Алгоритм Форда-Фалкерсонадля нахождения максимального потока начинает свою работу с произвольного начального потока в сети. Например, нулевого потока.

Алгоритм на каждой итерации состоит из двух этапов.

Этап 1 (расстановка меток). На этом этапе ищется цепь, увеличивающая поток. Поиск такой цепи осуществляется с помощью расстановки меток. В процессе расстановки меток каждая вершина может находиться в одном из трех состояний: непомеченная, помеченная и непросмотренная, помеченная и просмотренная.

В начале все вершины непомечены.

Источник s получает метку вида (–, ). После этого s переходит в состояние «помечен и непросмотрен».

Пусть существует несколько помеченных и непросмотренных вершин. Выберем среди них вершину х. Просматриваем непомеченные вершины yÎO⁺(x) с  проверкой условия . Если для дуги , неравенство имеет место, то вершина y получает метку , где

                         .

Затем просматриваем непомеченные вершины yÎO^-(x)  и проверяем условие . Если для дуги (y, x) неравенство выполняется, то вершина y получает пометку , где

                                  .

После этого вершина x переходит в состояние «помеченная и просмотренная».

Далее выбирается очередная помеченная и непросмотренная вершина, и для нее повторяются все описанные выше действия. Причем придерживаемся правила: «первый помечен − первый просмотрен».

Расстановка пометок продолжается до тех пор, пока или будет помечена вершина t, или сток t никоим образом пометить нельзя.

В первом случае найден увеличивающий путь. Переходим к этапу 2.

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

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

Этап 2 (увеличение потока). Сток t может получить одну из двух пометок  или . Если t имеет пометку , поток по дуге  увеличивается на значение . Если t имеет пометку , поток по дуге , уменьшается на значение .

В любом из этих случаев переходим к вершине x, которая указана в пометке вершины t. Эта вершина имеет пометку  или . В первом случае по дуге  увеличивает поток на , во втором – поток по дуге  уменьшается на . Изменение потоков на величину  по дугам повторяется до тех пор, пока не будет достигнута вершина s.

Стираем у вершин все метки и возвращаемся к этапу 1 с новым увеличенным потоком.

В изложенном варианте сложность алгоритма Форда-Фалкерсона равна O(|V | |E |²).

Пример.Для следующей сети (на дугах заданы пропускные способности) найти максимальный поток.

Начинаем с нулевого потока. Метки вершин на итерациях приведены в таблице 3.

Изменение потока на дугах сети приведены на рисунке 5. Номер итерации, на которой проводится увеличение потока, указан у величины изменения нижним индексом.

Таблица 3

№

s

x₁

x₂

x₃

t

n

(- , ¥ )

(s⁺, 2)

(s⁺, 3)

(s⁺, 4)

(x₁⁺, 2)

0+2

(- , ¥ )

(s⁺, 3)

(s⁺, 4)

(x₂⁺, 2)

2+2

(- , ¥ )

(s⁺, 1)

(s⁺, 4)

(x₃⁺, 2)

4+2

(- , ¥ )

(s⁺, 1)

(s⁺, 2)

По последней (четвертой) итерации строим минимальный разрез. Получаем S = {s, x₂, x₃}. Следовательно, . Величина максимального потока n = 6.

Рис. 5

Алгоритм Форда-Фалкерсона можно применять для решения задачи, при наличия дополнительных условий.

1) Заданы ограничения на пропускные способности вершин. Тогда вершина x c заданной пропускной способностью c (x) > 0 заменяется дугой (x^’ , x^’’ ), пропускная способность которой полагается равной c (x). При этом каждая дуга исходной сети (у , x), входящая в вершину x, заменяется дугой  (у , x^’), а каждая дуга (x , y), выходящая из x заменяется дугой (x^’’, y). Пропускные способности новых дуг принимаются равными пропускным способностям заменяемых дуг.

2) Сеть имеет несколько источников s₁ , … , s_k и стоков t₁ , … , t_r . Необходимо найти максимальный поток из всех источников во все стоки. Вводим фиктивный источник s и фиктивный сток t. В сеть добавляем дуги (s, s_i),  (t_j , t),   с пропускными способностями
с(s, s_i) = , с(t_j , t) = .

3) Для дуг заданы нижние и верхние пропускные способности. То есть величина потока по дуге (x, y) не может быть меньше нижней пропускной способности дуги h(x, y) и не может превышать верхнюю пропускную способность c(x, y).  В предположении существования потока и найденного какого-либо начального потока, модификация алгоритма Форда-Фалкерсона состоит в вычислении  для вершины x по входящей дуге (y, x) с f (y, x) > h (y, x) по формуле .

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

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

История происхождения и развития детской игры