Стисла теоретична довідка. Транспортною мережею (чи просто мережею) у теорії графів називають орієнтований зважений граф, що задовольняє наступним умовам:

Транспортною мережею (чи просто мережею) у теорії графів називають орієнтований зважений граф, що задовольняє наступним умовам:

1) відсутні петлі;

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

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

4) кожній дузі поставлено у відповідність невід’ємне ціле число , що називається пропускною спроможністю дуги.

Потік у мережі — це функція, що ставить у відповідність дугам даної мережі деякі невід’ємні дійсні числа , що задовольняють наступним умовам:

а) потік у дузі не повинен перевищувати її пропускну спроможність;

б) для кожної вершини мережі, крім витоку та стоку, справедлива властивість збереження потоку: сумарний потік, що заходить до вершини повинен дорівнювати сумарному потоку, що виходить з неї.

Дуга мережі називається насиченою, якщо потік у цій дузі дорівнює її пропускній спроможності.

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

Розріз мережі є множиною найменшої кількості дуг, що відділяють виток від стоку. Тобто, розріз транспортної мережі поділяє її на дві незв’язані частини, причому до першої частини входить виток, а до другої — стік. Сумарна пропускна спроможність цих дуг називається пропускною спроможністю розрізу.

Теорема (Форда-Фалкерсона). Для будь-якої транспортної мережі величина максимального потоку з витоку до стоку дорівнює мінімальній пропускній спроможності розрізу мережі, що відокремлює виток від стоку.