Материал: 62_201
Класичною задачею, яка розв'язується за допомогою побу дови максимального паросполучення на дводольних графах, є задача про шлюби. Вона відома у такому формулюванні. Нехай є N хлопців та М дівчат, які готові взяти шлюб. Відомо, яким хлопцям які дівчата більше до вподоби, а також, з якими хлоп цями які дівчата хотіли б побратися. Необхідно визначити максимально можливу кількість майбутніх весіль.
Побудова максимального паросполучення у дводольному графі
Сформульовану задачу можна звести до побудови максималь ного потоку в мережі. Для цього необхідно зробити лише кілька підготовчих дій. По-перше, введемо орієнтацію ребер, спрямував ши їх від вершин першої групи до вершин другої. По-друге, наван тажимо всі ребра одиничною «вагою». По-третє, введемо верши- ну-витік, з'єднавши її з усіма вершинам першої групи, і вершинустік, з якою з'єднаємо всі вершини другої групи. Всім цим додат ковим ребрам також надамо одиничної «ваги» (мал. 98, а).
На малюнку 98, б продемонстровано 4 ітерації, які необхід но виконати, щоб побудувати всі можливі доповнюючі шляхи у мережі. У кожній ітерації темним кольором виділено верши ни, ребра яких утворюють доповнюючий шлях. Оскільки для побудови максимального паросполучення не можна двічі вико ристовувати вершини, які уже увійшли до паросполучення, то будемо запам'ятовувати їх у множині.
Мал. 98
У результаті виконання алгоритму Форда-Фалкерсона для побудованої мережі (мал. 98, а) отримаємо максимальний по тік, зображений на малюнку 99, а. Як бачимо, отримано ще
155
Мал. 99
один розв'язок поставленої задачі для заданого графа (1,8), (2,6), (4,9), (5,7) і він також відповідає умові існування макси мального паросполучення (мал. 99, б).
Слід зазначити, що будь-який новий доповнюючий шлях, знай дений у мережі, буде містити лише три ребра, з яких одне середнє і є новим шуканим ребром максимального паросполучення, що бу дується, а перше і останнє - це ті ребра, які введені фіктивно.
До речі, значення максимального потоку в нашому прикладі дорівнює 4. Однак задача про побудову максимального паро сполучення не вимагає цього результату, оскільки заданий граф незважений.
Дещо змінюється поняття перерозподілу потоку у вершинах графа і тлумачиться наступним чином. Оскільки ми або вклю чаємо ребро до паросполучення, або ж ні, то у випадку тупико вої ситуації (у разі спроби включення нового ребра до пароспо лучення) необхідно ребро, яке заважає цьому, виключити із розгляду, тобто врахувати відповідне йому зворотне ребро.
При визначенні можливості використання поточного ребра не враховується можливість його донасичення, тобто нас не цікавитиме питання, чи є ще резерв у даного ребра. При побу дові максимального паросполучення необхідно буде лише ви значати, чи поточне ребро (і, j) ще не увійшло до паросполучен ня С[і, j] - F[i, j] > 0. У разі позитивної відповіді його необхідно буде включити до паросполучення, збільшивши поточне зна чення на 1 inc(F[i, j]), і перерахувати значення відповідного зворотного ребра F\J, і] := -F[i, j].
Проаналізуємо кілька цікавих фактів, які стосуються особ ливостей алгоритму побудови максимального паросполучення.
Чому поточне значення елемента масиву F завжди збіль шується на 1? Тому що саме така кількість потоку може при йти до стокової вершини у дводольному графі, який складаєть ся лише з одиничних ребер.
Уточнимо випадок утворення тупикової ситуації під час по будови максимального паросполучення у дводольному графі.
156
Для цього розглянемо конкретний приклад (мал. 100, а). На перших двох ітераціях до паросполучення будуть включені реб ра (1,5) і (2,4). При побудові наступного доповнюючого шляху, що проходить через вершину 3, тупик утвориться у вершині 5, оскільки вона вже увійшла до паросполучення (мал. 100, б). Щоб вийти із ситуації, необхідно вилучити ребро (1,5) і замість нього включити ребро (3,5). На наступній ітерації буде знайдено новий доповнюючий шлях, куди увійде ребро (1,6) (мал. 100, в). Таким чином буде побудовано максимальне паросполучення для заданого дводольного графа.
Мал. 100
Тепер можна пояснити, чому при включенні зворотного ребра до паросполучення ми фактично при цьому виключаємо відпо відне йому пряме ребро. Це відбувається тому, що при почат ковому значенні F[i, /] = -1 після виконання операції inc(-F[i, /']) воно перетвориться на F[i, /] = 0. Тобто зворотне ребро виключи ться із розгляду. А після виконання операції F\j, і] := -F[i, j] із розгляду буде виключене і відповідне йому пряме ребро. Таким чином і буде здійснено вихід із тупикової ситуації.
Перейдемо до реалізації описаного алгоритму у вигляді програми і зупинимося на деяких змінних, що використовува тимуться у ній і набудуть деяких модифікацій.
Оскільки немає необхідності у зберіганні поточного значен ня насиченості кожного ребра мережі, то масивом Ibl можна знехтувати, а в масиві q будемо зберігати як номер поточної вершини, яку дописано у чергу, так і номер її вершини-предка.
Оскільки вершини, які вже увійшли до паросполучення, ви бувають із подальшого перегляду, то необхідно ввести ще одну множину для зберігання їх номерів. Отже, множина st_q місти тиме номери вершин, які розглядаються при поточному пошу ку в ширину, a st - номери вершин, які уже увійшли до резуль туючого паросполучення.
Зазначені змінні можуть бути описані так:
с, f: array[0..100, 0..100] of byte; q: array[ 1.. 100] of record
top, prev: byte; end;
st_q, st: set of byte;
157
Враховуючи все вищезазначене, можна запропонувати та кий варіант алгоритму побудови максимального паросполучення у вигляді процедури:
procedure matching; begin
while (head < tail) and not flag do begin
v := 0; |
{Починається перегляд з фіктивної вершини з номером 0.} |
|||||
|
|
|
|
{Поки не досягнута фіктивна вершина} |
||
while (v |
<= n |
+1) |
and |
not |
flag do |
{з номером n + 1,} |
begin |
|
|
|
|
|
|
U := q[head].top; |
{фіксується вершина, що є початком поточного ребра.} |
|||||
if ( c [ u , v] - f [ u , v] > 0) and not (v in st_q) then |
{Якщо це ребро ще} |
|||||
|
|
|
{не розглядалося у поточному перегляді, то} |
|||
begin |
|
|
|
|
|
{фіксується вершина,} |
q[tail].top := v; q[tail].prev := head; |
{що є кінцем цього ребра,} |
|||||
St_q := S t q + [v]; |
{запам'ятовується ця вершина як «побачена»;} |
|||||
inc(tail); |
|
|
|
{збільшується «хвіст» черги.} |
||
if v= n + 1 then flag := true; |
{У разі досягнення вершини n + 1,} |
|||||
end; |
|
|
|
|
|
{цей факт фіксується.} |
inc(v) |
{Перехід до наступної вершини, яка може бути початком ребра.} |
|||||
end; |
|
|
|
|
|
|
if not flag then inc(head) |
{Якщо пошук не завершено, то відбувається} |
|||||
end; |
|
|
{перехід до наступної вершини з «голови» черги.} |
|||
end;
Процедура перегляду масиву F з метою корекції його значень може бути такою:
procedure flows; begin
k := tail - 1; {Визначається кінець доповнюючого шляху, що містить нове ребро.}
while q[k].prev О 0 do |
|
{Поки існує доповнюючий шлях,} |
begin |
|
{фіксується початок} |
u := q[q[k] . prev] . top; v := q [ k ] . t o p ; |
{і кінець поточного ребра,} |
|
inc(f[u,v], 1);f[v, u] : = - f [ u , v]; {наявність нового ребра фіксується у масиві F,} |
||
St := st + [v]; |
{нова вершина запам'ятовується у множині st,} |
|
k := q[k].prev; |
{здійснюється перехід до попередньої вершини} |
|
end; |
|
{у доповнюючому шляху.} |
St := St - [n + 1 ] |
{Вилучається фіктивна вершина з номером п + 1.} |
|
end; |
|
|
Тіло основної програми також набуде деяких змін: |
||
|
{Підготовка масивів С і Fз урахуванням} |
|
for І := 0 to П + 1 do |
|
{фіктивних вершин і ребер.} |
for j := 0 to n + 1 do |
|
|
begin |
|
|
| c [ i , j ] : = 0 ; f [ i , j ] : = 0 ; end;
158
for І := 1 to ID do |
{Перегляд ребер мережі.} |
|
begin |
|
|
read(f_in, U, v); C[U, v] := 1; |
{Введення інформації про ребра мережі.} |
|
с [ 0 , U] := 1; c[v, n + 1] := 1; |
{Введення фіктивних ребер.} |
|
end; |
|
|
St := [ ] ; |
{Підготовка множини для фіксації вершин, що належать ребрам} |
|
repeat |
|
{максимального паросполучення.} |
q [ 1 ] . t o p := 0; q[1].prev := 0; |
{Перший елемент черги - фіктивна вершина 0,} |
|
head := 1; tail := 2; |
{що не має предка.} |
|
St_q :== [ 0 ] ; |
{Фіксація першої вершини доповнюючого шляху у множині.} |
|
flag := false; |
|
|
marking; |
{Звернення до процедури визначення доповнюючого шляху.} |
|
if flag then flows; |
{Якщо доповнюючий шлях знайдено, то перехід} |
|
until not flag; |
|
{до перегляду масиву F.} |
Оскільки нас не цікавлять ребра, що виходять із фіктивної вершини 0 і входять до фіктивної вершини п + 1, то виведення отриманого результату буде таким:
for І := 1 to П do |
{Виведення номерів вершин,} |
for j := 1 to n do |
{що належать ребрам} |
'f f [ i . j] > 0 then writeln(f_OUt, І, ' ', j); |
{максимального паросполучення.} |
Аналіз оцінки ефективності роботи алгоритму побудови мак симального паросполучення у дводольному графі із застосуван ням алгоритму побудови максимального потоку є таким. Оскіль ки у даному випадку відсутній варіант перерозподілу потоку у вершинах, то оцінка кількості ітерацій буде залежати тільки від кількості ребер, які по одному будуть виключатися із дводольно го графа і включатися до максимального паросполучення. Однак таких ребер буде не т, оскільки далеко не всі ребра входять до шуканого максимального паросполучення. Кількість ребер у максимальному паросполученні дорівнює кількості вершин у меншій з двох груп вершин дводольного графа. Тому і поточна оцінка кількості ітерацій залежить тільки від кількості вершин, а саме 0(п). Оскільки оцінка пошуку в ширину на кожній іте рації залишається тією самою, що і в алгоритмі Форда-Фалкер- сона 0(т), то загальна оцінка методу становитиме 0(пт).
Стосовно тестування алгоритму побудови максимального паросполучення слід зазначити, що обов'язковим є підбір тес тів як малих, так і середніх та великих. При цьому необхідно передбачити три варіанти: кількість вершин в обох групах приблизно однакова; кількість вершин у групі, що з'єднана з фіктивною вершиною-витоком, значно більша за кількість вер шин у групі, що з'єднана з вершиною-стоком; кількість вер шин у групі, що з'єднана з фіктивною вершиною-витоком, значно менша за кількість вершин у групі, що з'єднана з вер шиною-стоком .
159