2 Метод Форда-Фалкерсона

У будь-якій мережі існує максимальний потік. Величина максимального потоку дорівнює пропускній здатності мінімального розрізу.

Потік, обчислений за допомогою алгоритму Форда-Фалкерсона має максимальну величину, а розріз (X, X), де X-безліч вершин, помічених при останньому помечіваніі, має мінімальну пропускну здатність.

опис алгоритму

Нехай спочатку в мережі мається потік f (припустимо з нульовими значеннями на всіх дугах).

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

1) Процедура помечіванія вершин

2) Процедура зміни потоку

1) Процедура помечіванія вершин.

Обробка i-й вершини з позначкою (x, e) полягає в тому, що з вершини i позначаються суміжні непомеченние вершини за наступним правилом:

- Якщо дуга направлена з i в j і потік по цій дузі (fij) менше пропускної здатності дуги (cij), то вершині j присвоюється мітка (i +, min (e, cij-fij))

- Якщо дуга направлена з j в i і потік по цій дузі (fji) більше нуля, то вершині j присвоюється мітка (i-, min (e, fji))

Ця процедура завжди починається з помечіванія та обробки витоку. Він позначається особливою міткою (-,  ). Потім обробляються інші помічені вершини (після обробки витоку послідом вершини, суміжні з ним) і т. д.

Процес помечіванія закінчується в двох випадках:

1) Жодну вершину більше не можна помітити, але стік НЕ помечен. Це значить, що знайдений потік - максимальний і алгоритм зупиняється.

2) позначаю стік. В цьому випадку проводиться зміна потоку.

2) Процедура зміни потоку.

Якщо стік отримав мітку (k +, d), то потоки будуть змінюватися на величину d таким чином:

- Якщо ми перебуваємо в вершині j з міткою (i +, x), то додаємо d до fij і переходимо в вершину i.

- Якщо ми перебуваємо в вершині j з міткою (i-, x), то віднімаємо d з fij і переходимо в вершину i.

Зміна потоку починається від стоку і триває до досягнення витоку. Після цього всі мітки стираються і заново виконується процедура помечіванія вершин.

Цей процес продовжується до тих пір, поки не буде знайдений максимальний потік (жодну вершину більше не можна помітити, але стік НЕ помечен).

приклад:

Обчислимо максимальний потік для зображеної нижче мережі.

Тут перше число в дужках - пропускна здатність дуги, друге число - потік (в початковий момент беремо потік рівний нулю)

1) Помечіваніе вершин

Исток i отримує мітку (-,  ).

Для суміжній з i Непомічені вершини a1 маємо:

дуга направлена з i в a1, 0 < 7, отже присвоюємо вершині a1 мітку (i +, min (     )) = (i +, 7)

Для суміжній з i Непомічені вершини a2 маємо:

дуга направлена з i в a2, 0 < 6, отже присвоюємо вершині a2 мітку (i +, min (     )) = (i +, 6)

Після обробки вершини i ми позначили ще дві вершини a1 і a2. Подальшу обробку можна починати з будь необробленої поміченої вершини. Розглянемо спочатку вершину a2.

Для суміжній з a2 Непомічені вершини a4 маємо:

дуга направлена з a4 в a2, потік дорівнює нулю, отже мітку вершині a4 НЕ присвоюємо

Для суміжній з a2 Непомічені вершини s маємо:

дуга направлена з a2 в s, 0 < 9, отже присвоюємо вершині s мітку (a2 +, min (6, 9-0)) = (a2 +, 6)

В процесі обробки вершини a2 у нас послідом стік, тому переходимо до процедури зміни потоку. На малюнку зображені помічені вершини.

2) Зміна потоку

Сток отримав мітку (a2 +, 6), отже потоки будуть змінюватися на 6.

Починаємо з стоку:

Ми перебуваємо в вершині s з позначкою (a2 +, 6), отже змінюємо потік з вершини a2 в вершину s. Нове значення потоку 0 + 6 = 6, і переходимо в вершину a2.

Вершина a2 має мітку (i +, 6), отже змінюємо потік з вершини i в вершину a2. Нове значення потоку 0 + 6 = 6, і переходимо в вершину i.

Ми повернулися до витоку => процедура зміни потоків закінчена. Стираємо все мітки і заново виконуємо процедуру помечіванія вершин.

На малюнку зображена мережа, після першого зміни потоків.

3) Помечіваніе вершин

Исток i отримує мітку (-,  ).

Для суміжній з i Непомічені вершини a1 маємо:

дуга направлена з i в a1, 0 < 7, отже присвоюємо вершині a1 мітку (i +, min (     )) = (i +, 7)

Для суміжній з i Непомічені вершини a2 маємо:

дуга направлена з i в a2, 6 = 6, отже вершині a2 позначку не присвоюємо

Переходимо до обробки вершини a1.

Для суміжній з a1 Непомічені вершини a3 маємо:

