Тема 35. Мережі та потоки

35.1. Мережі та потоки

Мережу можна представити як систему, яка транспортує деякий продукт з однієї точки в іншу. Цим продуктом можуть бути люди, електроенергія, природній газ, нафта та багато іншого. Прикладом може бути система нафтопроводу, де нафта тече з однієї точки до інших точок систем. Використовуючи таке представлення розглянемо мережу як орієнтований граф, де кожному ребру e = (v, u) відповідає додатне дійсне число c(e), яке називається пропускною спроможністю ребра e. Якщо між вершинами немає ребра, то пропускна спроможність дорівнює нулю. Такий граф не може мати петель, адже розглядаються задачі для транспортування продукту тільки між різними вершинами. Необхідна умова: орієнтований граф повинен бути зв’язним, адже якщо є шлях з s в t, то нас буде цікавити тільки компонента, які містить s та t. Розглянемо також особливу вершину s, яка називається джерелом, – степінь заходу в неї дорівнює 0 (d⁺(s) = 0), а також вершину t, яка називається стоком, – степінь виходу з неї дорівнює також 0 (d^–(t) = 0).

Означення 35.1. Мережа – це орієнтований граф G = (V, E) разом з ваговою функцією c: ER⁺ та виділеними вершинам s та t, такими що d⁺(s) = 0 та d^–(t) = 0.

Мережу зручно представляти за допомогою матриці пропускних спроможностей C = ||c_ij||, де елемент матриці c_ij = c(v_i, v_j) дорівнює пропускній спроможності ребра (v_i, v_j), якщо воно існує, та c_ij = 0, якщо вершини v_i та v_j несуміжні.

Для кожного ребра e розглянемо значення функції f(e), яке визначає потік через це ребро. Зрозуміло, що величина потоку в ребрі не може перебільшувати пропускну спроможність цього ребра. Також будемо вимагати, щоб потік, який заходить у вершину дорівнював потоку, який виходить з вершини (окрім джерела s та стоку t).

Означення 35.2. Функція f: ER⁺ називається потоком в мережі G, якщо:

1. Для кожного ребра (u, v)E виконується 0  f(u, v)  c(u, v), тобто потік через ребро не є від’ємними та не перебільшує пропускну спроможність ребра.

2. Для кожної вершини vV окрім джерела s та стоку t виконується

.

Друга умова називається умовою збереження потоку.

Означення 35.3. Якщо s – джерело потоку, то число називається величиною потоку. Якщо f(u,v) = c(u,v), то ребро (u, v) називається насиченим.

Рис. 35.1.

На рис. 35.1 наведено приклад мережі з потоком. Ребра позначені парами чисел, де перше число – пропускна спроможність ребра, а друге – потік через дане ребро. Величина потоку становить 4 + 2 = 6. Як можна пересвідчитись, розмір потоку, який потрапляє у стік t, дорівнює також 6 = 3 + 2 + 1. Це підтверджує наступна теорема.

Теорема 35.1. Для будь-якого фіксованого потоку f виконується:

.

Доведення. Нехай S – підмножина множини вершин V, яка містить s, але не містить t. Також T = V\S. Для будь-якої вершини v  s, t виконується умова збереження потоку:

---

.

Відповідно, сумування по вершинам, які належать S\{s}, дає:

або

.

Тому, якщо включити s, отримаємо:

.

Нехай (S, T) – множина всіх ребер з S в T, тобто (S, T) = {e: початкова вершина ребра e належить S, а кінцева вершина ребра e належить T}. Аналогічно (T, S) – множина всіх вершин з T в S. Розглянемо знову

.

У випадку, коли початкова та кінцева вершини ребра e належать S, e з’являється в обох сумах і, відповідно, взаємно скорочується. Якщо виключити такі ребра, то у лівій сумі отримаємо тільки ребра, які йдуть з S в T, а у правій сумі – тільки ребра, які йдуть з T в S. Таким чином маємо:

