Лекція 14. 15. Приклад застосування алгоритма форда_фалкерсона

Збільшення потоку

Розставляння позначок

Позначка довільної вершини х_i складається з двох частин і може бути двох видів:

(+ x_j, d) або (- x_j, d)

де + x_j означає, що потік припускає збільшення уздовж дуги (x_{i ,} x_j); -x_j - потік може бути зменшений уздовж дуги (x_{i ,} x_j); d - максимальний розмір додаткового потоку, що може протікати від S до x_i, уздовж побудованого ланцюга потоку. Вершина може знаходитися в одному із трьох станів:

1. Вершині приписана позначка, і вершина переглянута (тобто вона має позначку і всі суміжні з нею вершини "оброблені").

2. Позначка приписана, але вершина не переглянута (тобто вона має позначку, але не всі суміжні з нею вершини "оброблені").

3. Вершина не має позначки.

Спочатку усі вершини не мають позначок.

Крок 1. Привласнити вершині х_i = S позначку (+ S, ¥).

Крок 2. Взяти деяку не переглянуту вершину x_i із позначкою; нехай її позначка є (± x_k, d (x_i));

а) кожній непозначеній вершині x_j Î F (x_j), для якої x _ij > q_ij,., привласнити позначку

(+ x_k, d (x_j)), де d (x_j) = min { d (x_i), q_ij - x _ij};

б) кожній непозначеній вершині x_j Î F^-1 (x_j), для якої позначку x _ij > 0, привласнити позначку (- x_j, d (x_j)), де d (x_j) = min { d (x_i), x _ij}.

Тепер вершина x_i і позначена, і переглянута, а вершини позначки яким привласнені, є непереглянутими.

Крок 3. Повторювати крок 2 доти, поки або вершина t буде позначеною, і тоді перейти до кроку 4, або t буде не позначена, і ніяких інших позначок не можна розставити; у цьому випадку алгоритм закінчує роботу з максимальним вектором потоку.

Крок 4. Покласти х = t і перейти до кроку 5.

Крок 5. а) якщо позначка у вершині x_j має вид (+ x_k, d (x_j)), то змінити потік уздовж дуги

(x_k, x_j) із x _kj на x _kj + d (t);

б) якщо позначка у вершині x_j має вид (-x_j, d (x_j)), то змінити потік уздовж дуги

(x_k, x_j) із x _kj на x _kj - d (t).

Крок 6. Якщо x_j = S, то стерти всі позначки і повернутися до кроку 1, знову розставляючи позначки, але використовуючи вже покращаний потік, знайдений на кроці 5. Якщо x_j ¹ S, те повернутися до кроку 5, вважаючи x = x_k.

Приклад 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. Вихідний граф.

Матриця ваг

С =		x1	x2	x3	x4	x5	x6	x7	x8	x9
x1
x2
x3
x4
x5
x6
x7
x8
x9

Крок 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

	x1	x2	x3	х4	x5	x6	x7	x8	х9
х1^+	0^+	¥	¥	¥	¥	¥	¥	¥	¥
х7^+			¥	¥	¥	¥	3^+
х2^+		5^+	¥		¥
х8^+					¥			6^+
х4^+				7^+

Рисунок 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).

Дата добавления: 2015-06-04