5.3.1. Постановка завдання визначення максимального потоку в мережі зв'язку
Нехай проектується мережа зв'язку. При проектуванні задано безліч джерел інформації S і безліч одержувачів інформації Т. Зазвичай ці безлічі пересічні або можуть бути тотожними S = Т. тобто вузол джерело може бути і вузлом одержувачем. Кожен вузол безлічі S породжує потік інформації, яка повинна бути передана вузлів безлічі Т. Гілки графа можуть мати задану пропускну здатність з (u, v), між кожною парою вузлів u і v. або може знадобитися визначити пропускну здатність кожної гілки. Пропускна спроможність галузі (ребра) може розглядатися як максимальна швидкість передачі інформації вздовж даної галузі.
Задана, топологія мережі, тобто встановлено відповідність вузлів і гілок, задана матриця ваг гілок A [u, v], де в якості ваг виступає пропускна здатність кожної гілки.
Які завдання вже можна вирішити при цих вихідних даних? Очевидно, можна виділити безліч пов'язаних вузлів. Можна знайти найкоротші шляхи між усіма парами вершин. Можна знайти, нарешті, всі шляхи між вершинами s і t. При цьому кожен шлях повинен відрізнятися від іншого, хоча б однією гілкою або вузлом. Однак, рішення жодної верб цих завдань не дозволить нам отримати відповідь на питання - яку максимальну кількість інформації в одиницю часу можна передати від вузла s до вузла t. або від групи вузлів безлічі S до групи вузлів безлічі. Т. Вирішені вищевикладені завдання не допоможуть також вирішити і зворотну задачу - скільки і з якими пропускними здатностями потрібно гілок, щоб пропустити все інформаційні потоки між безліччю вузлів S і безліччю вузлів Т. Таке завдання, до речі для реальних мереж і не вирішена (не дозволяє розмірність завдання і невизначеність вихідних даних).
Для постановки задачі формалізуємо деякі поняття. Припишемо кожної гілки (u, v) деяку вагу f (u, v), званий потоком від u до v. Значення потоку в галузі (u, v) можна розглядати як швидкість, з якою передається інформація в даній галузі.
Тоді величина, звана дивергенцией потоку f в вершині v
де Σf (v, u) - потік, що виходить з вершини v. Σf (u, v) - потік, що входить в вершину v, визначає кількість потоку, що виходить з вершини u.
Ця величина може бути негативною (коли в v більше входить, чому вийшов), позитивною (коли з v більше виходить, ніж входить) і рівною 0. Останній випадок буде цікавити нас найбільше. Це означає, що потік не накопичується і не виникає ні в одній з вершин, крім s і t.
Під потоком з s в t будемо розуміти функцію, для якої виконуються умови
Який потік, може бути переданий від s до t через ці гілки? Очевидно, з огляду на, що гілки орієнтовані
тобто він буде дорівнює сумі пропускних спроможностей гілок, що входять в розріз.
Під розрізом мережі R (A) відповідним АV (А підмножина V), А ≠ V. А ≠ 0. будемо розуміти безліч дуг, (u, v) таких що (u, v) W. UА і vV \ А.
Для довільного потоку f в мережі потік через розріз визначиться очевидним чином
тоді, якщо уявити, що sA. a tV \ A. то потік з s в t визначиться як
Введемо поняття мінімального розрізу. Під мінімальним разре-зом, що розділяє s і t. ми будемо розуміти довільний розріз R (A), SА і tV \ A з мінімальною пропускною спроможністю.
Приклад. Сформулюємо класичну теорему теорії потоків в мережах. Ця теорема про максимальний потік і мінімальному розрізі:
Величина кожного потоку з s в t. не перевищує пропускної здатності мінімального розрізу, причому існує потік, що досягає цього значення.
Максимальний потік в мережі
Всі відомі алгоритми побудови максимального потоку грунтуються на послідовному збільшенні потоку, причому модифікація потоку, що збільшує його величину, найчастіше спирається на метод збільшують ланцюгів (або шляхів нарощування).
Введемо ряд понять, які знадобляться нам при подальшому викладі матеріалу.
Будемо говорити, що дуга m мережі G є допустимою дугою з u в v щодо потоку f. якщо