Теорема про максимальний потік, мінімальний розріз

Теорема ^[ru] — ^[ru] — теорема про найбільший потік у графі, тісно пов'язана з теоремою Менгера.

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

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

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

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

Інше доведення (через посилення)

Посилимо теорему Форда — Фалкерсона. Доведемо для мережі ${\displaystyle G(V,E)}$ з потоком f рівносильність одразу трьох таких фактів:

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

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

3° У графі ${\displaystyle G}$ немає шляху розширення.

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

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

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

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

Приклад

Мережа з двома найменшими розрізами

Праворуч показно мережу з 6 вершинами ${\displaystyle V=\{s,o,p,q,r,t\}}$, де сумарний потік від витоку ${\displaystyle s}$ до стоку ${\displaystyle t}$ дорівнює 5. Цей потік є найбільшим для цієї мережі.

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

Література

• Новиков Ф. А. Дискретная математика для программистов. — 3-е. — СПб. : , 2009. — С. 277—279. — .

Посилання

• Алгоритм Форда — Фалкерсона на algolist.manual.ru.(рос.)
• Мережі, потоки у мережах. Теорема Форда — Фалкерсона на Mini-Soft.ru (рос.)