одна вершина, з якої не виходить жодної дуги; ця вершина називається
стоком або
кінцем мережі .
Потоком мережі називається неотрицательная функція f (1) така, що f (e) менше або дорівнює c (e). (Потік не може перевищувати пропускну здатність дуги.)
Дуга називається насиченою потоком f, якщо (Потік називається повним , якщо містить насичену дугу f (e) = c (e).)
Розрізом L мережі G (V, E) називається безліч насичених дуг, що відокремлюють джерело s від стоку t.
Теорема Форда-Фалкерсона.
Нехай D - транспортна мережа, - допустимий потік у цій мережі, - безліч вершин таких, що довжина мінімального шляху з о в орграфе збільшень дорівнює нулю. Тоді, якщо, то - максимальний потік, величина якого дорівнює. p> Нехай. Тоді виконується рівність
(1)
В
Якщо, тому що в противному випадку, використовуючи маємоВ , А отже, в силу існує шлях нульової довжини з вВ , Що суперечить умові. Але тоді з (1) отримуємо
В
Слідство 1. Використовуючи теорему Форда-Фалкерсона отримуємо, що величина максимального потоку в транспортної мережі дорівнює пропускної здатності мінімального розрізу.
Слідство 2. Нехай - допустимий потік в транспортній мережі D. Тоді, якщо довжина мінімального шляху з v1 у vn в орграфе збільшень дорівнює нескінченності, то - максимальний потік.
Алгоритм рішення.
Спочатку будемо будувати повний потік, потім перевіримо, чи можна його збільшити. Якщо ні, то цей потік є максимальним. Якщо ж його можна збільшити, то будемо будувати інший повний потік і т.д. Вирішувати завдання будемо з допомогою методу розстановки позначок. p> Дві основні процедури (Операції алгоритму):
В· операція розстановки позначок;
В· операція зміни потоку.
Розглянемо першу процедуру. Для кожної вершини даної мережі потрібно приписати позначку, яка має наступний вид: або де, а - натуральне число або нескінченність. Взагалі можливі три стану вершини:
1) НЕ позначена;
2) позначена, але не оглядена;
3) позначена та оглядена.
Розставляти позначки почнемо з джерела S. Він отримає позначку Джерело позначений, але не переглянутий. Решта вершини не помічені. Щоб джерело S був позначений і переглянутий, треба помістити всі вершини, суміжні з S.
Вершина отримає позначку, де.
Тепер всі вершини суміжні з S, помічені, але не переглянуті. А вершина S позначена та оглядена. Почнемо переглядати ту з вершин, яка має найменший індекс. Для цього потрібно розставити позначки вершин, суміжних з. Якщо для вершини виконується наступне умова, то вона отримає мітку, де. Якщо ж для вершини виконується умова, то отримує мітку, де. Далі переглядаємо наступну вершину, і так до тих пір, поки не пометим сток t або ж поки не можна буде більше помітити ні однієї верши...
