Перегляд вихідного коду сторінки Задача про максимальний потік

[[Файл:Max flow.svg|thumb|upright=1.5|Максимальний потік в транспортній мережі. Числа позначають потоки і пропускні властивості.]]
В [[Оптимізація (математика)|теорії оптимізації]] та [[Теорія графів|теорії графів]], '''задача про максимальний потік''' полягає у знаходженні такого [[Потокова мережа#Визначення|потоку]] за [[Потокова мережа|транспортною мережею]], щоб сума потоків з витоку, або, що означає те ж саме, сума потоків до стоку була максимальна.

Задача про максимальний потік є окремим випадком більш складних задач, таких, як, наприклад, задача про циркуляцію.

== Історія ==
Після [[Напад на Перл-Гарбор|вступу США у Другу світову війну]] у 1941 році математик [[Джордж Данціг|Джордж Бернард Данціг ]] почав працювати у відділі статистичного управління [[Військово-повітряні сили США|Військово-повітряних сил США]] у [[Вашингтон]]і. З 1941 по 1946 роки він очолював підрозділ аналізу військових дій (Combat Analysis Branch), де працював над різноманітними математичними проблемами.<ref>{{MacTutor Biography|id=Dantzig_George|title=George Dantzig}}</ref><ref>Cottle, Richard; Johnson, Ellis; Wets, Roger, [http://www.stanford.edu/group/SOL/GBD/cottle-johnson-wets-2007.pdf «George B. Dantzig (1914–2005)»] {{Webarchive|url=https://web.archive.org/web/20150907195444/http://stanford.edu/group/SOL/GBD/cottle-johnson-wets-2007.pdf |date=7 вересня 2015 }}, ''Notices of the American Mathematical Society'', v.54, no.3, March 2007. Cf. p.348</ref> Згодом з використанням роботи Данцига задача про максимальний потік була вперше розв'язана у ході підготовки повітряного мосту під час [[Берлінський повітряний міст|Берлінського повітряного мосту]], що відбувався у 1948–1949 роках.<ref name="MIT2010">Hardesty, Larry, [http://web.mit.edu/newsoffice/2010/max-flow-speedup-0927.html «First improvement of fundamental algorithm in 10 years»] {{Webarchive|url=https://web.archive.org/web/20140328104600/http://web.mit.edu/newsoffice/2010/max-flow-speedup-0927.html |date=28 березня 2014 }}, MIT News Office, September 27, 2010</ref><ref>Borndörfer, Ralf; Grötschel, Martin; Löbel, Andreas, [http://www.zib.de/Publications/Reports/SC-95-27.pdf «Alcuin's Transportation Problems and Integer Programing»] {{Webarchive|url=https://web.archive.org/web/20110807120135/http://www.zib.de/Publications/Reports/SC-95-27.pdf |date=7 серпня 2011 }}, ''Konrad-Zuse-Zentrum für Informationstechnik'', Berlin, Germany, November 1995. Cf. p.3</ref><ref>Powell, Stewart M., [http://www.airforce-magazine.com/MagazineArchive/Pages/1998/June%201998/0698berlin.aspx «The Berlin Airlift»], ''Air Force Magazine'', June 1998.</ref>

У 1951 році Джордж Данциг вперше сформулював задачу у загальному вигляді.<ref>Dantzig, G.B., [http://cowles.econ.yale.edu/P/cm/m13/m13-23.pdf «Application of the Simplex Method to a Transportation Problem»] {{Webarchive|url=https://web.archive.org/web/20100719015952/http://cowles.econ.yale.edu/P/cm/m13/m13-23.pdf |date=19 липня 2010 }}, in T.C. Koopman (ed.): ''Activity Analysis and Production and Allocation'', New York, (1951) 359–373.</ref>

У 1955 році {{нп|Лестер Форд|||L. R. Ford Jr.}} і {{Не перекладено|Фалкерсон, Делберт|Делберт Фалкерсон||D. R. Fulkerson}} вперше побудували алгоритм, призначений для вирішення цього завдання. Їх алгоритм отримав назву [[Алгоритм Форда — Фалкерсона|алгоритм Форда&nbsp;— Фалкерсона]].<ref>Ford, L.R., Jr.; Fulkerson, D.R., «Maximal Flow through a Network», ''Canadian Journal of Mathematics'' (1956), pp.399-404.</ref><ref>Ford, L.R., Jr.; Fulkerson, D.R., ''Flows in Networks'', Princeton University Press (1962).</ref>

Надалі рішення задачі багато разів поліпшувалося.

У 2010 році дослідники Джонатан Келнер (Jonathan Kelner) і Олександр Мондри (Aleksander Mądry) з [[Массачусетський технологічний інститут|МТІ]] разом зі своїми колегами [[Даніель Спілман|Даніелєм Спілманом]] з [[Єльський університет|Єльського університету]] і {{Нп|Шень-Хуа Тен|Шень-Хуа Тенем||Shang-Hua Teng}} з [[Університет Південної Каліфорнії|університету Південної Каліфорнії]] продемонстрували чергове покращення алгоритму, вперше за 10 років.<ref name="MIT2010"/><ref>Kelner, Jonathan, [http://www.csail.mit.edu/events/eventcalendar/calendar.php?show=event&id=2711 «Electrical Flows, Laplacian Systems and Faster Approximation of Maximum Flow in Undirected Graphs»] {{Webarchive|url=https://web.archive.org/web/20110624084844/http://www.csail.mit.edu/events/eventcalendar/calendar.php?show=event&id=2711 |date=24 червня 2011 }}, talk at CSAIL, MIT, Tuesday, September 28 2010</ref><ref>[http://math.mit.edu/~kelner/Publications/Docs/maxFlow.pdf Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs] {{Webarchive|url=https://web.archive.org/web/20101129012854/http://math.mit.edu/~kelner/Publications/Docs/maxFlow.pdf |date=29 листопада 2010 }}, by Paul Cristiano et al., October 19, 2010.</ref>

== Визначення ==
Розглянемо [[Потокова мережа|транспортну мережу]] <math>\scriptstyle N = (V, E)</math> з джерелом <math>\scriptstyle s \in V</math>, стоком <math>\scriptstyle t \in V</math> та пропускними здатностями <math>\scriptstyle c</math>.

: '''Величиною [[Потокова мережа#Визначення|потоку]]''' ('''value of flow''') називається сума потоків з джерела <math>\scriptstyle |f| = \sum_{v \in V} f_{sv}</math>. У статті «[[Потокова мережа|Транспортна мережа]]» доведено, що вона дорівнює сумі потоків у сток <math>\ \sum_{w \in V} f(w,t)</math>.

'''Задача про максимальний потік ''' полягає в знаходженні потоку такого, щоб величина потоку була максимальна.

== Розв'язання ==
В таблиці перераховано деякі алгоритми розв'язування задачі.
{| class="wikitable"
! Метод
! Складність
! Опис
|-
| [[Лінійне програмування]]
| Залежить від конкретного алгоритму.<br/> Для [[симплекс-метод]]у експоненціальна.
| Розглянемо задачу про максимальний потік як задачу лінійного програмування. Змінними є потоки по ребрах, а обмеженнями&nbsp;— збереження потоку й обмеження пропускної здатності.
|-
| [[Алгоритм Форда — Фалкерсона|Алгоритм Форда&nbsp;— Фалкерсона]]
| Залежить від алгоритму пошуку шляху, що збільшується.<br/> Потребує ''O''(max<nowiki>|</nowiki> ''f'' <nowiki>|</nowiki>) таких пошуків.
| Знайти будь-який шлях, що збільшується. Збільшити потік по всіх його ребрах на мінімальну з їх залишкових пропускних здатностей. Повторювати, поки є шлях, що збільшується. Алгоритм працює тільки для цілих пропускних здатностей. В іншому випадку, він може працювати нескінченно довго, не сходячись до правильної відповіді.
|-
| [[Алгоритм Едмондса-Карпа]]
| ''O''(''VE''²)
| Виконуємо алгоритм Форда&nbsp;— Фалкерсона, щоразу обираючи '' найкоротший '' шлях, що збільшується (знаходиться [[Пошук у ширину| пошуком у ширину]]).
|-
| [[Алгоритм Дініца]]
| ''O''(''V''²''E'')<br/> <math>\scriptscriptstyle  O(V\sqrt{E})</math> для одиничних пропускних здатностей<br/> <math>O(VE\log(V))</math> з використанням динамічних дерев Слетора і Тар'яна<ref>{{Cite web |url=http://e-maxx.ru/algo/dinic |title=Алгоритм Диница |accessdate=18 травня 2015 |archive-date=7 травня 2015 |archive-url=https://web.archive.org/web/20150507002725/http://e-maxx.ru/algo/dinic }}</ref>
| Удосконалення алгоритму Едмондса-Карпа (але хронологічно був знайдений раніше). На кожній ітерації, використовуючи пошук у ширину, визначаємо відстані від джерела до всіх вершин у залишковій мережі. Будуємо граф, який містить лише такі ребра залишкової мережі, на яких ця відстань зростає на 1. Виключаємо з графу усі тупикові вершини з інцидентними їм ребрами, поки всі вершини стануть не тупиковими. (Тупиковою називається вершина, в яку не входить і з якої не виходить жодне ребро, крім джерела і стоку.) На отриманому графі відшукуємо найкоротший шлях, що збільшується (їм буде будь-який шлях з s в t). Виключаємо із залишкової мережі ребро з мінімальною пропускною здатністю, знову виключаємо тупикові вершини, і так поки ще існують шляхи, що збільшуються.
|-
| {{нп|Алгоритм просовування предпотоку|||Push–relabel maximum flow algorithm}}
| ''O''(''V''²''E'')
| Замість потоку оперує з передпотоком. Різниця в тому, що для будь-якої вершини u, крім джерела і стоку, сума потоків, що входять до неї для потоку повинна бути строго нульовою (умова збереження потоку), а для передпотока&nbsp;— невід'ємною. Ця сума називається '' надмірним потоком '' у вершину, а вершина з позитивним надмірним потоком називається '' переповненою ''. Крім того, для кожної вершини алгоритм зберігає додаткову характеристику, '' висоту'', яка є цілим невід'ємним числом. Алгоритм використовує дві операції: '' просування '', коли потік по ребру, що йде з більш високої в нижчу вершину, збільшується на максимально можливу величину, і '' підйом '', коли переповнена вершина, просування з якої неможливо через недостатню висоту, підіймається. Просування можливо, коли ребро належить залишковій мережі, коли воно веде з більш високої вершини в більш низьку, і вихідна вершина переповнена. Підйом можливий, коли вершина, що піднімається, переповнена, але жодна з вершин, в котру з неї ведуть ребра залишкової мережі, не нижче за неї. Він вчиняється до висоти на 1 більшою, ніж мінімальна з висот цих вершин. Спочатку висота джерела V, по всім ребрам, що виходять з джерела, тече максимально можливий потік, а решта висоти і потоки нульові. Операція просування і підйому виконуються до тих пір, поки це можливо.
|-
| {{нп|Алгоритм просовування предпотоку|Алгоритм «підняти на початок»||Push–relabel maximum flow algorithm}}
| ''O''(''V''³)<br/>''O''(''VE'' log(''V''²/''E'')) з використанням динамічних дерев
| Варіант попереднього алгоритму, що спеціальним чином визначає порядок операцій просовування і підйому.
|-
|Алгоритм двійкового блокуючого потоку {{ref|GR97}}
| <math>\scriptscriptstyle O(E\min(V^{2/3},\sqrt{E})\log(V^2/E)\log{\max{|f|}})</math>
|
|}

Для детальнішого списку, див. {{ref|GT88}}.

== Теорема про цілий потік ==
'''Якщо пропускні спроможності цілі, максимальна величина потоку теж ціла.'''

Теорема випливає, наприклад, з [[Теорема Форда — Фалкерсона|теореми Форда — Фалкерсона]].

== Узагальнення, що зводяться до вихідної задачі ==
Деякі узагальнення задачі про максимальний потік легко зводяться до вихідної задачі.

=== Довільне число джерел та / або стоків ===
[[Файл:Multi-source multi-sink flow problem.svg|thumb|right|Трансформація задачі з довільною кількість джерел і стоків до початкової задачі]]&nbsp;
Якщо джерел більше одного, додаємо нову вершину S, яку робимо єдиним джерелом. Додаємо ребра з нескінченною пропускною здатністю від S до кожного зі старих джерел.

Аналогічно, якщо стоків більше одного, додаємо нову вершину T, яку робимо єдиним стоком. Додаємо ребра з нескінченною пропускною здатністю від кожного зі старих стоків до T.

=== Неорієнтовані ребра ===
Кожне неорієнтоване ребро (u, v) замінюємо на пару орієнтованих ребер (u, v) і (v, u).

=== Обмеження пропускної здатності вершин ===
[[Файл:Node splitting.svg|thumb|right|Трансформація задачі з обмеженою пропускною здатністю вершин до початкової задачі шляхом розщеплення вершин]]
Кожну вершину v з обмеженою пропускною здатністю <math>c_v</math> розщеплюємо на дві вершини v<sub>in</sub> і v<sub>out</sub>. Всі ребра, які до розщеплення входять до v, тепер входять в v<sub>in</sub>. Всі ребра, які до розщеплення виходять з v, тепер виходять з v<sub>out</sub>. Додаємо ребро (v<sub>in</sub>,v<sub>out</sub>) з пропускною здатністю <math>c_v</math>.

== Див. також ==
* [[Потокова мережа]]

== Примітки ==
{{примітки}}

== Література ==
* Schrijver, Alexander, [http://homepages.cwi.nl/~lex/files/histtrpclean.pdf «On the history of the transportation and maximum flow problems»] {{Webarchive|url=https://web.archive.org/web/20141110042025/http://homepages.cwi.nl/~lex/files/histtrpclean.pdf |date=10 листопада 2014 }}, ''Mathematical Programming'' 91 (2002) 437—445
* {{CLRS|chapter=26. Максимальний потік}}
* {{Note|GR97}}{{cite journal
 | author = {{iw|Andrew V. Goldberg}} and S. Rao
 | title = Beyond the flow decomposition barrier
 | journal = J. Assoc. Comput. Mach.
 | volume = 45
 | pages = 753–782
 | year = 1998
 | doi = 10.1145/290179.290181
}}
* {{Note|GT88}}{{cite journal
 | author = {{iw|Andrew V. Goldberg}} and [[Роберт Андре Тар'ян|Robert E. Tarjan]]
 | title = A new approach to the maximum-flow problem
 | journal = Journal of the ACM
 | volume = 35
 | year = 1988
 | issn = 0004-5411
 | pages = 921–940
 | doi = 10.1145/48014.61051
 | publisher = ACM Press
 | розміщення       = New York, New York, U.S.
 | issue = 4
}}
* {{Note|HA99}}{{cite journal
 | author = {{нпні|Joseph Cheriyan}} and [[Курт Мельгорн|Kurt Mehlhorn]]
 | title = An analysis of the highest-level selection rule in the preflow-push max-flow algorithm
 | journal = Information Processing Letters
 | volume = 69
 | year = 1999
 | pages = 239–242
 | doi = 10.1016/S0020-0190(99)00019-8
 | issue = 5
}}
* {{Note|ST83}}{{cite journal
 | author = [[Деніел Слітор|Daniel D. Sleator]] and [[Роберт Андре Тар'ян|Robert E. Tarjan]]
 | title = A data structure for dynamic trees
 | journal = Journal of Computer and System Sciences
 | volume = 26
 | year = 1983
 | issn = 0022-0000
 | pages = 362–391
 | doi = 10.1016/0022-0000(83)90006-5
 | url = http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf
 | issue = 3
 | accessdate = 18 травня 2015
 | archive-date = 14 травня 2015
 | archive-url = https://web.archive.org/web/20150514064947/http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf
 }}
* {{Note|ST85}}{{cite journal
 | author = [[Деніел Слітор|Daniel D. Sleator]] and [[Роберт Андре Тар'ян|Robert E. Tarjan]]
 | title = Self-adjusting binary search trees
 | journal = Journal of the ACM
 | volume = 32
 | year = 1985
 | issn = 0004-5411
 | pages = 652–686
 | doi = 10.1145/3828.3835
 | publisher = ACM Press
 | розміщення = New York, New York, U.S.
 | url = http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
 | issue = 3
 | accessdate = 18 травня 2015
 | archive-date = 5 березня 2015
 | archive-url = https://web.archive.org/web/20150305221817/http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
 }}
* {{cite book | author =  Eugene Lawler | authorlink = Eugene Lawler | title = Combinatorial Optimization: Networks and Matroids | chapter = 4. Network Flows | year = 2001 | publisher = Dover | isbn = 0486414531 | pages = 109–177}}
{{Алгоритми на графах}}
{{Математика-доробити}}

[[Категорія:Алгоритми на графах]]