Алгоритмы поиска максимального потока

s              1,0       1,1              t

3,2                           1,1

y

Рис.2.3

Перш  ніж  довести  теорему  2.3, проілюструємо її  на  одному  прикладі. Розглянемо  мережу,  зображену на  рис.2.2, з функцією  пропускної  спроможності    і потоком , вказаними на  рис. 2.3, де    це  перше,   а друге з чисел, написаних поряд з кожною  дугою . Величина  потоку  тут рівна 3. Оскільки  розріз, що складається з дуг ,   і , також має пропускну спроможність  3, з леми  2.2  виходить, що  цей потік - максимальний, а розріз – мінімальний.

Доведення  Через  лему  2.2  достатньо показати, що  існують потік   і розріз  , для яких  величина  потоку  і пропускна спроможність  розрізу рівні. Ми  це  зробимо, узявши  максимальний  потік   (очевидно, такий існує)  і визначивши  з його  допомогою розріз  , для якого

 

 

  і, таким  чином, в  силу  (2.15), потрібна  рівність    матиме  місце.

Отже, нехай  максимальний  потік. Користуючись  , визначимо множину   рекурентно  таким чином:

2. Якщо    і то 

 Якщо    і  то 

 Ми  стверджуємо, що  . Насправді, допустимо, що  існує шлях  з   у , скажемо  що володіє властивістю, що  для всіх  прямих  дуг   цього шляху а для всіх  його  зворотних дуг –

Нехай  мінімум різниці , узятий  по  всіх  прямим  дугам цього шляху, а мінімум , узятий  по  всіх  його  зворотних дугах, і нехай . Змінимо тепер потік   таким чином: збільшимо   на  ε на  всіх  прямих  дугах і зменшимо    на  ε на  всіх  зворотних дугах нашого  шляху. Легко перевірити, що  така  певна нова  функція є потоком з   у , що має величину  . Але тоді  потік     не був максимальним  в суперечності  з нашим припущенням і, значить, .

Таким чином, множина    це  розріз, що відділяє    і . Крім того, з визначення  множини виходить, що для

   для оскільки  інакше  вузол    входив би у  . Тому   так що  в (2.15)  має місце рівність.

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

Наслідок  2.4 Потік    є максимальним  в тому  і лише  в тому випадку, якщо  немає жодного шляху, що збільшує  потік .[2]

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

Наслідок  2.5  Розріз    мінімальний в тому  і лише  в тому випадку, якщо  кожен максимальний  потік   насичує всі дуги  розрізу   і залишає вільними  всі дуги, що належать  .[2]

Наслідок  2.6 Нехай   і мінімальні  розрізи. Тоді і

  і   мінімальні  розрізи.

Наступна  теорема  показує, що  мінімальний  розріз  , побудований в доведенні теореми 2.3, насправді    не залежить  від максимального потоку  .

Теорема  2.7 Нехай    довільний мінімальний розріз, деякий  максимальний  потік і мінімальний розріз, визначений  по  потоку    в доведенні теореми 2.3. Тоді  .[2]

Теорема  2.8.  Нехай  множина вузлів, визначена в доведенні теореми 2.3, множина, визначена вище, і припустимо, що  функція пропускної  спроможності  із  строго  позитивна. Тоді  мінімальний розріз    єдиний  в тому  і лише  тому  випадку, якщо  .[6]

Із  задачею  про  максимальний  потік  тісно  пов’язана  задача  про  мінімальний  розріз  мережі. Наведемо  формулювання  цих  задач.

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

                          (2.16)

Задача  про  максимальний  потік  полягає  у  знаходженні  максимального  значення  інтенсивності  d, при  якому  в  розглядуваній  мережі  існує  потік. Потік  , що  відповідає  максимальному значенню    інтенсивності, називається максимальним  потоком, а величиною цього потоку.

