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

Нехай заданий граф G={N, A}. Розіб'ємо множину N на дві підмножини, які не пересікаються , так щоб джерело та стік графа не знаходились в одній підмножині. Всі дуги, що з'єднують ці дві підмножини, утворюють множину .

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

Кількість дуг в перетині називається рангом перетину, а сумарна пропускна спроможність всіх дуг перетину - розрізом.

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

Дана теорема корисна для аналізу “вузьких місць” у мережі. Тобто, якщо збільшити пропускну здатність будь-якої дуги з мінімального перетину, то можна збільшити загальний потік в мережі.

Рисунок 4.1 – Граф мережі з обмеженими пропускними здатностями

1 ітерація. Шлях: 1-3-5

Позначки:

Потоки в дугах:

Загальний потік збільшився на =2

2 ітерація. Шлях: 1-2-3-4-5

Позначки:

Потоки в дугах:

Загальний потік збільшився на =1

3 ітерація. Шлях: 1-2-5

Позначки:

Потоки в дугах:

Загальний потік збільшився на

4 ітерація. Шлях: 1-3-2-5

Позначки:

Потоки в дугах:

Загальний потік збільшився на

5 ітерація. Шлях: 1-4-5

Позначки:

Потоки в гілках:

Загальний потік збільшився на

6 ітерація. Ще будь-який шлях вибрати неможливо.

Максимальний потік в мережі дорівнює сумі збільшень потоків на кожній ітерації, тобто V=6. В даному прикладі можна визначити максимальний потік, використовуючи теорему про максимальний потік та мінімальний розріз, яким є розріз .