Материал: 62_201
|
|
|
{Поки не знайдено вершини,} |
while (v <= n) and not flag do |
{для якої існує ребро (и, v),} |
||
begin |
|
|
|
U := q [ h e a d ] ; |
{визначаємо вершину u, якає «головою» черги.} |
||
if (cfu, v] - f[u, v] > 0) and not (v in st) №еп{Якщо існує резерв потоку} |
|||
begin |
|
{на ребрі (и, v) і вершина v ще не переглядалася,} |
|
q[tail] |
:= v; |
|
{то записуємо її у «хвіст» черги;} |
St := St + [v]; |
{запам'ятовуємо її як «побачену» у множині;} |
||
lbl[tail].prev := head; {створюємо для неї мітку: номер вершини-предка,} |
|||
|
|
{значення оптимального потоку ребром (и, У);} |
|
lbl[tail].flow := min(lbl[head].flow, c[u, v] - f[u, v]); |
|||
inc(tail); |
|
{збільшуємо значення «хвоста» черги.} |
|
if v = t then flag := true; {Фіксуємо ознаку досягнення вершини-стоку.} |
|||
end; |
|
|
|
inc(v) |
{Переходимо до наступного елемента v рядка и в масиві С.} |
||
end; |
|
|
|
if not flag then inc(head) |
|
{Якщо вершина-стік не досягнута,} |
|
end; |
|
|
{то збільшуємо «голову» черги.} |
|
|
|
{Передаємо в основну програму} |
n e w f l o w := lbl[tail - 1].flow; |
|
{значення потоку у вершині г.} |
|
end;
Для зміни значень прямих ребер, що визначають їх наси ченість, можна скористатися такою процедурою:
procedure flows; begin
|
{Визначаємо порядковий номер вершини f у побудованому} |
|||
k := tail - 1; |
|
|
|
{доповнюючому шляху.} |
while lbl[k].prev О 0 do |
{Поки не повернемося до вершини s, для якої} |
|||
begin |
|
|
|
{немає вершини-предка,} |
u := q[lbl[k] . prev]; v := q [ k ] ; |
{визначаємо вершини ребра (и, v);} |
|||
|
|
|
|
{збільшуємо значення потоку} |
inc(f[u, v], Iblftail - 1].flow); |
{у ребрі (и, v) на величину потоку у вершині г;} |
|||
f[v, u] := - f [ u , v ] ; |
{запам'ятовуємо значення для зворотного ребра (v, и);} |
|||
k := lbl[k].prev; |
{значення номера вершини и стає номером вершини v) |
|||
end; |
{для перегляду наступного ребра визначеного доповнюючого шляху.} |
|||
end;
Для коректної роботи основного блоку програми необхідно зробити такі початкові призначення:
for і := 1 to П do {Задання початкових нульових значень для масивів С і F.} for j := 1 to n do
begin
| c [ i , j ] : = 0 ; f [ i , j ] : = 0 ; end;
for І := 1 |
to m do |
{Читання з вхідного файлу} |
begin |
|
|
read(f_in, u, v, d); |
{інформації про ребра мережі} |
|
c [ u , v] := d; |
{і внесення її у масив С.) |
|
end; |
|
|
flow := 0; |
|
{Початкове значення максимального потоку.} |
150
Основний блок програми може виглядати так:
repeat |
|
{Початковий стан черги q |
q[1] := s; lbl[1].prev := 0; lbl[1].flow := maxint; |
{та масиву міток/fo/.} |
|
head := 1; tail := 2; |
{Початковий стан «голови» і «хвоста» черги.} |
|
|
{Початковий стан множини розглянутих вершин:} |
|
St := [ s ] ; |
{починаємо з вершини-витоку.} |
|
flag := false; |
|
|
marking(torrent); |
{Перехід до процедури побудови доповнюючого шляху.} |
|
if flag then |
{Якщо доповнюючий шлях побудовано, то} |
|
b e g i n |
{збільшуємо значення максимального потоку} |
|
inc(flow, torrent); |
{на значення потоку доповнюючого шляху.} |
|
flows; |
{Перехід до процедури перерахунку значення потоку} |
|
end |
{на кожному ребрі побудованого доповнюючого шляху.} |
|
Until not flag; |
{Завершення побудови максимального потоку.} |
|
Отримані результати можуть бути виведені такою послідов |
||
ністю операторів: |
|
|
writeln(fout, flow); |
{Виведення значення максимального потоку.} |
|
for І := 1 to n do |
{Виведення значень елементів масиву F,} |
|
for j := 1 to П do {які мають додатне значення, що відповідає ребрам мережі,} |
||
if f [ i , j] > 0 t h e n Writeln(f_OUt, І, ' ', j, ' ', f [ l , j])! |
{ЯКИМИ ПРОХОДИВ ПОТІК.} |
|
Цікавою може виявитися ситуація, коли необхідно побудувати максимальний потік у мережі з кількома витоками і стоками (мал. 96, а). Як бути у цьому разі? Виявляється, проблем немає: до сить додати до мережі одну вершину-витік і ребра, які з'єднують її з усіма заданими витоками, і вершину-стік, в яку входитимуть ребра з усіх заданих вершин-стоків. «Вага» нових введених до ме режі ребер повинна дорівнювати оо (мал. 96, б). Далі лишається
тільки застосувати вже відомий алгоритм Форда-Фалкерсона. |
||||
,15^" Y ^ 8 |
|
,~ |
^ Д 5 *А" ї "8 |
|
|
||||
®с |
^® |
лх; |
¥&\ |
|
а) |
5 ^4D «) |
~ ^ |
Мал. 96
Визначимо оцінку алгоритму Форда-Фалкерсона. За наши ми позначеннями п - кількість вершин мережі, am - кількість її ребер. Визначимо спочатку, якою буде оцінка кількості іте рацій. Основна суть методу полягає у виключенні насичених
151
ребер. Нехай на кожній ітерації, тобто під час кожного прохо дження мережі від вершини-витоку до вершини-стоку, виклю чається тільки одне ребро. Тоді таких переглядів буде стільки само, скільки і ребер у мережі. Тому оцінку на цьому етапі мож на визначити як 0(т). Чи може виключене ребро знову включи тися до перегляду? Так, і це може відбутися у разі, коли в одній з вершин, що йому належать, буде розподілено потік. Оскільки така ситуація може виникнути у кожній з я вершин мережі, то загальна оцінка кількості ітерацій становить 0(пт).
У свою чергу, на кожній ітерації виконується пошук у ши рину і перерахунок значень потоку на ребрах, що увійшли до доповнюючого шляху. А це вимагає у найгіршому випадку пе регляду всіх ребер, тому потребує 0(т) часу. Звідси загальна оцінка методу визначається як 0(пт2).
Щодо тестування алгоритму Форда-Фалкерсона, то слід зазначити, що при доборі тестів необхідно розглядати як ме режі з одним витоком і стоком, так і з кількома. При цьому оцінка роботи алгоритму за часом не зміниться, оскільки кіль кість вершин збільшується лише на дві.
Корисним є розгляд як невеликих мереж, так і мереж з до статньо великою кількістю вершин і ребер. Однак створення таких тестів вимагає розробки спеціальних програм, які врахо вували б усі особливості графів, які можна назвати мережами. Для спрощення задачі по генерації таких тестів можна запро понувати варіант з'єднання невеликих мереж в одну послідов но одна за одною або паралельно з додаванням вершини-витоку і вершини-стоку. Такі мережі можуть бути цікавими для дослідження і порівняння отриманих результатів. Це дасть змогу провести аналітичний аналіз роботи алгоритму побудови максимального потоку в мережі.
Серед тестів обов'язково повинні бути і такі, що вимагають перерозподілу потоку в одній або кількох вершинах. Такі тести, що описують невеликі мережі, найчастіше створюються вручну, а потім можуть бути скомпоновані повторенням у великі мережі.
Завдання
1.Розробити та реалізувати у вигляді програми алгоритм ви значення максимального потоку в заданій мережі.
2.Виконати завдання 1 для мережі з кількістю верпіин N ^ 6,
вякій відсутній перерозподіл потоку з використанням зво ротних ребер, визначивши кількість необхідних для одер жання результату ітерацій. Результат виконання програми вивести у файл.
3.Виконати завдання 1 для мережі з кількістю вершин N К 6,
вякій існує необхідність перерозподілу потоку з викорис-
152
танням зворотних ребер, визначивши кількість необхідних для одержання результату ітерацій. Результат виконання програми вивести у файл.
4. Виконати завдання 1 для мережі, яка є незв'язним графом, з кількістю вершин N^6, визначивши кількість необхідних для одержання результату ітерацій. Результат виконання програми вивести у файл.
5.Виконати завдання 1 для мережі з кількістю вершин N > 6, в якій відсутній перерозподіл потоку з використанням зворотних ребер, визначивши кількість необхідних для одержання резуль тату ітерацій. Результат виконання програми вивести у файл.
6.Виконати завдання 1 для мережі з кількістю вершин N > 6,
вякій існує необхідність перерозподілу потоку з викорис танням зворотних ребер, визначивши кількість необхідних для одержання результату ітерацій. Результат виконання програми вивести у файл.
7.Виконати порівняльний аналіз виконання завдань 2-6 щодо ефективності роботи алгоритму Форда-Фалкерсона.
/Запитання для самоконтролю
1.Які графи можна назвати мережами?
2.Якими властивостями визначається потік у мережі?
3.Як формулюється задача про максимальний потік у мережі?
4.Які задачі на графах можна віднести до потокових?
5.На якій методиці базується алгоритм Форда-Фалкерсона?
6.Як формулюється задача побудови максимального потоку в ме режі у термінах графів?
7.Що розуміють під розрізом мережі? Поясніть це поняття на конк ретному прикладі.
8.Як визначається пропускна спроможність розрізу?
9.Що розуміють під мінімальним розрізом мережі?
10.Як пов'язані між собою мінімальний розріз мережі і максималь ний потік у ній?
11.Як можна визначити мінімальний розріз мережі і значення мак симального потоку?
12.Яким є метод Форда-Фалкерсона для побудови максимального потоку в мережі?
13.У чому полягає суть ітераційного підходу до побудови алгоритму за методом Форда-Фалкерсона?
14.Які вхідні дані необхідні для виконання алгоритму Форда-Фал керсона?
15.Який відомий пошуковий алгоритм використовується в методі Форда-Фалкерсона?
16.Запропонуйте власний приклад мережі і продемонструйте на ньому роботу алгоритму методу Форда-Фалкерсона побудови максимального потоку.
17.У чому полягає ідея методу Форда-Фалкерсона побудови мак симального потоку щодо перерозподілу потоку у вершині? Про демонструйте це на власному прикладі.
153
18.Які ребра у мережі називаються прямими, а які - зворотними?
19.Якою є ознака завершення алгоритму Форда-Фалкерсона побу дови максимального потоку?
20.Сформулюйте алгоритм побудови максимального потоку в ме режі, що базується на методі Форда-Фалкерсона.
21. Як виглядає реалізація алгоритму побудови максимального пото ку в мережі за методом Форда-Фалкерсона у вигляді програми?
22.Як у програмі реалізується ідея введення зворотних ребер та їх обробка?
23.Як можна визначити максимальний потік у мережі для задачі з кількома витоками і стоками?
Ш24. Якою є оцінка методу Форда-Фалкерсона для побудови макси мального потоку в мережі? Обґрунтуйте свою відповідь.
Дводольні графи
Продовжуючи тему графів, не можна залишити поза увагою ще один їх різновид - це дводольні графи.
b Дводольним графом називається такий неорієнтований і • граф, у якому всі вершини можна розбити на дві групи, вер
шини кожної з яких з'єднані ребрами лише з вершинами протилежної групи.
На малюнку 97, а зображено дводольний граф, до першої групи вершин якого входять вершини 1, 2,3,4, 5, а до другої - 6,7,8,9.
Паросполученням у дводольному графі називається мно жина ребер, що не мають спільних вершин. На малюнку 97, б жирними лініями виділено ребра, які утворюють саме таке паросполучення. Причому в даному разі - це є максимальне паросполучення, оскільки більше ребер, що не порушують паросполучення, визначити у заданому графі неможливо.
Максимальним паросполученням називається таке паросполучення, яке містить максимально можливу кількість ребер.
Слід, однак, зазначити, що наведене на малюнку 97, бпаросполучення не єдине. Наприклад, ребро (2,7) можна замінити ребром (5,7) і при цьому ознаки паросполучення не будуть порушені.
|
@ \ . \Г\0 |
2л*^ |
Г > 7 ) |
|
®z/&® |
3)гУ |
Із® |
а) |
^ ® |
б) ' |
—^® |
|
3/— |
||
|
®— |
||
Мал. 97
154