Материал: 62_201

Залишається тільки підбити підсумок виконання дій протягом цієї ітерації:

-знайдено додатковий варіант проходження мережі, тобто ще один доповнюючий шлях (1,2), (2,5), (5,6);

-при цьому значення максимального потоку збільшене на 5 одиниць (мал. 88, б).

Мал. 88

Можна констатувати факт, що на завершення роботи другої ітерації до вершини-стоку потрапило вже 15 одиниць води.

Третя ітерація

Після двох виконаних кроків не будемо детально зупиня­ тися на третьому. Розглядаючи малюнок 88, б, визначимо послідовність ребер, якими можна пройти від витоку до стоку, збільшивши потік. Починаючи з вершини 1 з міткою [0, °о]; переходимо лише до вершини 3, помічаючи її міткою [1,30], оскільки по ребру (1,2) йде максимально можливий потік і вер­ шина 2 вже недосяжна. З вершини 3 можна перейти до вер­ шин 2 і 4. Позначаємо їх відповідно мітками [3,5], оскільки вони ще не розглядалися у даній ітерації і саме значеннями 5 визначені пропускні спроможності ребер (3,2) і (3,4). Наступ­ ний хід у вершину 2. З неї можна перейти лише до вершини 5: ребро (2,4) повністю насичене і перехід до вершини 4 неможли­ вий. Скільки води можна передати ще ребром (2,5)? Пропускна спроможність ребра дає змогу додати ще 15 одиниць, але у вер­ шину 2 прийшло лише 5, тому більше немає звідки взяти. Отже, обмежимося цим значенням і поставимо мітку [2,5] біля вершини 5. Далі у нашій послідовності іде вершина 4, яку ми побачили з вершини 3. Однак з неї вершини 6 не видно, оскіль­ ки ребро (4,6) насичене. Після вершини 4 у послідовності іде вершина 5. Переходимо до неї і можемо побачити вершину 6, яка є стоком. Резерв ребра (5,6) становить 7 одиниць води, але передати з вершини 5 можемо лише 5 одиниць. Зробимо це, поставивши мітку [5,5] біля вершини 6 (мал. 89, а).

142

Мал. 89

Черговий прохід мережею завершено, і нам вдалося проштовх­ нути доповнюючим шляхом (1,3), (3,2), (2,5), (5,6) ще 5 одиниць води. Тепер потік мережею становить 20 одиниць (мал. 89, б).

Четверта ітерація

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

Розглянувши поточний стан мережі, зображений на малюнку 89, б, можемо зробити висновок, що частина ребер вже повністю насичена, а деякі ребра ще мають перспективу бути донасиченими. До них відносяться ребра (1,3), (2,5), (3,4), (5,4), (5,6). Спробуємо побудувати новий доповнюючий шлях, використавши ці ребра.

Почнемо, як завжди, з вершини 1, помітивши її тра­ диційною міткою [0, °°] (мал. 90, о). З неї можна перейти лише до вершини 3, передавши туди 25 одиниць резервної води і по­ значивши міткою [1,25] (мал. 90, б).

Далі перейдемо до вершини 3 і побачимо лише вершину 4, куди можна передати, зважаючи на пропускну спроможність

Мал. 90

143

ребра (3,4), лише 5 одиниць води з 25 можливих. Підтвердимо цей факт міткою [3,5] біля вершини 4 (мал. 91, а). А от куди йти далі? Дуже хотілося б потрапити у вершину 2, оскільки саме звідти можна перейти до вершини 6, але як там опинитися? Поставимо собі слушне запитання: а чи вірно ми розподілили воду в кожній вершині мережі? Проаналізувавши сумарні по­ токи води, що входять у кожну вершину і виходять з неї, зазначимо, що ці значення збігаються. Цей факт відомий з ви­ значення мережі: вода ззовні у вершини не поступає, тому скільки до них втікає ребрами, що входять, стільки само і витікає ребрами, що виходять. У вершинах 2 і 4 цей основний принцип мережі справджується.

Уважно розглянувши досліджувану мережу, можна поміти­ ти, що є можливість розподілити потік об'ємом 20 одиниць, який приходить у вершину 2, далі у вершини 4 і 5 інакше, ніж це вийшло у результаті виконання попередніх ітерацій. На­ приклад, ребра (2,5) і (5,6) дають змогу пропустити більше ніж 10 одиниць води, тим самим на це значення зменшиться потік через ребра (2,4) і (4,5). Це, у свою чергу, дасть можливість донаситити ребро (4,6), подавши воду у вершину 4 ребром (3,4). Отже, вирішення проблеми знайдено і можна буде виконати ще одну ітерацію.

Сформулюємо задачу, що виникла, мовою графів так: повер­ немо частину потоку, що попередньо спрямований ребром (2,4), у зворотному напрямі. Насправді, потік не повертається назад, а лише його поточне значення зменшується на деяке значення.

