Поняття залишкової мережі - студопедія
Теорема Форда-Фалкерсона: У будь-якій мережі максимальна величина потоку з витоку в стік дорівнює мінімальній пропускній здатності розрізу відокремлює від.
Завдання про максимальний потік
Мережа - це орієнтований граф. кожному ребру якого поставлено у відповідність число. зване пропускною спроможністю, а також виділено дві вершини - витік витік.
Потік - це функція. володіє трьома властивостями:
- величина вхідного потоку для вершини
- величина вихідного потоку для вершини
Розглянемо орієнтований граф. Будемо розглядати його як мережу труб, по яких деяка речовина рухається від витоку (де воно проводиться з постійною швидкістю) до стоку (де воно споживається - з тією ж швидкістю). Замість потоків речовини можна розглядати рух струму по проводах, деталей по конвеєру, інформації по лініях зв'язку або товарів від виробника до споживача.
Як і в завданні про найкоротших шляхах, на кожному ребрі графа ми пишемо число. Але якщо раніше це число означало довжину шляху, то тепер це швидше ширина дороги, або пропускна здатність труби - максимальна швидкість потоку в цій трубі.
Ми вважаємо, що в вершинах речовина не накопичується - скільки приходить, стільки і йде (якщо вершина не є джерелом або стоком).
Завдання про максимальний потік для даної мережі полягає в наступному: знайти максимально можливу швидкість виробництва (і споживання) речовини, при якій його ще можна доставити від витоку до стоку при даних пропускних спроможностях труб.
Ключову роль в методі Форда-Фалкерсона грають два поняття: залишкові мережі і доповнюють шляху.
Пошук максимального потоку даним методом проводиться по кроках. Спочатку потік нульовий (і величина його дорівнює нулю). На кожному кроці ми збільшуємо значення потоку. Для цього ми знаходимо "доповнює шлях", по якому можна пропустити ще трохи речовини, і використовуємо його для збільшення потоку. Цей крок повторюється, поки є що доповнюють шляху. Як випливає з теорії, отриманий потік буде максимальним.
Нехай дана мережа і потік в ній. Тоді залишкова мережа складається з тих ребер (званих також залишковими), потік за якими можна збільшити. Зауважимо, що залишкове ребро повинно бути ребром вихідної мережі. Такі "дивні" ребра з'являються коли є потік речовини в зворотному напрямку - адже цей потік можна зменшити.
У залишкових мереж є цікава властивість - якщо в остаточний мережі існує потік f, то додавши його до вихідного потоку в мережі, ми отримаємо також потік, що задовольняє всім вимогам, але який більше вихідного.
Назвемо доповнює шляхом простої шлях з витоку в стік в залишкової мережі. З визначення залишкової мережі випливає, що по всіх ребрах доповнює шляху можна переслати ще скільки-то речовини, що не перевищивши їх пропускну здатність. Величину найбільшого потоку, який можна переслати по доповнює шляху назвемо залишкової пропускною спроможністю шляху. Очевидно, вона дорівнює значенню мінімального залишкового ребра, що входить в даний шлях.
Мережа. - пропускна здатність дуги