Транспортні мережі. Алгоритми визначення найбільшого потоку
Транспортної мережеюназивається кінцевий Зв'язний орграф G (V, E) без петель, кожній дузі якого поставлено у відповідність деяке невід'ємне число c (), зване пропускною здатністюдуги, і існує:
1) рівно одна вершина, у якому не заходить жодна дуга, звана джереломабо початком мережі;
2) рівно... одна вершина, з якої не виходить жодної дуги; ця вершина називається стокомабо кінцем мережі.
Потоком мережіназивається неотрицательная функція f (1) така, що f (e) менше або дорівнює c (e). (Потік не може перевищувати пропускну здатність дуги.)
Дуга називається насиченоюпотоком f, якщо (Потік називається повним, якщо містить насичену дугу f (e) = c (e).)
Розрізом Lмережі G (V, E) називається безліч насичених дуг, що відокремлюють джерело s від стоку t.
Задача про максимальний потік на мережі.
Нехай задана транспортна мережа, що складається з безлічі вузлів J з номерами 
і безлічі дуг D, що з'єднують деякі з цих вузлів між собою.
Передбачається, що мережа є симетричним графом, тобто якщо дуга (i, j) входить в мережу, то в неї входить і симетрична дуга (j, i), хоча реально такий дуги може і не бути. Кожній дузі 
поставлено у відповідність число d ij, зване пропускною здатністю дуги. Величина d ij визначає максимальну кількість продукції, яке може бути переведене по дузі (i, j) в одиницю часу. Вузол з номером Ø має необмежений запас продукції і називається джерелом, а вузол з номером n має необмежену потребу в еой продукції і називається стоком. В інших вузлах, які називаються проміжними, запас продукції або потребу в ній дорівнюють нулю.
Необхідно знайти максимальну кількість продукції, що перевозиться з вузла з номером 
в вузол з номером n в одиницю часу, при цьому не порушуючи пропускні спроможності дуг мережі.
Алгоритм рішення задачі про максимальний потік заснований на теоремі Форда - Фалкерсона про максимальний потік і мінімальний розрізі. Для розгляду цієї теореми вводяться понятіяо прямого і зворотного дуги ланцюга. Під ланцюгом в даному випадку розуміється послідовність зчеплених дуг мережі без урахування їх оріетаціі. Дугу, прінажлежащую деякі ланцюга, називають прямою, якщо її напрямок співпадає з напрямком обходу вузлів цієї мети, і зворотного - в іншому випадку наприклад, ланцюг μ = (3,5,4,7,6,8) на рис.1, зв'язує вузол 3 з вершиною 8, містить три прямі дуги (3,5), (4,7), (6,8) і дві зворотні (4,5), (6,7).
Теорема. В будь-якій мережі максимальна величина потоку з джерела в стік дорівнює пропускній здатності мінімального розрізу мережі.
Алгоритм Форда знаходження максимального потоку на мережі.
Вихідні дані заносяться в таблицю розмірності (n +1) × (n +1). Якщо дуга 
, То у відповідній клітині таблиці записується значення d ij.
Якщо зворотна дуга 
, То у відповідній клітині записується значення d ji, якщо дуга 
, То в клітці (j, i) записується Ø.
Якщо дуги 
, 
, То відповідні клітини залишаються порожніми. Отже, заповненими будуть тільки клітини, симетричні відносно головної діагоналі.
Кожен крок алгоритму Форда складається з трьох дій.
1.Находітся шлях по таблиці з вузла-джерела Ø у вузол-стік n з пропускною спроможністю більше 0. Для цього стовпець, відповідний вузлу-витоку, відзначається знаком *. Далі відшукуються в рядку з номером 0 елементи d ij> 0 і стовпці, в яких вони знаходяться, відзначаються зверху номером переглядається рядки (цифрою 0). В результаті виявляться виділеними всі дуги (0, j) c позитивними пропускними здатностями. Ці дуги можуть служити першими дугами шляху з витоку в стік.
Далі проглядаються ті рядки, номери яких співпадають з номерами зазначених стовпців. У кожній такій рядку i відшукуються елементи d ij> 0, що знаходяться в непозначених стовпцях, і ці стовпці відзначаються номером переглядається рядки. Таким чином, виявляться виділеними дуги, які можуть служити другими дугами шляхів з витоку в стік.
Аналогічний перегляд рядків продовжується до тих пір, поки: а) або не буде позначений стовпець з номером n (сток) що означає виділення шляху з пропускною спроможністю більше нуля з витоку в стік, б) або не можна позначати нові стовпці (у переглядаються рядках не виявиться позитивних елементів), при цьому стовпець з номером n також залишиться не відміченим.
В останньому випадку відсутня шлях з джерела в стік, що проходить по дугам з позитивною пропускною здатністю.
У разі "а" шуканий шлях μ з джерела в стік знаходиться використовуючи позначки стовпців. Нехай останній стовпець n позначений номером k, тоді дуга (k, n) остання ланка шуканого шляху. Далі проглядається стовпець з номером k, нехай відмітка цього стовпця l. Тоді дуга (l, k) передостаннє ланка шуканого шляху і т.д.Етот процес продовжується до тих пір, поки не знайдеться відмітка *, тобто відмітка витоку Ø. Нехай ця позначка буде цифра m. Таким чином шлях від витоку до стоку буде складатися з дуг μ = ((Ø, m),..., (l, k), (k, n)). (5)
2.Клеткі, відповідні дугам цього шляху, відзначаються знаком (-), а симетричні їм клітини, тобто відповідні зворотним дугам - знаком (+). По знайденому шляху (5) можна пропустити максимально можливий потік, величина якого дорівнює Θ = min { d ij -}. Ця величина Θ віднімається від всіх пропускних спроможностей клітин, відмічених знаком (-) та додається до пропускним здібностям клітин, відмічених знаком (+). У результаті виходить нова таблиця, в якій записані невикористані пропускні спроможності дуг після пропускання максимального потоку по шляху (5).
За новою таблицею знову відшукується, вже інший, шлях від витоку до стоку, що складається з дуг з невикористаними пропускними здатностями. Якщо такий шлях існує, то по цьому шляху пропускається максимально можливий потік з витоку в стік. Після цього коригується таблиця аналогічно як на етапі 1.
Це процес продовжується до тих пір, поки не буде мати місце випадок б).
3.Пусть є випадок б), тобто коли не існує шляху з витоку в стік, що складається з дуг з невикористаними пропускними здатностями. Це означає, що знайдені всі можливі шляхи перевезення продукції і завдання вирішене. Для визначення максимального потоку на мережі V * в останній таблиці виділяються зазначені стовпці, номери яких утворюють безліч R *, причому витік 
*. У результаті виходить мінімальний розріз (R *, 
*) І по теоремі Форда-Фалкерсона
Для знаходження значень потоків по дугах x ij *, утворюючих потік V * з елементів першої таблиці віднімаються відповідні елементи останньої таблиці. Якщо в клітці виходить ненегативна величина, то вона полишиться якщо - негативна, то в клітці записується 
. Значення заповнених клітин будуть відповідати потокам по дугам x ij *. Причому
21. Розріз з мінімальною пропускною спроможністю. Обчислювальна та ємнісна складність алгоритму.