Розглянемо задачу визначення максимального потоку між виділеними вузлами зв'язковою мережі. Кожна дуга мережі володіє пропускними здатностями в обох напрямках, які визначають максимальну кількість потоку, що проходить по даній дузі. Орієнтована (одностороння) дуга відповідає нульовий пропускної здатності в забороненому напрямку.
Пропускну здатність Cij мережі можна представити в матричній формі.
Крок 1 :
Знайти мета, яка з'єднує джерело S і стік t. по якій потік приймає позитивне значення. У напрямку S → t. Якщо такої мети не існує, перейти до кроку 3. В іншому випадку перейти до кроку 2.
Нехай () - пропускні спроможності дуг ланцюга (S, t) в напрямку S → t (t → S).
Матрицю пропускних спроможностей C = [Cij] змінити наступним чином:
а) відняти # 1012; з усіх ;
б) додати # 1012; до всіх .
Замінити поточну матрицю С на знову отриману і перейти до кроку 1. Операція (а) дає можливість використовувати залишки пропускних спроможностей дуг вибраного ланцюга в напрямку S → t.
Операція (б) відновлює вихідні пропускні спроможності мережі, тому що зменшення пропускної здатності дуги в одному напрямку можна розглядати як збільшення її пропускної здатності в протилежному напрямку.
Знайти максимальний потік в мережі.
Нехай C = [Cij] - вихідна матриця пропускних спроможностей.
C * = [C * ij] - остання матриця, отримана в результаті модифікації вихідної матриці (крок 1 і 2).
Оптимальний потік Х = [xij] в дугах задається так:
Максимальний потік з S в t дорівнює:
Приклад: визначити максимальний потік в графі
В якості вихідної ланцюга виберемо S → 1 → 4 → t. Тоді осередки (S, 1), (1,4), (4, t) помічаємо знаком (-), а осередки (1, S), (4,1), (t, 4) помічаємо знаком (+).
Максимальний потік для цього ланцюга дорівнює
Можна вибрати різні вихідні ланцюга. Хороший вибір повинен давати найбільше значення # 1012 ;. Але може виникнути багато варіантів таких ланцюгів. При програмуванні ланцюг зручно визначати безпосередньо з матриці С, починаючи з першого рядка S-рядки і вибираючи наступний вузол серед тих, які з'єднані з S позитивним потоком. Далі розглядається рядок, яка відповідає вибраному вузлу, і вибирається наступний вузол, з'єднаний з попереднім позитивної дугою. Процес триває до тих пір. поки не буде досягнутий вузол t.
Коригуємо матрицю С, віднімаючи # 1012; = 5 з усіх елементів, позначених (-), і складаючи з усіма елементами, що мають знак (+). Отримуємо нову матрицю.
Аналогічні дії виробляємо і на наступних ітераціях.
Виберемо ланцюг (S → 3 → 2 → t)
# 1012; = min = 10 Скорегуємо матрицю С
Виберемо ланцюг (S → 1 → 3 → 4 → t)
# 1012; = min = 5 Скорегуємо матрицю С
Виберемо ланцюг (S → 4 → t)
# 1012; = min = 3 Скорегуємо матрицю С
Виберемо ланцюг (S → 3 → t)
# 1012; = min = 2 Скорегуємо матрицю С
Між S і t можна побудувати ланцюг, т.к всі елементи в стовпці t дорівнюють нулю. Таким чином отримаємо матрицю С *
Побудуємо матрицю Х. Негативні елементи в матриці замінимо нулями.
Σ # 1012; = 5 + 10 + 5 + 3 + 2 = 25
Графічно рішення представлено графом:
