Транспортні мережі. Алгоритми визначення найбільшого потоку

Транспортної мережею називається кінцевий Зв'язний орграф 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. Розріз з мінімальною пропускною спроможністю. Обчислювальна та ємнісна складність алгоритму.