Лекція 14.15. ПРИКЛАД ЗАСТОСУВАННЯ АЛГОРИТМА ФОРДА_ФАЛКЕРСОНА

Приклад 11. Розглянемо граф, зображений на Рисунке 12. Потрібно знайти максимальний потік від х₁ до x_9.

Розв’язок. Як початковий візьмемо потік із нульовими значеннями на всіх дугах x_ij = 0, "_ij.

Пропускні спроможності дуг q_ij зазначені на Рисунке 12.

Крок 1. Припишемо вершині x_i позначку (+ x₁, ¥).

Крок 2.а) множина непозначених вершин: {x_j|x_j Î F(x₁), x_1j < q_1j} = {x₁, x₄}.

Вершині x₂ приписується позначка (+x₁, min (¥, q₁₂ - x₁₂)) = (+x₁, min (¥, 14-0) = (+x₁, 14).

Вершині x₄ приписується позначка (+x₁, min (¥, q₁₄ - x₁₄)) = (+x₁, min (¥, 23-0) = (+x₁, 23).

Рисунок 12. Вихідний граф.

б) множина непозначених вершин: {x_j|x_j Î F^-1(x₁), x_j1 > 0} = Æ.

Отже, x₁ позначена і переглянута, x₂ і x₄, позначені і не переглянуті, а всі інші вершини не позначені.

Повторюємо крок 2, переглядаючи вершину x₂ (вершини переглядаються в порядку зростання їхніх номерів). Множина непозначених вершин:

a) {x_j|x_j Î F(x₂), x_2j < q_2j} = {x₃}.

Позначка для x₃: (+x₂, min (14, q₂₃ - x₂₃)) = (+x₁, min (14, 10-0) = (+x₂, 10).

б) Множина непозначених вершин

{x_j|x_j Î F^-1(x₂), x_j2 > 0} = Æ.

Тепер вершини х₁ і х₂ позначені і переглянуті, а x₃, x₄ позначені і не переглянуті.

Переглядаємо вершину x₃.

а) множина непозначених вершин: {x_j|x_j Î F(x₃), x_3j < q_3j} = {x₅, x₈}.

