Лекция 8. Задача о максимальном потоке в сети. Алгоритм пометок Форда-Фалкерсона (1162204)
Текст из файла
Методы дискретной оптимизацииЗадача о максимальном потоке в сети.Алгоритм пометок Форда-Фалкерсона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.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
