мітімо, что ЯКЩО пропускні здатності симетричних дуг Рівні между собою те ЦІ дуги могут буті замінені ребрами Будемо позначаті ятір. Де - множини дуг або ребер. Сформулюємо задачу. Знайте невід'ємні значення (для всіх), Які максімізують
(3.1)
при ОБМЕЖЕНОЮ:
(3.2)
. (3.3)
Умова (3.1) відображає величину максимального потоку, Який Рівний кількості Речовини, яка вітікає Із джерела, або кількості Речовини, яка потрапляє в СТІК. Умова (3.2) означає, что Потік по Кожній дузі має буті невідємнім и НЕ перевіщуваті ее пропускну здатність. Із умови (3.3) віпліває, что кількість Речовини, что потрапляє до будь-якої проміжкової вершини, дорівнює кількості, Речовини, яка вітікає з неї.
ВАЖЛИВО роль в обґрунтуванні алгоритмом розв «язання задачі про Максимальний Потік відіграє Поняття розрізу. Розіб »ємо множини всех вершин мережі на Дві підмножіні, Які НЕ перетінаються и так, щоб,. Если віділіті ВСІ дуги, Початкові вершини Котре належати підмножіні R, а кінцеві -, то ЦІ дуги 6удуть утворюваті Розріз, Який відокремлює джерело від стоку. Таким чином, розрізом назівається сукупніть всех дуг, Які Прокуратура: з вершин и закінчуються у вершинах.
Коженая Розріз характерізується Пропускна здатністю, яка чисельного дорівнює сумі пропускних здатностей дуг, что его утворюють:
.
Очевидно, что будь-який шлях Із джерела в СТІК містіть хочай б одну дугу розрізу. Тому, ЯКЩО ВИДАЛИТИ ВСІ дуги будь-якого розрізу, то Всі шляхи Із джерела в СТІК будут заблоковані. Оскількі Пропускна здатність шляху рівна найменшій Із пропускних здатностей дуг, Які належати до цього шляху, то величина потоку, Який перемішується по всех, можливіть шляхах, Які з'єднують з, що не может перевіщуваті пропускну здатність будь-якого розрізу мережі, тоб,. 3 цього віпліває что, ЯКЩО вдається побудуваті такий шлях, что его величина буде рівною пропускній здатності Деяк розрізу, то цею Потік и буде максимальним.
Теорема (Форда-Фалкерсона) У будь-якій мережі максимальна величина потоку Із джерела в СТІК дорівнює мінімальній пропускній здатності розрізу, Який розділяє від.
3.2 Алгоритм Форда знаходження максимального потоку
Розглянемо табличний алгоритм Форда знаходження максимального потоку в мережі, Який Складається з послідовності кроків.
Початковий етап. Запісуємо пропускну здатність дуг мережі в таблиці розмірності, де - кількість вершин мережі G (E, e).
Основний етап. Основний етап, Який повторюється, Складається з трьох Дій.
. Знаходимо по табліці шлях з в з пропускними здатністю більшою за нуль. Для цього стовпчік, Який відповідає Джерелу Е0 помічаємо символом *. Шукаємо в-му рядку елєменти, и стовпці в якіх смороду знаходяться, помічаємо зверху номером рядка, Який розглядаємо (тоб цифрою 0). У результаті будут віділені ВСІ дуги () з додатного Пропускна здатністю. ЦІ дуги могут буті дерло дугами шляху з в.
Далі розглянемо ті рядки, номери якіх співпадають з номерами поміченіх стовпців. У кожному такому рядку, Наприклад-овому, шукаємо елєменти> 0, Які знаходяться в непоміченіх стовпцях, и помічаємо ЦІ стовпці номером розглядуваного рядка. Таким чином, ми віділяємо ті дуги, Які могут буті іншими дугами шляху з Е0 в Е. Продовжуємо аналогічній переглядання рядків, номери якіх співпадають з номером поміченіх стовпців, до тихий ПІР, поки:
...
