Оптимізація на мережах

Нехай S є довільна, частково орієнтована мережа, кожному ребру u якої приписане невід'ємне число c(u) - пропускна спроможність. Потоком у мережі S називається пара (f, w), де w - деяка орієнтація всіх неорієнтованих ребер мережі, а f(u) - задана на множині всіх ребер функція з невід'ємними значеннями, що не перевершують пропускних спроможностей, і така, що в кожній внутрішній вершині a виконується закон Кірхгофа, відповідно до якого сума значень потоку по ребрах, що входить у вершину, дорівнює сумі потоків по ребрах, що виходить із вершини. Іншими словами, для f(u) виконуються умови:

0 £ f(u) £ c(u) для усіх вершин мережі;

R(a) = 0 для усіх внутрішніх вершин, де

а G(a) (відповідно G'(a)) - множина всіх ребер, що виходять із a (відповідно вхідних у a) при орієнтації w.

Оскільки сума значень R(a) по усіх вершинах мережі, включаючи полюси, дорівнює нулю (кожне ребро є вихідним для однієї вершини і вхідним для іншої), то R(a_s) = - R(b_s). Значення R = R(a_s) називається величиною потоку.

Розглянемо задачу визначення максимального значення R_max потоку через мережу S при заданих значеннях пропускних спроможностей. Відповідь може бути отримана у термінах перетинів мережі.

Перетином мережі називається множина ребер, при видаленні яких мережа стає незв'язною, причому полюса потрапляють у різні компоненти зв'язності. У мережі на рис. 2.11 прикладами перетинів є {d, e, f}, {b, c, e, g, h}, {d, g, h, i}.

Перетин називається простим, якщо при видаленні будь-якого його ребра, він перестає бути перетином. Так, перетини {d, e, f} і {b, c, e, g, h} - прості, а перетин {d, g, h, i} не є таким. Очевидно, що для кожного ребра простого перетину можна зазначити ланцюг, що проходить через це ребро, але не проходить через інші ребра даного перетину.

7 a d h 2

a_S 2 c 4 e 3 g b_S

3 b 4 i

1

f

Рис.2.12. Задача максимального потоку

Якщо у зв'язній мережі віддалиться простий перетин, то мережа розпадеться рівно на дві частини: ліву і праву, що містить a_S і b_S відповідно. Кожне ребро простого перетину зв'язує вершини з різних частин. Будемо називати ребро перетину прямим, якщо воно в мережі не орієнтоване або орієнтоване зліва праворуч, і оберненим у противному випадку. Буде орієнтоване ребро прямим або оберненим, залежить від вибору перетину. Так, у прикладі ребро е в перетинах {d, e, f} і {b, c, e, g, h} - обернене, а в перетині {a, c, e, g, i}- пряме.

Кожному простому перетину W припишемо пропускну спроможність c(W), рівну сумі пропускних спроможностей усіх його прямих ребер. У прикладі на рис.2.12 перетин {d, e, f} має пропускну спроможність 5+1=6, а перетин {b, c, e, g, h} - 3+2+3+2=10.

Теорема про максимальну пропускну спроможність мережі сформульована Фордом і Фалкерсоном так: максимальний розмір потоку R_max через мережу S дорівнює мінімальній пропускній спроможності c_min її простих перетинів. Ця теорема покладена в основу задачі визначення максимальної пропускної спроможності мережі.

Розглянемо алгоритм Форда - Фалкерсона для розв'язання цієї задачі.

Крок 0.Нехай джерела позначені, але не переглянуті, а всі інші вузли не позначені.

Крок 1. Вибрати довільний позначений, але не переглянутий вузол i.

Крок 2. Переглянути всі дуги e (i, j) із пропускною спроможністю a _е > 0, що з'єднують вузол i з ще не позначеними вузлами j. Приписати позначки вузлам j і відзначити дуги e _j = e = (i, j). Тепер вузол i позначений та переглянутий, вузли j позначені, але не переглянуті. Якщо при цьому стік виявився позначеним, то необхідний ланцюг знайдений. У противному випадку після перегляду по всіх дугах (i, j) перейти до кроку 3.

Крок 3.Нехай вузол i позначений і переглянутий. Перейти до кроку 1 і повторювати кроки алгоритму доти, поки не залишиться позначених і не переглянутих вузлів. На цьому пошук максимального потоку закінчується.

Розглянемо приклад. Нехай необхідно знайти максимальний потік для графа (рис.2.13).

7.7 I

c e

16 I 9.8 I 12 I 7 I

8.8 I d

s a j

12.1 12 I 5 I

f 11 I

6.2 I 11 I 15 I 20 I

7.5 I

b t

8 I

Рис. 2.13. Заданий граф

Позначено: I - ресурси не використані; R - ресурси використані цілком; IR - ресурси використані частково.

1. Вибираємо один із довільних маршрутів (рис.2.14). Нехай це буде маршрут (s, b), (b, t).

p1 = min {f(s, b), f(b, t)} = min {6.2; 8} = 6.2.

c I e

I

I I d I

I

s a I j

I I I

f

R I I

I

b t

IR

Рис.2.14. Перший маршрут

2. Маршрут (s, a), (a, f), (f, t) наведений на рис.2.15.

p2 = min {f(s, a), f(a, f), f(f, t)} = min {12.1; 12; 15} = 12; P_S[AK1] = 18.2.

I

c e

I

I I d I

I

s a I j

IR R I

f

R I I IR I

b t IR

Рис.2.15. Другий маршрут

3. Маршрут (s, a), (a, b), (b, f), (f, t) наведений на рис.2.16.

p3 = min {f(s, a), f(a, b), f(b, f), f(f, t)} = min {0.1; 11; 7.5; 3} = 0.1; P_S = 18,3.

I

c e

I

I I d I

I

s a I j

R R I

f

R IR IR I

IR b t

IR

Рис.2.16. Третій маршрут

4. Наступний маршрут (s, c), (c, e), (e, j), (j, t) наведений на рис.2.17.

p4 = min {f(s, c), f(c, e), f(e, j), f(j, t)} = min {16; 7.7; 7; 20} = 7; P_S = 25.3.

c IR e

I

IR I d R

IR

s a R j

IR R I

f

R IR IR IR

R b t

R

Рис.2.17. Четвертий маршрут

Таким чином, максимальний потік буде 25.3 одиниць.

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

Розглянемо алгоритм Дейкстри для визначення найкоротшого шляху (ланцюга) з початку в стік.

Крок 0. Вибрати як перспективну множину вузлів множину S _c = S ₀ і покласти d _i = 0 для i ÎS ₀ та d _i = ¥ для i Ï S ₀.

Крок 1. Вибрати вузол i ^* Î S _c, якому відповідає найменше значення d_i (i Î S₀). Знайдений в такий спосіб розмір d _i відповідає найкоротшому шляху з деякого джерела у вузол i^* (довжиною дуги є c _e), а дуга e _i (визначена для усіх вузлів i Î S _c, крім джерел) є остання дуга шляху. Якщо i * - стік, то процедура пошуку найкоротшого шляху закінчується.

Крок 2. Переглянути дуги e = (i ^*, j) і замінити оцінку d _j на min {d _j, d _i + c _e}. Якщо d _j була дорівнена ¥, увести вузол j у S _c. Якщо d _j зменшилася, увести позначення e _j = e = (i^*, j).

Крок 3. Видалити i^* із S _c і перейти до кроку 1, якщо множина S _c не порожня. На цьому пошук найкоротшого шляху закінчується.

Розглянемо приклад.

Для мережі, показаної на рис.2.18, визначити найкоротший шлях із початку в стік.

7.7

c e

16 9.8 d 12 7

8.8

s a 5 j

Поча- 12.1

ток 12 f 11

6.2 7.5 15 20

b t

8 Стік

Рис. 2.18. Мережа для визначення найкоротшого шляху

1. Фарбуємо вершину s.

Приймемо d(s) = 0;

d(a) = d(b) = d(c) = d(e) =d(f) = d(j) = ¥.

2. Поточна змінна y = s.

d(a) = min { d(a), d(s) + d(s, a)} = min {(; 0 + 12.1} = 12.1;

d(b) = min {d(b), d(s) + d(s, b)} = min {(; 0 + 6.2} = 6.2;

d(c) = min {d(c), d(s) + d(s, c)} = min {(; 0 + 16 } = 16;

d(d) = min {d(d), d(s) + d(s, d)} = min {(; 0 + (} = ¥;

d(e) = min {d(e), d(s) + d(s, e)} = min {(; 0 + (} = ¥;

d(f) = min {d(f), d(s) + d(s, f)} = min {(; 0 + (} = ¥;

d(j) = min {d(j), d(s) + d(s, j)} = min {(; 0 + (} = ¥;

d(t) = min {d(t), d(s) + d(s, t)} = min {(; 0 + (} = ¥;

min {d(a), d(b), d(c), d(d), d(e), d(f), d(j), d(t)} =

= min {12.1; 6.2; 16; ¥; ¥; ¥; ¥; ¥} = 6.2; d(b) = 6.2. Фарбуємо вершину b.

3. Поточна змінна y = b.

d(a) = min {d(a), d(b) + d(b, a)} = min {12.1; 6.2 + ¥} = 12.1;

d(c) = min {d(c), d(b) + d(b, c)} = min {16; 6.2 + ¥} = 16;

d(d) = min {d(d), d(b) + d(b, d)} = min {¥; 6.2 + ¥} = ¥;

d(e) = min {d(e), d(b) + d(b, e) } = min {¥; 6.2 + ¥} = ¥;

d(f) = min {d(f), d(b) + d(b, f) } = min {¥; 6.2 + 7.5} = 13.7;

d(j) = min {d(j), d(b) + d(b, j) } = min {¥; 6.2 + (} = ¥;

d(t) = min {d(t), d(b) + d(b, t) } = min {¥; 6.2 + 8} = 14.2;

min {d(a), d(c), d(d), d(e), d(f0, d(j),d(t)} =

= min {12.1; 16; ¥; ¥; 13.7; ¥; ¥} = 12.1; d(a) = 12.1. Фарбуємо вершину a.

4. Поточна змінна y = a.

d(c) = min {d(c), d(a) + d(a, c)} = min {16; 12.1 + 9.8} = 16;

d(d) = min {d(d), d(a) + d(a, d)} = min {¥; 12.1 + 8.8} = 20.9;

d(e) = min {d(e), d(a) + d(a, e)} = min {¥; 12.1 + ¥} = ¥;

d(f) = min {d(f), d(a) + d(a, f)} = min {13.7; 12.1 + 12} = 13.7;

d(j) = min {d(j), d(a) + d(a, j)} = min {¥; 12.1 +¥} = ¥;

d(t) = min {d(t), d(b)+d(b, t)} = min {¥; 12.1 + ¥, 6.2+8} = 14.2;

min {d(c), d(d), d(e), d(f), d(j), d(t)} =

= min {16; 20.9; ¥; 13.7; ¥; ¥} =13.7; d(f) = 13.7.

Фарбуємо вершину f.

5. Поточна змінна y = f.

d(c) = min {d(c), d(f) + d(f, c)} = min {16; 13.7 + ¥} = 16;

d(d) = min {d(d), d(f) + d(f, d)} = min {20.9; 13.7 + ¥} = 20.9;

d(e) = min {d(e), d(f) + d(f, e)} = min {¥; 13.7 + ¥} = ¥;

d(j) = min {d(j), d(f) + d(f, j)} = min {¥; 13.7 +11} = 24.7;

d(t) = min {d(t), d(f) + d(f, t), d(b)+d(b, t)} = min {¥; 13.7 + 15, 6.2+8} = 14.2;

min {d(c), d(d), d(e), d(j), d(t)} = min {16; 20.9; ¥; 24.7; 14.2} =14.2;

d(t) = 14.2.

Фарбуємо вершину t.

Висновок. Найкоротший шлях з початку s у стік t тільки один, складається з дуг (s, b) і (b, t) та дорівнює 14.2 одиниць.

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

Дата добавления: 2014-11-29