Лекция 8. Задача о максимальном потоке в сети. Алгоритм пометок Форда-Фалкерсона (Лекции 2016 года)

Методы дискретной оптимизацииЗадача о максимальном потоке в сети.Алгоритм пометок Форда-Фалкерсона1 / 11Основные понятияОпределение.Потоковая сеть – набор G = (V, E, c, s, t), где (V, E) – орграф, c – векторпропускных способностей дуг, |c| = |E|, вершины s,t – исток и стоксоответственно. Степень захода вершины s равна 0, степень исходавершины t равна 0.Система обозначений:u+ = {v ∈ V |(u, v) ∈ E}u− = {v ∈ V |(v, u) ∈ E}f – поток в G, т.е. вектор, |f | = |E|, для которого выполнены условия1.

f (e) ∈ [0, c(e)], e ∈ E2. f (u) = f (v),P ∀u ∈ V \{s, t},Pт.е.f (u+ ) = v∈u+ f (u, v) = v∈u− f (v, u) = f (u− )Условие 1) – ограничение на величину потока по каждой дуге, т.е.величина потока по каждой из дуг e ∈ E не может превосходитьпропускной способности этой дуги c(e). Условие 2) – условиенеразрывности потока в каждой вершине: выходящий из вершины u потокf (u+ ) совпадает с потоком f (u− ), входящим в u.2 / 11Задача поиска максимального потока||f || = f (s+ ) – величина потока в сети.Задача: Найти поток f максимальной величины при условиях 1), 2).

Втерминах задачи линейного программирования задача формулируетсяследующим образом. Пусть |V | = n, |E| = m, v1 = s, vn = t, матрицаинцидентности A = (aij ), aij = +1 ⇔ (vi , vj ) ∈ E; aij = −1 ⇔ (vj , vi ) ∈ E,i = 2, 3, . . . , n − 1. В других случаях элемент матрицы A равен 0.Элементы матрицы A не касаются вершин s, t, в частности, это означает,что строки матрицы суть ai , i = 2, . . . , n − 1. Строка a1 участвует вцелевой функции полученной задачи(a1 , f ) → max, Af = 0, 0 ≤ f ≤ cПоследнее условие задачи означает существование ее решения f ∗ в силуограниченности множества допустимых точек в линейной задачиоптимизации.3 / 11Задача поиска максимального потокаОпределение.Разбиение (Vs , Vt ) множества вершин V : V = Vs ∪ Vt , Vs ∩ Vt = ∅,s ∈ Vs , t ∈ Vt называется (s, t)-разрезом сети G.Для (s, t)-разреза множество дуг идущих из Vs в Vt обозначим какE(Vs → Vt ) = {e|e = (u, v) ∈ E, u ∈ Vs , v ∈ Vt }Величину потока, идущего из из Vs в Vt , обозначим какXf (Vs → Vt ) =f (e).e∈E(Vs →Vt )Аналогично множество дуг, идущих из Vt в Vs , обозначим черезE(Vt → Vs ) = {e|e = (v, u) ∈ E, v ∈ Vt , u ∈ Vs },а величину потока, переходящего из t в s, обозначим какXf (Vt → Vs ) =f (e).e∈E(Vt →Vs )4 / 11Задача поиска максимального потокаЛемма 1.||f || = f (Vs → Vt ) − f (Vt → Vs )Доказательство.Из равенствPP f (v+ ) − f (v− ) = 0, f (s+ ) = ||f || следуетсоотношение v∈Vs f (v+ ) − v∈Vs f (v− ) = ||f ||.

В полученном равенствеслагаемые, соответствующие ребрам вида (u, v), где u, v ∈ Vs , взаимноуничтожаются, остаются лишь слагаемые, соответствующие ребрам сконцами из разных множеств Vs , Vt .Определение.Пропускной способностью (s, t)-разреза называется величинаXc(Vs , Vt ) =c(e).e∈E(Vs →Vt )По определению 0 ≤ f (Vs → Vt ) ≤ c(Vs , Vt ) ⇒ ||f || ≤ c(Vs , Vt ).Следствие.