.

Відповідно,

,

тобто для будь-якої заданої множини вершин S, яка містить s, але не містить t, різниця потоку, який виходить з S, та потоку, який входить у S, дорівнює , тобто потоку, якій виходить з вершини s. Тепер нехай S = V\{t}, так що T = {t}. Тоді є просто потік, який вливається в t, так що

та , оскільки цей потік витікає з t. Відповідно,

і отже

. ►

Наслідок. Нехай S – підмножина множини вершин V, яка містить s, але не містить t, та Т = V\S. Тоді

.

35.2. Розрізи

Означення 35.4. Нехай S – підмножина множини вершин V та T = V\S. Тоді множина P = {e: e  (S,T)} називається розрізом. Якщо sS та tT, то розріз називається s-t розрізом.

Означення 35.5. Величина називається пропускною спроможністю розрізу.

Означення 35.6. Потік f* в мережі називається максимальним потоком, якщо (f*)  (f) для будь-якого можливого потоку f в мережі. s-t розріз (S, T) називається мінімальним розрізом, якщо C(S, T) не більше пропускної спроможності будь-якого іншого s-t розрізу.

Теорема 35.2. Нехай S – підмножина множини вершин V, яка містить s, але не містить t, та T = V\S. Тоді (f)  C(S,T).

Доведення.

.►

Наслідок 1. Якщо (f) = C(S, T) для деякого потоку f, а розріз (S, T) є s-t розрізом, то f – максимальний потік, а C – мінімальний розріз.

Наслідок 2. Для деякого потоку f та s-t розрізу (S, T) рівність (f) = C(S, T) виконується тоді й лише тоді, коли f(e) = c(e) для всіх e(S, T) та f(e) = 0 для всіх e(T, S).

а	б

Рис 35.2.

35.3. Максимальні потоки

Розглянемо способи визначення максимального потоку в мережі. На рис. 35.2, а зображено мережу, а на рис. 35.2, б вказано максимальний потік в цій мережі. Зазначимо, що максимальний потік не обов’язково повинен бути єдиними. В даному випадку відомо, що потік максимальний, тому що величина потоку, який виходить з джерела s, не може бути більшим за суму пропускних спроможностей ребер, які виходять з s.

Слід звернути увагу, що якщо потік з джерела дорівнює сумі пропускних спроможностей ребер, які виходять з джерела, або потік, якій втікає в стік, дорівнює пропускній спроможності ребер, які входять в стік, то потік є максимальним. Однак, потік може бути максимальним й без виконання будь-якої з цих ознак.

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

---

Отже, як знаходити максимальні в сенсі потоків мережі? Для цього сформуємо шляхи з s в t, не звертаючи увагу на направлення ребер. Такі шляхи назвемо ланцюгами. Одним з таких шляхів для мережі з рис. 35.3, а є

.

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

.

Однак, при розгляді ланцюга

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

,

що збільшує потік на 2.

а	б

Рис. 35.3.

Перше питання, яке постає: чому обирається 2? Зрозуміло, що потік бажано збільшити якомога більше. Але він не може перевищити пропускну спроможність жодного з заданих ребер. Саме тому ми обмежені величиною 2. Крім того, якщо ребро має направлення, яке протилежне мережі, то неможна зменшувати потік через це ребро більше, ніж на поточну величину потоку через нього, інакше отримаємо від’ємний потік.

Друге питання: як це впливає на збереження потоку? Пересвідчимось, що умова збереження потоку виконується. Розглянемо, наприклад, зміну

на

.

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

на

потік з вершини b в вершину e збільшений на ту ж саму величину, на яку зменшений потік з вершини d у вершину e, тому чистий потік у вершині e лишився тим самим. Нарешті, розглянемо зміну

на

.

Потік з d в e зменшений на ту ж величину, на яку збільшений потік з d в c. Тому чистий потік у вершині d лишився незміннім.

