ни, сток при цьому залишиться поміченим. Якщо стік виявиться не позначеним, то процес знаходження максимального потоку в мережі можна вважати закінченим, а якщо сток позначений, то потрібно переходити до
процедурі 2.
Розглянемо процедуру зміни потоку. Якщо вершина має позначку, то замінюємо на, якщо ж вершина має позначку, то замінюємо на
Переходимо до наступної вершині і так до тих пір, поки не досягнемо джерела S. Тут зміна потоку припиняється. Далі переходимо до процедури 1 і так до тих пір, поки величину потоку вже не можна змінити.
Розглянемо конкретну задачу про знаходження максимального потоку в мережі.
Дана мережа G (V, E) (рис. 11) з джерелом S і стоком t. Пропускні здатності дуг вказані. Знайти максимальний потік з S в t. br/>
Потік в транспортної мережі.
Функція, визначена на множині X дуг транспортної мережі D і приймаюча цілочисельні значення, називається допустимим потоком (або просто потоком) у транспортної мережі D, якщо:
• для будь дуги величина, звана потоком по дузі, задовольняє умові;
• для будь проміжної вершини v виконується рівність
В
тобто сума потоків по дуг, що заходить в v, дорівнює сумі потоків по дугах, що походить із v.
В
Приклад. На малюнку показаний допустимий потік в транспортній мережі. При кожній дузі вказана величина потоку по ній. Очевидно, що виконуються всі умови, перераховані в визначенні допустимого потоку (перевіряємо виконання другої умови для проміжних вершин). p> Для будь-якого допустимого потоку в транспортної мережі D виконується рівність:
В
За визначенням допустимого потоку маємо:
В
Зауважимо, що для кожної дуги деВ , Величина входить в ліву частину рівності лише один раз і при цьому зі знаком плюс. Аналогічно для кожної дуги, величина входить в ліву частину рівності (2) лише один раз і при цьому зі знаком мінус. З іншого боку, для кожної дуги величинаВ входить в ліву частина рівності (2) один раз зі знаком плюс (при) і один раз зі знаком мінус (при), що в сумі дає нульовий внесок в ліву частину рівності (2). Враховуючи сказане, укладаємо, що з рівності (2) випливає справедливість рівності (1).
Величиною потоку в транспортній мережі D називається величина, що дорівнює сумі потоків по всім дугам, що заходить в, або, що те ж саме - величина, що дорівнює сумі потоків по всіх дугах, що походить з
В В
Нехай - допустимий потік в транспортної мережі D. Дуга називається насиченою, якщо потік по ній дорівнює її пропускної здатності, тобто якщо. Потік називається повним, якщо будь-який шлях в D з містить, принаймні, одну насичену дугу.
Потік називається максимальним, якщо його величина приймає максимальне значення в порівнянні з іншими допустимими потоками в транспортної мережі D.
Очевидн...