Розглянемо  описану  вище  мережу. Розрізом  мережі, що  відокремлює  s від  t, називається  множина  дуг  , де  деяка множина вершин    мережі, така, що  . Нагадаємо, що  пропускна спроможність  цього розрізу визначається  звичайним чином:  .

Приклад  2.1  Розглянемо мережу, зображену на рис. 2.3, де вершина  1  є  джерелом, а  вершина  6 стоком. Нехай , тоді  розріз, який  відокремлює вершину 1  від вершини 6, що  відповідає  вибраній  множині С. Пропускна спроможність  цього розрізу .

                                              2                       5                       4                        

3 6

1 4  2 3 6

2

c 2

3 1 5

Рис. 2.3

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

Для  розв’язання  задачі  про  максимальний  потік  Фордом  та  Фалкерсоном  був  розроблений  метод, що  носить  їх  ім’я.

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

Алгоритм  Форда розпочинає  роботу  з  будь-якого  допустимого  потоку  (зокрема нульового)  величини  . Для  цього  визначається  множина  . Якщо  , то  потік   є максимальним, в іншому  випадку можна знайти    та  новий потік   величини  . Для нового  потоку  цей цикл  операцій  повторюється  і т.д.

Процеси  визначення    та    об’єднуються  в один  процес  «розставлення позначок» вершин. Позначка  μ(i)  довільної вершини і складається з двох  чисел та  . Ці  числа означають, що  вздовж  деякого ланцюга, останнім  ребром  якого є , можна додатково доставити , одиниць потоку  з вершини s  до  вершини i.

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

Дамо  детальний  виклад  алгоритму, вважаючи, що  відомий  допустимий  потік  х (зокрема  нульовий).

Крок 1 (процес  розставлення  позначок). На цьому кроці кожна з вершин  належить  до  одного  з трьох типів:

• Непозначена,
• Позначена  і  непроглянута,
• Позначена  і  проглянута.

Спочатку  всі  вершини  непозначені. Позначимо  вершину  s  позначкою  , що  означає: можна послати потік з вершини s  у саму  себе  необмеженої  величини. Тепер  вершина  s  позначена  і  непроглянута.

Взагалі, нехай  позначена і непроглянута  вершина ,  або її  позначка. Розглядаємо ще  непозначені вершини     k:I  . Кожній  з таких вершин  приписуємо  позначку  , де  . Розглядаємо ще  непозначені вершини   , i. Кожна з таких вершин  одержує позначку  , де  . Всі вершини k, які одержали  позначки, тепер позначені і непроглянуті, а вершина позначена і проглянута. Продовжуємо приписувати позначки  непозначеним  вершинам  до  тих пір, поки  або вершина t  виявиться позначеною, або не  можна буде  позначити жодної   вершини і вершина t  виявиться непозначеною. У другому випадку існуючий  потік максимальний, а множина позначених  вершин    визначає  мінімальний розріз  мережі. У першому випадку існуючий  потік х на  кроці 2  можна збільшити.

Крок 2 (збільшення  потоку). Нехай  , або позначка  вершини t. Це  означає, що  існуючий  потік з s  в t  можна збільшити на  величину  . Для цього в першому випадку змінюємо    на  , у другому -   змінюємо  на  . Переходимо  до  вершини k  і виконуємо аналогічні  операціїї, змінюючи  величину  потоку  на  ту  ж величину  . Продовжуємо ці  дії, поки  не  досягнемо вершини s. Після цього ліквідовуємо  позначки  всіх  вершин  і переходимо  до  кроку 1.

Приклад 2.2 Знайти  максимальний  потік  з  вершини  1  у  вершину  8  на  мережі, зображеній  на  рис.2.5.

Рис.2.5

Процес  розв’язання  задачі  продовжується на  рисунках  2.6-2.7.

Рис. 2.6

Рис. 2.7

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

 

2.2.2  Алгоритм Едмондса – Карпа 

Алгоритм є частковим випадком алгоритму Форда-Фалкерсона, на кожному кроці вибирають найкоротший доповнюючий шлях з s в t в  кінцевій мережі (думаючи, що кожне ребро має одиничну). Найкоротший шлях знаходиться пошуком в ширину. Алгоритм працює за час O(VE²).

