Материал: 62_201

води можна через неї пропустити? Саме на це запитання і дає відповідь метод, який розглядатиметься далі.

І ще дамо відповідь на таке запитання: чому потоки у мере­ жах розглядаються в теорії графів? Це пов'язано з тим, що

будь-яку мережу можна представити у вигляді зв'язного зва­ женого орієнтованого графа, де «вага» кожного ребра вказува­ тиме його пропускну спроможність, а орієнтація - напрям ру­ ху цим ребром.

Будь-якою мережею рухається потік. У мережі виділяються дві вершини: виток і стік. Вважається, що потік рухається ме­ режею, починаючи з вершини-витоку, проходячи ребрами че­ рез інші вершини, і надходить до вершини-стоку. Потік у ме­ режі визначається такими властивостями: величина потоку будь-яким ребром не перевищує його пропускної спромож­ ності; для будь-якої вершини, крім витоку і стоку, вхідний потік дорівнює вихідному. Вважається також, що для верши­ ни-витоку вхідний потік безмежний, а для вершини-стоку вихідний потік нікуди далі не розподіляється.

Задача про максимальний потік полягає у наступному: для даної мережі з витоком і стоком знайти потік максималь­ ного значення.

Які задачі можна віднести до потокових? Це не обов'язково може бути рух води трубами мережі. Замість води можна досліджувати рух інформації, що певним чином вимірюється і спрямована від одного пункту до іншого; грошових мас, що пе­ реміщуються від одного банку до іншого, враховуючи при цьо­ му потужність цих банків; рух транспорту з певним об'ємом си­ ровини поміж підприємствами, що її переробляють, враховую­ чи потужність цих підприємств і якість доріг, якими рухаєть­ ся транспорт. Різні, на перший погляд, задачі врешті-решт постають як графи, ребра яких мають певну «вагу» і напрям. Розв'язок цих задач можна одержати, визначивши максималь­ но можливу прохідність ребер заданих графів, враховуючи їх пропускну спроможність.

Алгоритм Форда-Фалкерсона побудови максимального потоку в мережі

Розглянута вище задача насправді є однією із класичних задач теорії графів і має алгоритм розв'язання. Він був запро­ понований різними авторами - Фордом та Фалкерсоном, однак базується на однаковій методиці розв'язання, яку можна визначити як «техніку міток».

Перш ніж розпочати її розгляд, звернемося до класичної постановки цієї задачі. Для кращого розуміння алгоритму

132

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

Отже, нехай задано зв'язний орієнтований зважений граф, в якому вершина s (витік) є початковою, а вершина t (стік) - кінцевою. При цьому кожному ребру мережі (графа) приписа­ на деяка пропускна спроможність С[і, j], що визначає макси­ мальне значення потоку, який може протікати заданим ребром (мал. 78).

>

Мал. 78

Висловлюючись «мовою водогону», під пропускною спро­ можністю ребра розумітимемо діаметр труби.

Для подальшого пояснення введемо поняття розрізу в ме­ режі. Підійдемо до цього поняття такою послідовністю мірку­ вань. Об'єднаємо дві мережі з малюнка 77 в одну таким чином, як зображено на малюнку 79, використавши для цього мову графів.

Якщо окремо кожною мережею, зображеною на малюнку 77, можна було прогнати по 10 л води, то, об'єднавши їх таким чи­ ном, як зображено на малюнку 79, 20 л! Цей висновок є інтуїтивно очевидним. Зважаючи на те, що у верхній частині мережі й у нижній є ребра з пропускною спроможністю 20 л, то слушним буде запитання: а які ребра гальмують проходження води заданою системою? Відповідь така: у верхній частині та­ ким ребром є центральне (1,2) з пропускною спроможністю 10 л, а в нижній - два крайніх (s,3), (4,£) також по 10 л.

Модифікуємо мережу, зображену на малюнку 79, а, так, як зображено на малюнку 79, б. Пропускна спроможність мережі

133

при цьому не зміниться, оскільки у верхній та нижній части­ нах залишилися «гальмуючі» ребра «вагою» 10. При цьому у верхній частині мережі у трубі біля витоку залишається 10 л невикористаної води, а у нижній частині мережі в останній трубі перед стоком труба наполовину порожня. Шкода, по­ тужність деяких труб знову не повністю реалізована. Чи мож­ на щось зробити? Висновок напрошується сам по собі: додати ще одне ребро, з'єднавши вершини 1 і 4. Для цього достатньо труби з пропускною спроможністю 10 л (мал. 80). Тепер у вер­ шині 1 вода буде перерозподілятися: половина піде трубою у вершину 2, а інша половина донаситить трубу, що виходить

звершини 4, злившись з 10 л води, що прийшли з вершини 3. Тепер до стоку мережі t буде надходити вже ЗО л води: 10 л

зверхньої частини і 20 л з нижньої.

ж \ ^У

1 0 -

Мал. 80

•

Проаналізуємо мережі, зображені на малюнках 79, б і 80 та визначимо, як можна отримати максимально можливу про­ пускну спроможність усієї мережі.

