Оптимізація на мережах
Нехай 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(as) = - R(bs). Значення R = R(as) називається величиною потоку.
Розглянемо задачу визначення максимального значення Rmax потоку через мережу 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
 |  |
aS 2 c 4 e 3 g bS
3 b 4 i
1
f
Рис.2.12. Задача максимального потоку
Якщо у зв'язній мережі віддалиться простий перетин, то мережа розпадеться рівно на дві частини: ліву і праву, що містить aS і bS відповідно. Кожне ребро простого перетину зв'язує вершини з різних частин. Будемо називати ребро перетину прямим, якщо воно в мережі не орієнтоване або орієнтоване зліва праворуч, і оберненим у противному випадку. Буде орієнтоване ребро прямим або оберненим, залежить від вибору перетину. Так, у прикладі ребро е в перетинах {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.
Теорема про максимальну пропускну спроможність мережі сформульована Фордом і Фалкерсоном так: максимальний розмір потоку Rmax через мережу S дорівнює мінімальній пропускній спроможності cmin її простих перетинів. Ця теорема покладена в основу задачі визначення максимальної пропускної спроможності мережі.
Розглянемо алгоритм Форда - Фалкерсона для розв'язання цієї задачі.
Крок 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; PS[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; PS = 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; PS = 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 0 і покласти d i = 0 для i ÎS 0 та d i = ¥ для i Ï S 0 .
Крок 1. Вибрати вузол i * Î S c, якому відповідає найменше значення di ( i Î S0 ) . Знайдений в такий спосіб розмір 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 одиниць.
Розглянуті положення за теорією графів можуть використовуватися при розв'язанні задач моделювання об'єктів із складною внутрішньою структурою. Алгоритми, побудовані з використанням теорії графів, відрізняються високою швидкодією, а моделі об'єктів і процесів отримуються наочними і простими в програмуванні.