Перегляд вихідного коду сторінки Теорема Форда — Фалкерсона

'''Теорема {{Нп|Лестер Форд|Форда|ru|Форд, Лестер}}&nbsp;— {{Нп|Делберт Рей Фалкерсон|Фалкерсон|ru|Фалкерсон, Делберт Рей}}'''&nbsp;— теорема про найбільший [[Потокова мережа|потік]] у [[Граф (математика)|графі]], тісно пов'язана з [[Теорема Менгера|теоремою Менгера]].

'''Формулювання''': величина найбільшого потоку в графі шляхів дорівнює величині пропускної спроможності його найменшого [[Розріз (теорія графів)|розрізу]].

'''Достатність''': будь-який потік між вершинами ''t'' і ''s'' менший або дорівнює величині будь-якого [[Розріз (теорія графів)|розрізу]]. Нехай дано деякий потік і деякий розріз. Величина цього потоку складається з величин «вантажів», що перевозяться по всіх можливих шляхах з вершини ''t'' до ''s''. Кожен такий шлях повинен мати спільне ребро з цим розрізом. Оскільки по кожному ребру перерізу сумарно не можна перевезти «вантажу» більше, ніж його пропускна здатність, то сума всіх вантажів менша або дорівнює сумі всіх пропускних здібностей ребер даного розрізу. Твердження доведено.

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

На цій теоремі ґрунтується [[алгоритм Форда — Фалкерсона]] пошуку найбільшого потоку в графі, він же є доведенням необхідності даної теореми, тобто воно є конструктивним.

== Інше доведення (через посилення) ==
Посилимо теорему Форда&nbsp;— Фалкерсона. Доведемо для мережі <math>G(V,E)</math> з потоком f рівносильність одразу трьох таких фактів:

1° Потік f найбільший.

2° Пропускна здатність найменшого розрізу дорівнює величині потоку f.

3° У графі <math>G</math> немає [[Потокова мережа|шляху розширення]].


1 ° → 3 °. Припустивши протилежне, отримаємо суперечність, описану в [[Потокова мережа|інформації щодо шляху розширення в транспортному графі]].

3 ° → 2 °. Очевидно, що величина потоку <math>f</math> не перевищує пропускної здатності найменшого розрізу <math>(S,T)</math>. Нехай <math>c(S,T)>f</math>. Розглянемо розріз, де у множині <math>S</math> будуть усі вершини, крім <math>t</math>. Його пропускна здатність не менша за пропускну здатність найменшого розрізу, що, у свою чергу, більше від величини потоку <math>f</math>. Отже, існує напрямок <math>(u,t)</math> з <math>S</math> у <math>T</math>, що <math>f(u,t)<c(u,t)</math>. Тепер візьмемо всі такі <math>u</math> і перенесемо їх у <math>T</math>. Розглянувши розріз, що вийшов, зауважимо, що його пропускна здатність теж більша від величини потоку. Знову збільшуємо множину <math>T</math> і робимо так доти, поки у множині <math>S</math> залишиться тільки вершина <math>s</math>. Вона ж буде першою вершиною в шляху, який ми створюємо. Тепер дивимося, яку пару ми вибрали минулим ходом. Нехай це пара <math>(s,u)</math>. Тоді до шляху додаємо вершину <math>u</math>. Далі дивимось, у парі з якою вершиною була на першому місці вершина <math>u</math>. Нехай це <math>(u,v)</math>. Тоді далі до шляху додаємо вершину <math>v</math>. Робимо так доти, доки не дійдемо до вершини <math>t</math>. Однак за побудовою цей шлях є залишковим{{Прояснити}}, що суперечить припущенню.

2 ° → 1 °. Як сказано раніше, очевидно, що величина будь-якого потоку не перевищує пропускної спроможності найменшого розрізу, а величина нашого потоку <math>f</math> дорівнює їй. Тоді величина потоку <math>f</math> не менше від величини будь-якого іншого потоку в нашій мережі, тобто потік <math>f</math> максимальний.

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

== Приклад ==
[[Файл:Max_flow.svg|міні| Мережа з двома найменшими розрізами]]
Праворуч показно мережу з 6 вершинами <math>V = \{s,o,p,q,r,t\}</math>, де сумарний потік від витоку <math>s</math> до стоку <math>t</math> дорівнює 5. Цей потік є найбільшим для цієї мережі.

У цій мережі можливі 2 найменші розрізи:

== Література ==
* {{Книга
|автор = Новиков Ф. А.
|посилання = https://archive.org/details/isbn_9785911807597
|видання = 3-е
|місце = {{СПб.}}
|видавництво = [[Питер (видавництво)|Питер]]
|рік = 2009
|сторінки = [https://archive.org/details/isbn_9785911807597/page/n276 277—279]
|сторінок = 384
|ISBN = 978-5-91180-759-7
|назва = Дискретная математика для программистов
}}

== Посилання ==
* [http://algolist.manual.ru/maths/graphs/maxflows/Ford_Fulkerson.php Алгоритм Форда&nbsp;— Фалкерсона] на algolist.manual.ru.{{Ref-ru}}
* [http://mini-soft.ru/nstu/diskr/12_.php Мережі, потоки у мережах. Теорема Форда&nbsp;— Фалкерсона] на Mini-Soft.ru {{Ref-ru}}
{{перекласти|en|Max-flow min-cut theorem}}
[[Категорія:Теореми теорії графів]]
[[Категорія:1962 у науці]]