Мережа на малюнку 79, б складається з двох гілок, і мінімальними ребрами у кожній з них є ребра (1,2) і (3,4) (або (s,3)) «вагою» 10. їхня сума і визначає максимально можливу спроможність цієї мережі 20. А що являють собою ці ребра? Вони мають такі дві властивості: по-перше, сума їхніх «ваг» визначає максимальну спроможність, по-друге, якщо ми їх приберемо з мережі, то жодна краплина води не зможе потрапити з витоку s до стоку t.

На малюнку 80 до цієї мережі додано ще ребро (1,4) «ва­ гою» 10. Це дало змогу перегнати додаткові 10 л води з верши­ ни 1 у вершину 4 і збільшити пропускну спроможність мережі. У цій мережі вона становить ЗО. Якщо у мережі, зображеній на малюнку 80, вилучити ті самі два ребра, що й у мережі, зобра­ женій на малюнку 79, б, то вода все одно поступатиме з вито­ ку s до стоку t через ребро (1,4) і дасть змогу пропустити 10 л води. Для того щоб припинити подачу води, необхідно прибра­ ти ще й ребро (1,4) «вагою» 10. Сума «ваг» вилучених ребер із мережі, представленій на малюнку 80, становить ЗО, що збігається з її максимальною пропускною спроможністю. Слід

134

зауважити, що ребра (s,l) і (s,3) мають таку саму властивість. Однак вилучення не лише цих ребер припинить подачу води з витоку до стоку. Таких ребер є більше, наприклад (2,t) і (4,і). Але сума їх «ваг» становить 40, що більше максимальної про­ пускної спроможності нашої мережі.

Отже, зробимо висновок: максимальна пропускна спро­ можність мережі дорівнює мінімальній сумі пропускних спро­ можностей ребер, вилучення яких з мережі призводить до роз­ риву всіх шляхів, що ведуть з s до t. При цьому граф, що опи­ сує мережу, стає незв'язним.

Будь-яка множина ребер, вилучення яких призводить до втрати зв'язності мережі, називається розрізом. Зрозуміло, що пропускна спроможність будь-якого розрізу дорівнює сумі пропускних спроможностей ребер, що його утворюють. Розріз з

мінімальною пропускною спроможністю називають мінімаль­ ним розрізом мережі.

Визначимо максимальну пропускну спроможність мережі, зображеної на малюнку 78. Сукупність яких ребер є критич­ ною щодо зв'язності заданого графа? На перший погляд таки­ ми є ребра (2,і) і (4,t). Цей розріз мережі дорівнює 22. Однак при детальному аналізі знайдеться ще один розріз, значення якого є меншим. Це сукупність ребер (s,l) і (3,4). Вилучення цих ребер із мережі не дасть змоги подати жодної краплі води до стоку системи. Такий розріз є мінімальним зі значенням 20, що і визначає остаточне значення максимального потоку в за­ даній мережі. Наведений приклад є цікавим тому, що мінімаль­ ний розріз утворюють ребра, які не мають спільних вершин, як у мережі, зображеній на малюнку 80, або ж візуально легко визначаються, як у мережах, зображених на малюнку 79.

Тепер перейдемо до алгоритму Форда-Фалкерсона. Він ба­ зується на твердженні, що можна сформувати різні варіанти потоків з s до t, однак усі вони не будуть перевищувати про­ пускної спроможності мінімального розрізу. Причому знай­ деться хоча б один, який дорівнюватиме йому, і саме він буде максимальним, а тому найкращим.

З малюнка 80 видно, що потоками з s до t можуть бути такі:

-(s,l,2,t) з пропускною спроможністю 10;

-(s,3,4,/) з пропускною спроможністю 10;

-(s,l,2,f), (s,3,4,f) з пропускною спроможністю 20;

-(s,3,4,f), (s,l,4,t) з пропускною спроможністю 20;

-(s,l,2,t), (s,3,4,i), (s,l,4,f)3 пропускною спроможністю ЗО. Як бачимо, дійсно, пропускні спроможності всіх потоків ме­

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

135

Яким же може бути алгоритм визначення максимального потоку в мережі?

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

Для реалізації наведеного алгоритму можна використати алгоритм повної вибірки, який розглядався у розділі «Елемен­ ти комбінаторики в алгоритмічних задачах» і алгоритм пошу­ ку в ширину для визначення зв'язності графа.

Не будемо детально зупинятися на цьому алгоритмі з двох причин: по-перше, він не є оптимальним з точки зору часу його виконання і може бути застосований лише для невеликих ме­ реж; по-друге, він дає лише часткову відповідь на поставлену задачу, а саме визначає тільки значення максимального пото­ ку. У разі, якщо необхідно визначити, якою буде оптимальна насиченість кожного ребра мережі під час проходження води від витоку до стоку, описаний алгоритм не допоможе.

Для повного розв'язання задачі про максимальний потік пе­ рейдемо до метода Форда-Фалкерсона, що використовує запро­ поновану «техніку міток». Цей метод є ітераційним. Пояснимо новий термін.

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

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

Перейдемо до розгляду алгоритму побудови максимального потоку в мережі, і метод ітерацій стане зрозумілим.

Порушимо цього разу послідовність викладення матеріалу: спочатку розглянемо ідею самого алгоритму на конкретному прикладі, а потім сформулюємо сам алгоритм.

Нехай задана мережа у вигляді орієнтованого зваженого графа (мал. 81, а), де виток позначимо вершиною з номером 1

136