Если для некоторого потока f его величина совпадает спропускной способностью некоторого разреза, то указанный потокявляется потоком максимальной величины, а найденный разрез являетсяразрезом минимальной пропускной способности.5 / 11Задача поиска максимального потокаОпределение.Цепь из вершины u в вершину v – последовательностьP = {u = v0 , v1 , . . .

, vn = v}, для каждой пары соседних вершин (vk , vk+1 ),k = 0, 1, 2, . . . , n − 1 которой либо (vk , vk+1 ) ∈ E, либо (vk+1 , vk ) ∈ E. Впервом случае дуга (vk , vk+1 ) – прямая дуга для цепи, во втором случае –обратная.Для цепи P из u в v величиныc (e) − f (e) , e − прямая дуга,∆ (y) =δ (P ) = min ∆ (e) .f (e) , e − обратная дугаe∈PОпределение.Цепь P увеличивает поток f , если δ(P ) > 0.6 / 11ПримерВ примере на Рис. 1 цепь P = {s, v3 , v4 , v2 , v1 , v5 },δ(P ) = min(3, 2, 2, 2, 4) = 2 > 0.7 / 11Задача поиска максимального потокаТеорема 1.Если f – поток в G, а (s, t)-цепь P увеличивает f , то существует поток f1такой, что ||f1 || = ||f || + δ(P ).Доказательство.

Построим поток f1 , положив f (e) + δ (P ) , e − прямая дуга,f (e) − δ (P ) , e − обратная дуга,f1 (e) =f (e) , e − не элемент цепи P.Для построенного потока условие ограничения на пропускнуюспособность выполнено. Далее рассмотрим произвольную вершину v, длянее возможны ситуации:1. В данную вершину входит прямая дуга e1 и выходит прямая дуга e2 .Тогда для обеих дуг величина потока увеличится на δ(P ), чтоозначает сохранение условия неразрывности потока.2.

В вершину v входит прямая дуга ek и входит обратная дуга ek+1 .Тогда величина потока для обеих дуг уменьшится на δ(P ), что такжеозначает сохранение условия неразрывности.8 / 11Задача поиска максимального потокаТеорема 2.Для потока f в сети G следующие условия эквивалентны:1. f – максимален.2. Не существует увеличивающей (s, t)-цепи.3. Существует разрез (Vs , Vt ), для которого ||f || = c(Vs , Vt ).Доказательство. Импликация 1 ⇒ 2 следует из теоремы 1.

Импликация3 ⇒ 1 следует из леммы 1. Покажем справедливость импликации 2 ⇒ 3.Обозначим Vs1 = {v ∈ V |∃(s, v)-цепь P ,для которой δ(P ) > 0},Vs = Vs1 ∪ {s}, Vt = V \Vs . Покажем: ||f || = c(Vs , Vt ). Рассмотрим дугуe = (u, v), u ∈ Vs , v ∈ Vt ⇒ f (e) = c(e),поскольку в противном случае множество Vs может быть дополненовершиной v. Из этого следует f (Vs → Vt ) = c(Vs , Vt ). Аналогично если дугаe = (u, v), u ∈ Vt , v ∈ Vs ⇒ f (e) = 0,откуда f (Vt → Vs ) = 0.

Следовательно, ||f || = f (Vs → Vt ), что доказываеттеорему.9 / 11Решение задачи о максимальном потокеАлгоритм пометок Форда-ФалкерсонаВершины разбиваются на 3 категории: непомеченные, помеченные ипросмотренные. На начальном шаге помечается исток s, остальныевершины непомечены.Определение метки вершины: тройка (k, ±, ∆), где- k – номер той смежной вершины, из которой данная вершинапомечается,- ± – указатель на то, прямая (+) или обратная (-) дуга ведет ввершину из смежной к ней в процессе расстановки пометок,- ∆ – величина потока, на который можно увеличить входящий ввершину поток.Процесс распространения пометок заключается в том, что из вершины,откуда идут пометки, на начальном шаге это s, распространяютсяпометки по всем дугам, как выходящим из данной вершины, так ивходящим в нее, для каждой дуги изменяя поток по ней.

После переборавсех дуг инцидентных с данной вершиной она переходит в разрядпросмотренных. Далее просмотр и расстановка пометок идет изследующих помеченных вершин. Пример работы алгоритма на рис. 2.10 / 11Пример11 / 11.