Материал: 62_201

(s = 1), а стік - вершиною з номером 6 (t = 6). Мережа задається таблицею пропускних спроможностей кожного ребра С[і, j], де (і,;') - орієнтоване ребро, початок якого знаходиться у вершині і, а кінець - у вершині j (мал. 81, б).

Мал. 81

Уважно придивившись до заданої мережі, можна помітити, що вона відрізняється від мережі, зображеної на малюнку 78, лише тим, що ребро (2,3) замінене на ребро (3,2). Пізніше, коли розглядатимемо алгоритм відшукання максимального потоку, ці зміни дадуть можливість дослідити всі особливості алгоритму Форда-Фалкерсона. Але для контролю коректності отриманого результату доведеться визначити значення максимального пото­ ку вже зараз. Для нашого прикладу він становить 22, оскільки визначається мінімальним розрізом, що утворюється ребрами (5,6) і (4,6). Нагадаємо, що для мережі, зображеній на малюн­ ку 78, вона становила 20. Отже, лише зміна напряму одного реб­ ра призвела до зміни значення максимального потоку в ній.

Для одержання максимального потоку в заданій мережі ми покроково насичуватимемо її водою, поки не дійдемо до макси­ мально можливого. У зв'язку з цим необхідно ще мати інфор­ мацію про поточну насиченість кожного ребра. Вона містити­ меться у таблиці F[i, j], значення елементів якої на початковому етапі дорівнюватиме 0. Поточне значення заповнення кожного ребра F[i, j] перед дужками з відповідним початковим заданим значенням С[і, j] (мал. 82).

^@-0(20)-<5Х

Мал. 82

І ще одна інформація буде потрібна під час виконання алго­ ритму: для кожної вершини визначатимемо, з якої вершини і скільки води можна подати до неї на поточному кроці. Ця мітка

137

вказуватиметься лише для вершин, що розглядатимуться на по­ точному кроці виконання алгоритму, тобто на даній ітерації.

Щодо самих вершин введемо для них вже традиційний ста­ тус: «відвідана», «побачена», «нова». Це дасть нам змогу конт­ ролювати перегляд і відвідування вершин під час кожної іте­ рації. Така термінологія наводить на думку, що для визначення послідовності ребер мережі, якими буде проходити потік, вико­ ристовуватиметься алгоритм пошуку в ширину. І це справді так.

Щодо кожного ребра, то нас буде цікавити питання стану йо­ го насиченості: чи воно вже максимально насичене, або ж має можливість донасичуватися, тобто у нього є певний резерв по­ току. Цю характеристику можна отримати порівнянням двох параметрів - заданою С[і, /] і поточною F[i, j\ пропускною спро­ можністю кожного ребра.

Наприкінці зазначимо ще один момент, який враховувати­ меться під час виконання алгоритму побудови максимального потоку. Коли у деяку вершину і приходить потік, то він не обов'язково продовжує переміщатися лише одним з ребер, що виходить із цієї вершини. Його можна перерозподіляти різни­ ми ребрами, що виходять з неї. На перший погляд це очевидно, але при виконанні алгоритму така особливість не повинна бути втраченою, тобто можливий перегляд перерозподілу наявної кількості води, що виходить з поточної вершини різними реб­ рами. Це можна буде побачити на одному з кроків виконання алгоритму, що і є його характерною особливістю.

Насичення потоку в мережі здійснюватимемо поетапно, за допомогою ітерацій. Скільки ітерацій (кроків) нам знадобиться для розв'язання задачі, стане зрозумілим, коли завершиться процес насичення і більше ніяких змін неможливо буде зроби­ ти. Отже, визначаємо ітерації.

Перша ітерація

Позначимо вершину 1 міткою [0, °°]. Це означає, що пропуск­ на спроможність цієї вершини не обмежена і вода поступає у цю вершину «нізвідки» (мал. 83, а). Визначимо вершину 1 як відвідану, позначимо її на малюнку темним кольором і занесе­ мо у послідовність як ту, з якої будемо дивитись далі на інші вершини. Далі будемо дивитись з вершини 1, позначивши її для цього стрілочкою.

Які ребра виходять з вершини 1? Це ребра (1,2) та (1,3). Вер­ шини 2 і 3 нові, але їх вже можна побачити, і, окрім цього, відо­ мо, який потік можна до них пропустити: до вершини 2 ребро (1,2) дає змогу пропустити 15 одиниць води, а до вершини З ребро (1,3) - ЗО одиниць. Позначимо їх відповідно мітками [1,15] та [1,30], де перше число - номер вершини, з якої іде

138

потік, друге - числове значення потоку, який можна передати цим ребром (мал. 83, б). До послідовності перегляду вершин до­ пишемо вершини 2 і 3, вказавши індексами номери вершин - предків, з яких вони «побачені», та на малюнку виділимо світ­ ло-сірим кольором. Нагадаємо, що поки дивимося на інші вер­ шини мережі з вершини 1.

[1,15]

Д У 0 ( 2 0 ) - ( 5 ^ (if)-0(20) */ІГ)г

ь

0(3)

0(5)-^(4j

Мал. 83 Оскільки з вершини 1 інших вершин не видно, то можна пе­

реходити у наступну видиму вершину для того, щоб продовжи­ ти огляд далі. Такою вершиною у послідовності, що нами бу­ дується, є вершина 2. З неї «видно» вершини 4 і 5. Обидві ці вершини є новими, тому дописуємо їх до послідовності і помі­ чаємо як «видимі», а вершину 2 - як «відвідану» (мал. 84, а). Перефарбуємо вершину 2 у темно-сірий колір, а вершини 5 і 4 - у світло-сірий. Який об'єм води можна отримати у кожній з вершин 4 і 5, враховуючи те, що попадає вона туди з верши­ ни 2? У вершині 2 накопичиться води 15 одиниць, а це означає, що якщо ми підемо шляхом на вершину 5, то вся вона пройде, ще й залишиться резерв 5 одиниць. Тому біля вершини 5 поста­ вимо мітку [2,15]. А от якщо будемо рухатися у напрямі верши­ ни 4, то більше ніж 10 одиниць води пропустити не зможемо. Тому і мітка у вершині 4 буде такою: [2,10] (мал. 84, а).

Вибираємо наступну в черзі, якою фактично є послідовність, вершину 3. З неї видно вершини 2 і 4. Але обидві ці вершини

139

відмічено як «видимі», тому дописувати їх у послідовність немає сенсу. Саме тому малюнок 84, б не містить інших відмінностей, окрім того, що огляд нових невидимих вершин проводимо з вершини 3.

Переходимо до вершини 4, позначивши її темним кольором (мал. 85, а). З неї можна потрапити лише у вершину 6. Ця вер­ шина «невидима», тому дописуємо її до послідовності і надаємо статус «видимої». Окрім цього, потрапивши у неї з вершини 4, можна передати ребром (4,6) 10 одиниць води, а саме стільки у цій вершині і було! Мітку [4,10], що засвідчує цей факт, по­ ставимо біля вершини 6. Процес проходження мережею від ви­ току до стоку завершено, і при цьому до вершини 6 надійшло 10 одиниць води.

Підіб'ємо підсумок першої ітерації: 1) знайдено перший варіант проходження мережі шляхом (1,2), (2,4), (4,6); 2) зна­ чення потоку знайденим шляхом дорівнює 10 одиницям.

Позначимо отриманий результат на малюнку 85, б виділени­ ми ребрами. Біля ребер, що утворюють прохідний шлях, який носить назву доповнюючого шляху, від витоку 1 до стоку 6 у цій ітерації, проставимо мітки, котрі визначають кількість води, яку можна пропустити кожним ребром, і у дужках відповідну пропускну спроможність. Біля вершини-стоку 6 вказано поточ­ не значення максимального потоку в мережі на даній ітерації.

Мал. 85

Друга ітерація

Перша ітерація завершилася результативно: знайшовся до­ повнюючий шлях від витоку 1 до стоку 6, яким було передано мережею 10 одиниць води. Варто спробувати збільшити потік.

Для цього почнемо процес прогону води з початку, врахову­ ючи результати попереднього кроку.

Отже, ставимо мітку [0, °°] у вершині 1 (мал. 86, а). Чи мож­ на з неї «побачити» вершини 2 і 3? Так, до верпіини 2 можна подати ще 5 одиниць води, а ребро (1,3) взагалі ще порожнє. Та-

140

ким чином вершина 2 отримує мітку [1,5], а вершина 3 - [1,30] (мал. 86, б).

Перейдемо у наступну «видиму» вершину 2 і подивимось з неї на решту вершин мережі. На попередній ітерації з неї мож­ на було перейти до вершин 4 і 5, а тепер вершина 4 нам недо­ ступна, оскільки ребро (2,4) максимально наповнене і значення його пропускної спроможності збігається зі значенням його наповнюваності. Таким чином, до послідовності переглянутих і видимих вершин можна дописати лише вершину 5, позначив­ ши її міткою [2,5] (мал. 87, а). Чому не 20, адже пропускна спроможність ребра (2,5) має саме таку потужність? Однак у вершину 2 прийде лише 5 одиниць води, тому і у вершині 5 більше води не з'явиться.

Наступним кроком у цій ітерації буде перехід до вершини 3. З неї можна «побачити» вершину 4, яку у цій ітерації ще не бу­ ло «видно». Зафарбуємо цю вершину як «видиму» і позначимо міткою [3,5] (мал. 87, б). Тепер є зрозумілим визначення пото­ ку величиною 5 у вершині 3. Це спричинене тим, що хоча у вер­ шину 3 приходить ЗО одиниць води, однак ребро (3,4) може пропустити з них лише 5.

Переходячи у вершину 5, дописуємо до послідовності нову «видиму» з неї вершину 6 і позначаємо її міткою [5,5] (мал. 88, а).

141