Введемо фіктивне ребро (4,2), позначене на малюнку 91, б пунктирною лінією, що називається зворотним ребром. Усі ре­ ально існуючі у мережі ребра називаються прямими. Ще раз за­ уважимо, що насправді ребра (4,2) у мережі не існує. Уведення його до мережі означатиме лише те, що попередньо спрямова­ ний потік з вершини 2 у вершину 4 зі значенням 10 буде змен­ шено на деяке значення, що не перевищує насиченості прямого ребра. Цей факт зрозумілий, оскільки не можна прибрати з ребра (2,4) більше води, ніж там уже є. Який же потік можна передати зворотним ребром (4,2) у вершину 2? Стільки, скіль­ ки прийшло у вершину 4, тобто 5 одиниць. Це можливо зроби­ ти, оскільки пропускна спроможність зворотного ребра (4,2) така сама, як і прямого (2,4): труба ж одна і та сама! Поставимо мітку [4, -5] біля вершини 2, де на цей раз значення потоку, що передається у неї зворотним ребром з вершини 4, позначимо від'ємним числом - 5 . У послідовність вершин допишемо види­ му вершину 2 з індексом -4, відмічаючи цим, що сюди при­ йшли саме зворотним ребром (мал. 91, б).

144

Отже, вихід знайдено і процес попіуку доповнюючого шляху з витоку до стоку, що можливо збільшить шуканий потік, роз­ блоковано. Дивимося з вершини 2 і бачимо нову вершину 5. У неї можна передати ще 5 одиниць води, які віртуально надійшли з вершини 4, а реально зекономлені у вершині 2. Зауважимо, що резерв ребра (2,5) становить на даний момент 10 одиниць води, однак у вершину 5 може прийти лише 5 оди­ ниць, які додатково подаються з вершини 2. Ставимо мітку [2,5] біля вершини 5 і дописуємо цю вершину у послідовність (мал. 92, а).

Тепер уже з вершини 5 видно стокову вершину 6. Вона буде позначена міткою [5,2], оскільки резерв ребра (5,6) обмежений величиною потоку 2. Таким чином, у вершину 6 надійшло ще 2 одиниці води (мал. 92, б).

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

Логічно було б прибрати уявне ребро (4,2) з мережі, оскіль­ ки воно вже виконало свою функцію. Для цього досить просу - мувати значення потоків, що рухаються прямим ребром (2,4)

145

ребра (3,4), лише 5 одиниць води з 25 можливих. Підтвердимо цей факт міткою [3,5] біля вершини 4 (мал. 91, а). А от куди йти далі? Дуже хотілося б потрапити у вершину 2, оскільки саме звідти можна перейти до вершини 6, але як там опинитися? Поставимо собі слушне запитання: а чи вірно ми розподілили воду в кожній вершині мережі? Проаналізувавши сумарні по­ токи води, що входять у кожну вершину і виходять з неї, зазначимо, що ці значення збігаються. Цей факт відомий з ви­ значення мережі: вода ззовні у вершини не поступає, тому скільки до них втікає ребрами, що входять, стільки само і витікає ребрами, що виходять. У вершинах 2 і 4 цей основний принцип мережі справджується.

Уважно розглянувши досліджувану мережу, можна поміти­ ти, що є можливість розподілити потік об'ємом 20 одиниць, який приходить у вершину 2, далі у вершини 4 і 5 інакше, ніж це вийшло у результаті виконання попередніх ітерацій. На­ приклад, ребра (2,5) і (5,6) дають змогу пропустити більше ніж 10 одиниць води, тим самим на це значення зменшиться потік через ребра (2,4) і (4,5). Це, у свою чергу, дасть можливість донаситити ребро (4,6), подавши воду у вершину 4 ребром (3,4). Отже, вирішення проблеми знайдено і можна буде виконати ще одну ітерацію.

Сформулюємо задачу, що виникла, мовою графів так: повер­ немо частину потоку, що попередньо спрямований ребром (2,4), у зворотному напрямі. Насправді, потік не повертається назад, а лише його поточне значення зменшується на деяке значення.

Введемо фіктивне ребро (4,2), позначене на малюнку 91, б пунктирною лінією, що називається зворотним ребром. Усі ре­ ально існуючі у мережі ребра називаються прямими. Ще раз за­ уважимо, що насправді ребра (4,2) у мережі не існує. Уведення його до мережі означатиме лише те, що попередньо спрямова­ ний потік з вершини 2 у вершину 4 зі значенням 10 буде змен­ шено на деяке значення, що не перевищує насиченості прямого ребра. Цей факт зрозумілий, оскільки не можна прибрати з ребра (2,4) більше води, ніж там уже є. Який же потік можна передати зворотним ребром (4,2) у вершину 2? Стільки, скіль­ ки прийшло у вершину 4, тобто 5 одиниць. Це можливо зроби­ ти, оскільки пропускна спроможність зворотного ребра (4,2) така сама, як і прямого (2,4): труба ж одна і та сама! Поставимо мітку [4, -5] біля вершини 2, де на цей раз значення потоку, що передається у неї зворотним ребром з вершини 4, позначимо від'ємним числом -5. У послідовність вершин допишемо види­ му вершину 2 з індексом -4, відмічаючи цим, що сюди при­ йшли саме зворотним ребром (мал. 91, б).

144