Проблема максимального потоку стосується пошуку можливого потоку в мережі (тобто, потік, який задовольняє верхні та нижні межі для всіх дуг, а також необхідні баланси у вузлах) таким чином, щоб максимізувати загальну кількість потоку, що надходить або циркулює в мережі.
У теорії графів потокова мережа визначається як орієнтований граф, що включає джерело ( ), поглинач ( ), а також кілька інших вузлів, з’єднаних ребрами. Кожен край має індивідуальну пропускну здатність, яка є максимальною межею потоку, яку може дозволити край.
Максимальний потік визначається за допомогою таких алгоритмів, як Форда-Фулкерсона або Едмондса-Карпа, надсилаючи все більше і більше потоку через ребра в мережі потоку, доки пропускна здатність ребер не стане такою, що більше потік не зможе пройти через. Такий шлях, через який може пройти більший потік, називається розширеним шляхом.
Приклад максимального потоку. Потік – це призначення невід’ємного числа кожній дузі (кількість потоку), яке задовольняє таке правило збереження потоку: Примітка: У кожному вузлі, крім джерела або стоку, загальний потік усіх дуг, що ведуть до вузла, дорівнює загальному потоку всіх дуг, що ведуть з нього.
Щоб знайти максимальний потік через потокову мережу, ми:
- Намалюйте кілька розрізів, позначивши краї, які перетинаються від сторони джерела до сторони раковини.
- Складіть пропускну здатність позначених країв, роблячи нотатку про найменшу загальну кількість.
- Перевірте інші розрізи, щоб побачити, чи можемо ми отримати меншу вартість.
Це важливо спостерігати модель максимального потоку дійсно є окремим випадком моделі потоку мінімальних витрат: фактично, якщо розглядати змінну val як значення потоку по дузі (t,s), то обмеження є стандартними для задач потоку (з нульовим балансом на всіх вузлах); цільова функція, яку необхідно мінімізувати…