Процес збільшення потоку в мережі дуже простий. Формуємо ланцюг з s в t. Якщо можливо, то збільшуємо потік, при цьому визначаємо найбільшу величину, яку можна додати до кожного з ребер, які мають те саме направлення, що й мережа, та яку можна відняти з кожного ребра, які мають протилежне направлення, при цьому не утворюючи від’ємний потік. Оскільки останнє ребро, яке входить в t, має те саме направлення, що й ланцюг, то потік в t збільшується. Аналогічно, ребро, яке виходить з s, має теж саме направлення, що й мережа, тому потік з s теж збільшується.

До цього часу розглядався спосіб збільшення існуючого потоку. А з якого потоку починати? Відповідь проста – слід починати з нульового потоку, тобто коли потік через кожне ребро дорівнює 0, а потім збільшувати його.

35.4. Алгоритм Форда-Фалкерсона

Тепер перейдемо до систематичного алгоритму для знаходження максимального потоку. Кожній вершині поставимо у відповідність впорядковану пару. Перший елемент пари – попередня вершина у ланцюгу, що розглядається, потрібна для того щоб визначити зворотній шлях. Другий елемент пари – резерв, тобто величина, на яку можна збільшити потік в кожному ребрі уздовж шляху, якщо орієнтація ребра співпадає з напрямом мережі (таку орієнтацію назвемо правильною), або зменшити потік, якщо ребро орієнтовано неправильно. Простіше кажучи, резерв заданої вершини дорівнює максимальній величині, на яку потік уздовж ланцюга до цієї вершини можна збільшити без порушення самого потоку. Розглянемо також множину M, яка містить всі вершини, які не задіяні при побудові ланцюга до t. Якщо M виявиться порожньою до того, як буде досягнута t, то більше немає вершин, які можна перевірити на шляху до t, тому й немає іншого шляху в t, і немає більше можливості збільшити потік, – отже потік максимальний.

---

Алгоритм Форда-Фалкерсона знаходження максимального потоку

1. Встановити попередника кожної вершини та резерв невизначеними. Вершина помічена, якщо її резерв не є невизначеним. Встановити резерв вершини s рівним , для того щоб вона не обмежувала резерв інших вершин. Встановити М = {s}.

2. Якщо M порожня, то потік максимізований. Якщо M не є порожньою, то обрати довільний елемент з M та видаляємо його. Нехай цей елемент v.

3. Якщо вершина w не помічена, (v, w) є ребром та f(v, w) < c(v, w), то встановити резерв вершини w рівним мінімуму величини c(v, w) – f(v, w) та резерву вершини v. Встановити попередника вершини w в v. Якщо w  t, то додати w в M.

4. Якщо вершина w не помічена, (w, v) є ребром та f(w, v) > 0, то встановити резерв вершини w рівним мінімуму величини f(w, v) та резерву вершини v. Встановити попередника вершини w в v та додати w в M.

5. Якщо t помічена, то використовуючи попередні вершини повернутись до вершини s та для кожного ребра ланцюга додати резерв вершини t до потоку кожного правильно орієнтованого ребра, і відняти резерв t з потоку кожного неправильно орієнтованого ребра. Повернутись до кроку 1.

6. Повернутись до кроку 2.

Доведення коректності алгоритму. Нехай S – множина всіх вершин, які були помічені під час останнього проходу алгоритму, та T = V\S. Множина S не порожня, адже sS. Якщо e – ребро з S в T, наприклад, e = (u, v), таке що v не помічено, то f(e) = c(e), так як інакше v могла бути помічена. Якщо e – ребро з T в S, наприклад, e = (v, u), так що v не помічена, то f(e) = 0, так як в протилежному випадку v могла бути помічена. Відповідно до наслідків теореми 35.2 потік f – максимальний, а (S, T) – мінімальний розріз. ►