Для x₅ позначкою є (+x₃, min (10, 12-0)= (+x₃, 10),

для x₈ позначкою є (+x₃, min (10, 18-0) = (+x₃, 10).

Переглядаючи x₄, ніяких позначок розставити не можна, тому що всі суміжні з x₄ вершини вже позначені. Переглядаючи x₅, одержимо такі позначки:для x₆ - (+x₅, min (10, 25-10) = (+x₅, 10);

для x₇ - (+x₅, min (10, 4-0) = (+x₅, 4).

Переглядаючи x₇ одержимо позначку для x₉ - (+x₅, min (4, 15-0) = (+x₅, 4).

Переходячи до кроків 4 і 5, отримаємо

x = x₉ - відповідна позначка (+x₇, 4). Потік x₇₉ змінюємо, додаючи d(x₉) = 4, x₇₉ = 0 + 4 = 4;

x = x₇ - відповідна позначка (+x₅, 4). Потік x₅₇ = 0 + 4 = 4;

x = x₅ - відповідна позначка (+x₃,10). Потік x₃₅ = 0 + 4 = 4;

x = x₂ - відповідна позначка (+х_1, 14). Потік x₁₂ = 0 + 4 = 4.

Всі інші значення потоків залишилися рівними нулю. Потік наприкінці кроку 5 і позначки вершини до їхнього стирання на кроці 6 показані на Рисунок 13а. Стираючи позначки у вершин і повертаючись до кроку 1 для другого проходу, одержимо такі нові позначки:

для x₁ - (+x₁,¥);

для x₂ - (+x₁, min (¥, 14-4) = (+x₁, 10);

для x₃ - (+x₁, min (¥, 23-0) = (+x₂, 23). Вершина x₁ позначена і переглянута. Переглядаючи вершину x₂, одержимо позначку

для x₃ - (+x₂, min (10, 10-4)) = (+x₂, 6). Вершина x₂ позначена і переглянута.

Переглядаючи вершину x₃, одержимо позначки: для x₅ - (+x₃, min (6, 12-4)) = (+x₃, 6);

для x₈ - (+x₃, min (6, 18-0)) = (+x₃, 6).

Вершина x₃ позначена і переглянута. Переглядаючи вершину x_5, одержимо позначки:

для x₆ - (+x₅, min (6, 25-0)) = (+x₅, 6). Вершина x₅ позначена і переглянута.

Переглядаючи вершину x_6, знаходимо, що позначкою для x₇ будет (+x₆, min (6, 7-0)) = (+x₆, 6).

Тепер вершина x₆ позначена і переглянута. Позначкою для x₉ : (+x₇, min (6, 15-4)) = (+x₇, 6).

Кроки 4 і 5. Нові потоки збільшилися в такий спосіб:

x₇₉ = 4 + 6 = 10; x₆₇ = 0 + 6 = 6; x₅₆ = 0 + 6 = 6;

x₃₅ = 4 + 6 = 10; x₂₃ = 4 + 6 = 10; x₁₂ = 4 + 6 = 10.

Всі інші значення потоку не змінилися. Новий потік і позначки вершин до стирання показані на Рисунок 13б.

Аналізуючи всі етапи визначення потоків, одержуємо після кожного проходу алгоритма потоки і позначки, зображені послідовно на Рисунках 14-17. Алгоритм закінчує роботу, коли тільки вершина x₆ може бути позначена. Розріз графа зображен на Рисунке 17 пунктиром . Множина містить позначені вершини, а множина - непозначені вершини. Потік, що відповідає дугам (x₂, x₃), (x₃, x₆), (x₆, x₇), (x₆, x₈), (x₅, x₇) є максимальним із значенням

10 + 0 + 8 + 7 + 4 = 29.

Лекція 16,17. ЗАДАЧА ПОШУКУ НАЙКОРОТШОГО (КРИТИЧНОГО) ШЛЯХУ МІЖ ДВОМА ЗАДАНИМИ ВЕРШИНАМИ S И t (cij ³ 0)

Нехай l(x_i) - позначка вершини x_i.

1. Приcвоєння початкових значень

Крок 1. Покласти l(s) = 0 і вважати цю позначку постійною.

Покласти для всіх l(x_i) = ¥ і вважати ці позначки тимчасовими. Покласти p = s.

2. Відновлення позначок

Крок 2. Для всіх x_iÎF(р), позначки яких тимчасові, змінити позначки у відповідності з таким виразом:

Перетворення позначки в постійну

Крок 3. Серед усіх вершин із тимчасовими позначками знайти таку, для якої

.

Крок 4. Вважати позначку вершини x_i^* постійною і покласти p = x_i^*.

Якщо p = t, то l(p) є довжиною найкоротшого шляху. Якщо p ¹ t, то перейти до кроку 2.

Приклад 35. Розглянемо граф, зображений на Рисунке 18 , де кожне неорієнтоване ребро розглядається як пару протилежно орієнтованих дуг рівної ваги. Матриця С ваг приведена нижче.

Рисунок 18. Вихідний граф.

Матриця ваг

Крок 1. l(x₁) = 0 - позначка постійна.

l(x₁) = р, "x_i ¹ x_i

p = x_i

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

Крок 2. F(p) = {x₂, x₇, x₈, x₉} множина вершин, в які є дуга з x₁.

Позначки l(x₂), l(x₇), l(x₈), l(x₉) - тимчасові і рівні ¥.

Обновляємо позначку вершини x₂, для цього находим

min {l(x₂), l(p) + c(p, x₂)}. Тому що l(x₂) = ¥, а l(p) = 0, с₁₂ = 10, то одержуємо min {¥, 0+10}= 10, виходить, l(x₂) = 10.

Аналогічно знаходимо

l(x₇) = min {¥, 0+3}= 3;

l(x₈) = min {¥, 0+6}= 6;

l(x₉) = min {¥, 0+12}= 12.

Крок 3. Знаходимо min {l(x_i)}, тобто

відповідає x₇

Крок 4. x₇ одержує постійну позначку l(x₇) = 3; p = x₇.

Крок 5. Не всі вершини мають постійну позначку, тому переходимо до кроку 2. Позначки на початку другої ітерації показані на Рисунке 19. Із знаком + показані постійні позначки.

Рисунок 19. Перша итерація.

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

Крок 2. F(p) = F(x₇) = {x₂, x₄, x₆, x₉} - усі позначки тимчасові.

Обновляємо позначку вершини x₂. З огляду на те, що l(x₂) = 10, l(p) = 3,

C₇₂ = 2, знаходимо min {10, 3+2}= 5, тобто l(x₂) = 5.

Аналогічно l(x₄) = min {¥, 3+4}= 7;

l(x₆) = min {¥, 3+14}= 17;

l(x₉) = min {12, 3+24}= 12.

Крок 3. Знаходимо min {l(x_i)}, тобто

відповідає x₂

Крок 4. x₂ одержує постійну позначку l(x₂) = 5; p = x₂.

Крок 5. Перейти до кроку 2.

Обчислення по кожній ітерації зручно звести в таблицю, наведену на Рисунок 20

Рисунок 20. Сводная таблиця всіх итерацій.

Перший рядок таблиці відповідає початковим позначкам вершин. Показані зліва в таблиці вершини зі знаком + одержують постійні позначки, а числа зі знаком + у рядку таблиці відповідають min{l(x_i)}. Після першої ітерації постійну позначку одержала вершина x₇, а min{l(x_i)} = 3. Після того, як вершина x₇ одержала постійну позначку, числа в стовпчику, що відповідає х₇ залишаються незмінними.

На четвертій ітерації постійну позначку одержує х₄, тобто р = х₄, а х₄ відповідає стокові t. Таким чином, алгоритм закінчує роботу, довжина найкоротшого шляху дорівнює

l(p) = l(x₄) = 7.

Для знаходження найкоротшого шляху використаємо співвідношення:

l(x_i') + c(x_i', x_i) = l(x_i), (*)

x_i' - вершина, що безпосередньо передує вершині x_i у найкоротшому шляху від S до x_i. Якщо існує декілька найкоротших шляхів від S до якоїсь іншої вершини, то при деякій фіксованій вершині x_i' співвідношення (*) буде виконуватися більш ніж для однієї вершини x_i. У цьому випадку вибір може бути або довільним (якщо потрібний якийсь один найкоротший шлях між S і x_i), або таким, що розглядаються всі дуги, які входять в якийсь із найкоротших шляхів.

Знайдемо найкоротший шлях від x₁ до x₂. Для цього знаходимо вершину х₂' із співвідношення:

l(x₂') + c(x₂', x₂) = l(x₂) = 5.

У стовпчику, x₂ матриці С, і в останньому рядку таблиці (див. Рисунок 20) знаходимо числа, сума яких дорівнює 5. У стовпчику x₂ матриці С містяться числа 10, 18, 2, 13. Потрібно взяти число 2, що відповідає вершині x₇

l(x₇') + c(x₇', x₇) = 3 + 2 = 5,

тобто вершиною, що задовольняє співвідношенню (*), є x₇.

Поклавши x_i = x₇, знаходимо вершину безпосередньо передуючу x₇ у найкоротшому шляху від x₁ до x₂. Вершина x₇', повинна задовольняти співвідношення:

l(x₇') + c(x7', x₇) = 3.

У стовпчику x₇ матриці С містяться числа 3, 2, 4, 14, 24. Можна брати або 2, або 3. Візьмемо число, рівне 2, йому відповідає вершина x₂, l(x₂) + c(x₂, x₇) = 2 + 5 ¹ 3, виходить, x₂ не задовольняє співвідношення (*). Залишається вершина x₁, l(x₁) + c(x₁, x₇) = 0 + 3 = 3. Таким чином, єдиною вершиною яка задовольняє співвідношення (*), є x₁. Отже, найкоротшим шляхом від x₁ до x₂ є шлях (x₁, x₇, x₂).

Знаходимо найкоротший шлях від x₁ до x₃, відзначимо, що l(x₃) = 23.

У стовпчику x₃ матриці С містяться числа 18, 25, 20. Придатним числом є 18, якому відповідає x₂.

l(x₂) + c(x₂, x₃) = 5 + 18 = 23 = l(x₃).

Виходить, найкоротший шлях від x₁ до x₃ - це шлях (x₁, x₇, x₂, x₃).

Аналогічно можна знайти найкоротші шляхи від вершини x₁ до будь-якої вершини мережного графа. Ці дуги зображені на Рисунке 21 жирними лініями. З Рисунку 21 очевидно, що найкоротший шлях від x₁ до x₄ - це шлях (x₁, x₇, x₄).

Рисунок 21. Найкоротший шлях.

Для того, щоб знайти критичний шлях у шляховому графіку, необхідно внести такі зміни на кроці 2 і кроці 3.

Крок 1. Покласти l(s) = 0 і вважати цю позначку постійною.

Покласти для всіх l(x_i) = - ¥ і вважати ці позначки тимчасовими. Покласти p = s.

Крок 2. l(x_i) = max {l(x_i), l(p) + c(p, x_i)}

Крок 3. l(x_i*) = max {l(x_i)} тобто замість мінімальних значень брати максимальні, а замість матриці вартостей С = (с_ij) - розглядати матрицю часу переходу від i-ой до j-ой роботи T = (t_ij).