Потік в мережі
Функція, що зіставляє дуг даної мережі (орієнтованого графа) нек-риє числа. Кожне число інтерпретується як інтенсивність потоку деякого вантажу по даній дузі. П. в с. є зручною моделлю при дослідженні ряду проблем в транснорте, зв'язку та ін. областях, пов'язаних з рухом вантажів, інформації і т. д. Багато задач про потоках є завданнями лінійного програмування і можуть вирішуватися загальними методами цієї теорії. Однак в більшості випадків завдання про потоках допускають ефективне рішення методами теорії графів. Нехай кожній дузі (х, у) .сеті N приписано невід'ємне дійсне число з (х, у) - пропускна здатність дуги (х, у). Кажуть, що потік f (x, у) .є стаціонарним потоком величини vіз вершини rв вершину s, що задовольняє обмеженням пропускних спроможностей дуг, якщо для будь-якої дуги (х, у), тут -поток, що виходить з, вершини x, а - потік , що входить в вершину х. У задачі про максимальний потік між двома вершинами потрібно побудувати стаціонарний потік з вершини rв вершину s, має максимально можливу величину v. Для вирішення цього завдання існують досить ефективні алгоритми. Нехай X - підмножина вершин мережі N таке, що. Тоді безліч дуг (х, у) .Так, що. наз. розрізом. Пропускною спроможністю розрізу зв. величина. Справедлива наступна теорема про максимальний потік і мінімальному розрізі: максимальна величина потоку дорівнює мінімальній пропускній здатності розрізів. У додатках часто використовується теорема про целочисленности: якщо пропускна здатність дуг целочисленном, то існує цілочисельний максимальний (стаціонарний) потік. До задачі про максимальний потік між двома вершинами зводиться ряд завдань: завдання про максимальному П. в с. з декількома джерелами і стоками; задача про максимальний П. в с. має невід'ємні обмеження на потоки по дугам як зверху, так і знизу; задача про максимальний потік в неорієнтованих і змішаних мережах; задача про максимальний потік в мережі з пропускними здатностями дуг і вершин і ін. Теорема про максимальний потік і мінімальному розрізі виявила загальну основу ряду результатів, отриманих раніше в теорії графів і комбінаторики. Виявилося, що як наслідки цієї теореми можуть бути отримані: теорема про максимальне паросполучення в графі дводольному, теорема про різні представників, теореми про k-зв'язності графів (див. Графа зв'язність), теорема про покриття частково впорядкованої множини найменшим числом ланцюгів і ін. Зведення різних завдань до задачі про максимальний потік є важливим методом теорії графів і комбінаторики. У ряді завдань про П. в с. кожній дузі (х, у) .сопоставляется число а (х, у) - вартість перевезення одиниці вантажу по дузі (х, у) .і потрібно знайти потік, що задовольняє певним обмеженням і мінімізує загальну вартість потоку. Завдання про потік мінімальної вартості полягає в знаходженні стаціонарного потоку з вершини rв вершину s, що задовольняє обмеженням пропускних спроможностей дуг, причому такого, що величина його дорівнює заданому числу v, а вартість мінімальна. У транспортній задачі мережу є дводольним графом. Вершини однієї частки Sl. Sm інтерпретуються як пункти відправлення деякого вантажу, вершини іншої T1. Т n - як пункти призначення. Кожен пункт відправлення Si має певну пропозицію bi, і кожен пункт призначення Tj має певний попит cj. Відома вартість а ij перевезення одиниці вантажу з Si в Т j. Завдання полягає в знаходженні потоку мінімальної вартості, що задовольняє попит у всіх пунктах призначення. Розглядаються також багатопродуктової потоки і потоки, що змінюються в часі. Літ.: [1] Форд Л. - Р. Фалкерсона Д. - Р. Потоки в мережах, пров. з англ. М. 1966. В. Б. Алексєєв.
Джерело: Математична енциклопедія на Gufo.me