Розглянемо приклад роботи алгоритму для мережі, яка зображена на рис. 35.4, а. На кроці 1 для кожної вершини встановлюємо невизначеними попередників та резерв; для вершини s резерв – , та вважаємо M = {s}. Після чого отримуємо мережу, яка представлена на рис. 35.4, б.

На кроці 2 перевіряємо чи не порожня множина M та обираємо з неї вершину s. На кроці 3 встановлюємо резерв для b рівним min(7, ) = 7, та встановлюємо в якості попередньої вершини для b вершину s. Додаємо вершину b до множини M. Також встановлюємо резерв для d рівним min(6, ) = 6 та попередню вершину для d – вершину s. Додаємо d до множини M. Пропускаємо кроки 4 та 5 і повертаємось на крок 2.

а	б
в	г
д	е

Рис. 35.4.

Перевіряємо, чи не порожня M, та обираємо з неї вершину, наприклад, b. Тепер множина M містить тільки вершину d. На кроці 3 встановлюємо резерв вершини c рівним min(3, 7) = 3 та встановлюємо вершину b як попередню для c. Додаємо c у M, так що M = {c, d}. Знову кроки 4 та 5 пропускаються та переходимо до кроку 2.

Тепер обираємо з M вершину c. Множина M знову містить тільки вершину d. На кроці 3 встановлюємо резерв для t рівним min(3, 5) = 3 та встановлюємо вершину c як попередню для t. Не додаємо t до M. На кроці 4 слід помітити вершину d, але вона вже помічена.

---

На кроці 5 бачимо, що вершина t вже помічена, і використовуючи попередні вершини знаходимо ланцюг:

.

Додаємо 3 (резерв вершини t) до потоку кожного ребра, отримаємо

що дає мережу, яка зображена на рис. 35.4, в.

Тепер повертаємось до кроку 1, де наново ініціалізуємо мітки та попередні вершини та встановлюємо M = {s}. На кроці 2 обираємо вершину s з множини M. На кроці 3 встановлюємо резерв для b рівним min(, 7–3) = 4 та встановлюємо попередника для b вершину s; додаємо вершину b до M. Встановлюємо резерв для d також рівним 6, встановлюємо s як попередника для d та додаємо d до M. Кроки 4 та 5 не застосовуємо, тому повертаємось до кроку 2. Обираємо b з множини M. Оскільки потік з b в c рівний пропускній спроможності з b в c, то вершину c не помічаємо. Обираємо d з множини M та продовжуємо процес, після чого маємо ланцюг

і додаючи 2 (резерв вершини t) до потоку кожного ребра отримаємо ланцюг

.

Поточна ситуація зображена на рис. 35.4, г.

Знову повертаємось до кроку 1 та повторюємо процес, поки не отримаємо ланцюг

.

Додаючи 2 (резерв вершини t) до потоку кожного ребра, отримаємо:

.

Ситуація зображена на рис. 35.4, д.

Повертаючи до кроку 1, перевстановлюємо мітки попередників та встановлюємо M = {s}. На кроці 2 обираємо вершину s з множини M. Як і раніше, на кроці 3 встановлюємо резерв для b рівним 4 та в якості попередника для b вершину s. Додаємо b до множини M. Встановлюємо також резерв для d рівним 6–4 = 2 та додаємо d до M. Повертаємось до кроку 2. Обираємо вершину b з множини M. Оскільки потік з b до вершини c рівний пропускній спроможності з b в c, то помітити c неможна, тому, зрештою, повертаємось до кроку 2. Обираємо вершину d з множини M. Оскільки потік з вершини d у вершину c та вершину t рівний їх пропускним спроможностям, то неможна помітити c та t. Знову повертаємось на крок 2, але множина M вже порожня. Отже, процес закінчено і кінцевий потік зображено на рис. 35.4, е.

---

Смотрите также файлы

• 37_Gramatiki.doc

• 38_Skinchenni_avtomati.doc

• dinamika.docx

• dinamika_1.docx

• komivoyazhera.docx