Крок 0. Ставимо всі потоки рівні нулеві. Кінцева мережа спочатку співпадає з початковою.

Крок 1. В  кінцевій мережі знаходимо найкоротший  шлях з джерела в сток. Якщо такого шляху немає, то зупиняємось.

Крок 2. Пропускаємо  через знайдений шлях (він називається  ланцюгом збільшення потоку) максимально  допустимий потік:

1. На знайденому шляху в кінцевій мережі шукаємо ребро з мінімальною пропускною здатністю c_min.
2. Для кожного ребра на знайденому шляху збільшуємо потік на c_min, а в протилежному до нього – зменшуємо на c_min.
3. Модифікуємо кінцеву мережу. Для всіх ребер на знайденому шляху, а також на протилежних до них, обчислюємо нову пропускну здатність. Якщо вона стала ненульовою , то добавляємо ребро до кінцевої мережі, а якщо вона нульова, стираємо його.

Повертаємось до кроку 1.

Щоб знайти найкоротший шлях в графі, використовуємо пошук в  ширину:

Крок 0. Створюємо чергу вершин О. Спочатку О складається тільки з вершини s.

Крок 1. Відмітимо вершину s як проглянуту , без предка, а всі інші як не проглянуті.

     Крок 2. Доки черга непуста, виконуємо наступні кроки:

1. Видаляємо першу в черзі вершину u.
2. Для всіх ребер (u, v), що виходять з вершини u, таких що вершина v ще непроглянута, виконуємо наступні шаги:
1. Відмічаємо вершину v як проглянуту, з предком u.
2. Додаємо вершину v в кінець черги.
3. Якщо v=t, виходимо з обох циклів: ми знайшли найкоротший шлях.

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

Крок 4. Якщо ж ні, йдемо від t до s, кожен раз переходячи до предка. Повертаємо шлях в зворотному порядкові.

Приклад 2.4

Нехай задана мережа з джерелом в A і стоком в вершині G. На рис.2.8. парою  f / c позначений потік  по цьому ребру і його пропускна здатність.

Рис.2.8

Пошук в ширину

Опишемо пошук в ширину на першому  кроці.

1. Черга складається з єдиної A. проглянута вершина A. Предка немає.
2. Черга складається (від начала до кінця) з вершини B та D. Проглянуті вершини A,B,D. Вершини B,D мають предка А.
3. Черга складається з вершин D и C. Проглянуті A,B,C,D. Вершини B,D мають предка А, вершина C–предка B.
4. Черга складається з вершин C,E,F. Проглянуті A,B,C,D,E,F. Вершини B,D мають предка А, вершина C – предка B, вершини E,F – предка D.
5. Вершина C видаляється з черги: ребра з неї ведуть тільки в уже проглянуті вершини.
6. Знаходиться ребро (E,G) и цикл зупиняється. В черзі вершини (F,G). Проглянуті всі вершини. Вершини B,D мають предка А, вершина C – предка B, вершини E,F – предка D, вершина G –предка E.
7. Йдемо по предкам: G->E->D->A. Повертаємо  пройдений шлях в зворотньому порядку: А->D->E->G.

Основний алгоритм:

    Пропускна здатність шляху Путь

1.min(c_f(A,D),c_f(D,E),c_f(E,G)) =                                

min(3 − 0,2 − 0,1 − 0) = 
min(3,2,1) = 1

 

 

 

 

2.min(c_f(A,D),c_f(D,F),c_f(F,G)) =

min(3 − 1,6 − 0,9 − 0) = 
min(2,6,9) = 2

 

 

 

 

 

3.min(c_f(A,B),c_f(B,C),c_f(C,D),c_f(D,F),c_f(F,G)) =

min(3 − 0,4 − 0,1 − 0,6 − 2,9 − 2) = 
min(3,4,1,4,7) = 1