Изменения

'''Алгоритм Форда — -Фалкерсона ''' — алгоритм, решающий задачу нахождения максимального [[Определение сети, потока #Определение потока | потока ]] в транспортной сети.

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение <tex>0</tex>: <tex> f(u,v) = 0 </tex> для всех <tex> u, v </tex> из <tex> V </tex>. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника <tex>s </tex> к стоку <tex>t</tex>, вдоль которого можно послать ненулевой поток). В данной статье рассматривается алгоритм, осуществляющий этот поиск с помощью [[Обход в глубину, цвета вершин|обхода в глубину (dfs)]]. Процесс повторяется, пока можно найти увеличивающий путь.

'''int''' dfs('''int''' u, '''int''' Cmin) : <span style="color:Green">// Cmin {{---}} пропускная способность в текущем подпотоке</span> '''if (''' u = t) '''return ''' Cmin visited[u.vis <- ] = ''true'' '''for ''' v '''in''' u.children '''auto''' uv = edge(uv in Eu, v) '''if (!''' '''not''' visited[v.vis) && (] '''and''' uv.f < uv.c) дельта <- '''int''' delta = dfs(v, min(Cmin, uv.c - uv.f)) '''if (дельта ''' delta > 0) { uv.f += дельтаdelta uv.backEdge.f -= дельтаdelta '''return дельта''' delta } } '''return''' 0

Добавляя поток увеличивающего пути к уже имеющемуся потоку, максимальный поток будет получен, когда нельзя будет найти увеличивающий путь. Тем не менее, если величина пропускной способности — иррациональное число, то алгоритм может работать бесконечно. В целых числах таких проблем не возникает и время работы ограничено <tex>O(|E|f|)</tex>, где <tex>E</tex> — число рёбер в графе, <tex>f</tex> — максимальный поток в графе, так как каждый увеличивающий путь может быть найден за <tex>O(E)</tex> и увеличивает поток как минимум на <tex>1</tex>.

[[Файл:F-f.5.png|300px|thumb|right|рисРис. 1]]Рассмотрим приведённую справа сеть, с источником <mathtex>\ s</mathtex>, стоком <mathtex>\ t</mathtex>, пропускными способностями рёбер <mathtex>\ e_1</mathtex>, <mathtex>\ e_2</mathtex> и <mathtex>\ e_3</mathtex> соответственно <mathtex>\ 1</mathtex>, <mathtex>r=(\dfrac{\sqrt{5}-1)/}{2}</mathtex> и <mathtex>\ 1</mathtex> и пропускной способностью всех остальных рёбер, равной целому числу <mathtex>M \ge geqslant 2</mathtex>. Константа <mathtex>\ r</mathtex> выбрана так, что <mathtex>\ r^2 = 1 - r</mathtex>. Мы используем пути из остаточного графа, приведённые в таблице, причём <mathtex>\ p_1 = \{ s, v_4, v_3, v_2, v_1, t \}</mathtex>, <mathtex>\ p_2 = \{ s, v_2, v_3, v_4, t \}</mathtex> и <mathtex>\ p_3 = \{ s, v_1, v_2, v_3, t \}</mathtex>.

! valign="top" rowspan=2 | Шаг !! valign="top" rowspan=2 | Найденный путь !! valign="top" rowspan=2 | Добавленный поток !! colspan=3 | Остаточные пропускные способности

! <mathtex>e_1</mathtex> !! <mathtex>e_2</mathtex> !! <mathtex>e_3</mathtex>

| <tex>0 </tex> || <tex>-</tex> || <tex>-</tex> || <mathtex>r^0=1</mathtex> || <mathtex>r</mathtex> || <mathtex>1</mathtex>

| <tex>1 </tex> || <mathtex>\{ s, v_2, v_3, t \}</mathtex> || <mathtex>1</mathtex> || <mathtex>r^0</mathtex> || <mathtex>r^1</mathtex> || <mathtex>0</mathtex>

| <tex>2 </tex> || <mathtex>p_1</mathtex> || <mathtex>r^1</mathtex> || <mathtex>r^2</mathtex> || <mathtex>0</mathtex> || <mathtex>r^1</mathtex>

| <tex>3 </tex> || <mathtex>p_2</mathtex> || <mathtex>r^1</mathtex> || <mathtex>r^2</mathtex> || <mathtex>r^1</mathtex> || <mathtex>0</mathtex>

| <tex>4 </tex> || <mathtex>p_1</mathtex> || <mathtex>r^2</mathtex> || <mathtex>0</mathtex> || <mathtex>r^3</mathtex> || <mathtex>r^2</mathtex>

| <tex>5 </tex> || <mathtex>p_3</mathtex> || <mathtex>r^2</mathtex> || <mathtex>r^2</mathtex> || <mathtex>r^3</mathtex> || <mathtex>0</mathtex>

Заметим, что после шага <tex>1</tex>, как и после шага <tex>5</tex>, остаточные способности рёбер <mathtex>e_1</mathtex>, <mathtex>e_2</mathtex> и <mathtex>e_3</mathtex> имеют форму <mathtex>r^n</mathtex>, <mathtex>r^{n+1}</mathtex> and и <mathtex>0</mathtex>, соответственно, для какого-то натурального <mathtex>n</mathtex>. Это значит, что мы можем использовать увеличивающие пути <mathtex>p_1</mathtex>, <mathtex>p_2</mathtex>, <mathtex>p_1</mathtex> и <mathtex>p_3</mathtex> бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме.Полный поток после шага <tex>5 </tex> равен <mathtex>1 + 2(r^1 + r^2)</mathtex>. За бесконечное время полный поток сойдётся к <mathtex>\textstyle 1 + 2\sum_sum\limits_{i=1}^\infty r^i = 3 + 2r</mathtex>, тогда как максимальный поток равен <mathtex>2M + 1</mathtex>. Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению.

При использовании поиска в ширину алгоритму потребуется всего лишь 2 два шага.Дана сеть (рисРис. 2).[[Файл:F-f.1.png|thumb|300px|center|рисРис. 2]]Благодаря двум итерациям (рисРис. 3 и рисРис. 4)[[Файл:F-f.2.png|thumb|300px|center|рисРис. 3]][[Файл:F-f.3.png|thumb|300px|center|рисРис. 4]]рёбра <tex>AB, AC, BD, CD</tex> насытились лишь на <tex>1</tex>.Конечная сеть будет получена ещё через 1998 итераций (рисРис. 5).[[Файл:F-f.4.png|thumb|300px|center|рисРис. 5]]

== Литература Источники информации ==* [http://ru.wikipedia.org/wiki/Алгоритм_Форда_—_Фалкерсона Википедия: Алгоритм Форда — Фалкерсона] <br>* Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1