дуга направлена з a1 в a3, 0 < 6, отже присвоюємо вершині a3 мітку (a1 +, min (7, 6-0) = (a1 +, 6)

Переходимо до обробки вершини a3.

Для суміжній з a3 Непомічені вершини s маємо:

дуга направлена з a3 в s, 0 < 4, отже присвоюємо вершині s мітку (a3 +, min (6, 4-0)) = (a3 +, 4)

В процесі обробки вершини a3 у нас послідом стік, тому переходімк процедурі зміни потоку. На малюнку зображені помічені вершини.

4) Зміна потоку

Сток отримав мітку (a3 +, 4), отже потоки будуть змінюватися на 4.

Починаємо з стоку:

Ми перебуваємо в вершині s з позначкою (a3 +, 4), отже змінюємо потік з вершини a3 в вершину s. Нове значення потоку 0 + 4 = 4 і переходимо в вершину a3.

Вершина a3 має позначку (a1 +, 6), отже змінюємо потік з вершини a1 в вершину a3. Нове значення потоку 0 + 4 = 4 і переходимо в вершину a1.

Вершина a1 має позначку (i +, 7), отже змінюємо потік з вершини i в вершину a1. Нове значення потоку 0 + 4 = 4 і переходимо в вершину i.

На малюнку зображена мережа після другого зміни потоків.

5) Помечіваніе вершин

Исток i отримує мітку (-,  ).

Для суміжній з i Непомічені вершини a1 маємо:

дуга направлена з i в a1, 4 < 7, отже присвоюємо вершині a1 мітку (i +, min (     )) = (i +, 3)

Для суміжній з i Непомічені вершини a2 маємо:

дуга направлена з i в a2, 6 = 6, отже вершині a2 позначку не присвоюємо

Переходимо до обробки вершини a1.

Для суміжній з a1 Непомічені вершини a3 маємо:

дуга направлена з a1 в a3, 4 < 6, отже присвоюємо вершині a3 мітку (a1 +, min (3, 6-4)) = (a1 +, 2)

Переходимо до обробки вершини a3.

Для суміжній з a3 Непомічені вершини s маємо:

дуга направлена з a3 в s, 4 = 4, отже вершині s позначку не присвоюємо

Для суміжній з a3 Непомічені вершини a4 маємо:

дуга направлена з a3 в a4, 0 < 3, отже присвоюємо вершині a4 мітку (a3 +, min (2, 3-0)) = (a3 +, 2)

Переходимо до обробки вершини a4.

Для суміжній з a4 Непомічені вершини a2 маємо:

дуга направлена з a4 в a2, 0 < 2, отже присвоюємо вершині a2 мітку (a4 +, min (2, 2-0)) = (a4 +, 2)

Переходимо до обробки вершини a2.

Для суміжній з a2 Непомічені вершини s маємо:

дуга направлена з a2 в s, 6 < 9, отже присвоюємо вершині s мітку (a2 +, min (2, 9-6)) = (a2 +, 2)

6) Зміна потоку

Сток отримав мітку (a2 +, 2), отже потоки будуть змінюватися на 2.

Починаємо з стоку:

Ми перебуваємо в вершині s з позначкою (a2 +, 2), отже змінюємо потік з вершини a2 в вершину s. Нове значення потоку 6 + 2 = 8 і переходимо в вершину a2.

Вершина a2 має позначку (a4 +, 2), отже змінюємо потік з вершини a4 в вершину a2. Нове значення потоку 0 + 2 = 2 і переходимо в вершину a4.

Вершина a4 має позначку (a3 +, 2), отже змінюємо потік з вершини a3 в вершину a4. Нове значення потоку 0 + 2 = 2 і переходимо в вершину a3.

Вершина a3 має позначку (a1 +, 2), отже змінюємо потік з вершини a1 в вершину a3. Нове значення потоку 4 + 2 = 6 і переходимо в вершину a1.

Вершина a1 має позначку (i +, 3), отже змінюємо потік з вершини i в вершину a1. Нове значення потоку 4 + 2 = 6 і переходимо в вершину i.

Ми повернулися до витоку => процедура зміни потоку закінчена. Стираємо все мітки і заново виконуємо процедуру помечіванія вершин.

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

7) Помечіваніе вершин

Исток i отримує мітку (-,  ).

Для суміжній з i Непомічені вершини a1 маємо:

дуга направлена з i в a1, 6 < 7, отже присвоюємо вершині a1 мітку (i +, min (     )) = (i +, 1)

Для суміжній з i Непомічені вершини a2 маємо:

дуга направлена з i в a2, 6 = 6, отже вершині a2 позначку не присвоюємо

Переходимо до обробки вершини a1.

Для суміжній з a1 Непомічені вершини a3 маємо:

дуга направлена з a1 в a3, 6 = 6, отже вершині a3 позначку не присвоюємо

Тепер у нас оброблені всі помічені вершини, але залишився Непомічені стік.

Це означає, що отриманий потік і є максимальний. При останньому помечіваніі ми позначили вершини i і a1. Область розрізу між поміченими при останньому помечіваніі вершинами і непоміченими має мінімальну пропускну здатність.

⇐ Предыдущая 1 2 3 45