Алгоритм Гопкрофта — Карпа — Вікіпедія
В інформатиці, алгоритм Гопкрофта—Карпа отримує на вході двочастковий граф і видає на виході парування найбільшої потужності – множину, що містить якнайбільше ребер з властивістю, що жодна двійка ребер не має спільної вершини. Виконується за час у найгіршому випадку, де це множина ребер і це множина вершин графа. У випадку насиченого графа часові рамки набувають вигляду , для випадкових графів час виконання майже лінійний.
Алгоритм винайшли Джон Гопкрофт and Річард Карп (1973). Як і в попередніх методах для парування як-от Угорський алгоритм і роботі Едмондс, (1965), алгоритм Гопкрофта—Карпа багаторазово збільшує часткове парування через знаходження шляху розширення. Однак, замість пошуку одного шляху розширення, алгоритм шукає найбільшу множину найкоротших шляхів розширення. У результаті, потрібно лише ітерацій. Цей принцип використовували для розробки складніших алгоритмів для недвочасткового парування з таким самим часом виконання як у алгоритму Гопкрофта—Карпа.
Шляхи розширення[ред. | ред. код]
У висліді маємо нове парування потужність якого на одиницю більша. Вершина, яка не є кінцем жодного ребра в певному частковому паруванні називається вільна вершина. В основі алгоритму лежить поняття шлях розширення, шлях який починається у вільній вершині і закінчується вільною вершиною, також він чергує ребро з парування з ребрами, що не входять до парування. Якщо це парування і це шлях розширення щодо , тоді симетрична різниця двох множин ребер, , буде парування розміру . Отже, знаходженням шляхів доповнення, алгоритм може збільшувати розмір парування.
І навпаки, припустимо, що не оптимальне, і нехай буде симетричною різницею де це оптимальне парування. Тоді, повинен утворювати набір неперетинних шляхів розширення і циклів або шляхів в яких вільні ребра і ребра з парування зустрічаються в однаковій кількості; різниця в розмірі між і це кількість шляхів розширення в Таким чином, якщо ми не можемо знайти шлях розширення, алгоритм може безпечно зупинитись, тому що в цьому випадку мусить бути оптимальним. Для докладнішого доведення дивись лему Берже.
Шлях розширення в задачі парування тісно пов'язаний із шляхом розширення в задачі про максимальний потік, тобто шляхом уздовж якого можна збільшити обсяг потоку між джерелом і стоком. Можливо перевести задачу парування двочасткового графа в задачу знаходження максимального потоку таким чином, що переміжні шляхи задачі парування стануть шляхами розширення задачі про максимальний потік.[1] Насправді, узагальнення техніки використовуваної в алгоритмі Гопкрофта—Карпа для довільної потокової мережі відоме як алгоритм Дініца.
- Вхід: Двочастковий граф
- Вихід: Парування
- повторювати
- найбільша множина вершинно-неперетинних найкоротших шляхів розширення
- поки
Звичайний алгоритм[ред. | ред. код]
Нехай і будуть двома множинами у двоподілі де і нехай парування з у в будь-який час представлене як множина . Визначимо орієнтований граф як
ЗНАЙТИ-ШЛЯХ-РОЗШИРЕННЯ
|
Лема: Алгоритм ЗНАЙТИ-ШЛЯХ-РОЗШИРЕННЯ знаходить шлях тоді і тільки тоді, коли в існує шлях розширення щодо Більше того, і є шляхом розширення.
НАЙБІЛЬШЕ-ПАРУВАННЯ
|
Розмір найбільшого парування має верхню границю і на кожному кроці збільшується на 1, отже цикл виконається не більше раз. Також нам потрібно часу, щоб знайти шлях розширення, отже алгоритм потребує часу.
Власне алгоритм Гопкрофта—Карпа[ред. | ред. код]
Задля гарантування, що довжина шляху розширення зростає від фази до фази, ми, в кожній фазі, будемо будувати найбільшу можливу множину шляхів розширення
Введемо позначення
Лема: Нехай буде довжиною найкоротшого шляху розширення щодо і нехай буде найбільшою множиною найкоротших неперетинних шляхів щодо тоді довжина найкоротшого шляху розширення щодо більша ніж
Наведемо процедуру, що будує множину . Процедура базується на пошуку в глибину.
ЧАСТКОВИЙ-DFS
|
Видалення вершин гарантує неперетинність зі шляхами, що ми знайдемо пізніше.
Ми використовуватимемо цю процедуру для багатошарового графа який ми будуємо з . Нехай буде множиною вільних вершин з Нехай буде відстань вершини від вершин з . Граф містить такі ребра:
- .
Лема: Кожен шлях у що починається в це найкоротший шлях в
МАКСИМАЛЬНА-МНОЖИНА-ШЛЯХІВ
|
Лема: Процедура МАКСИМАЛЬНА-МНОЖИНА-ШЛЯХІВ знаходить найбільшу множину найкоротших вершинно-неперетинних шляхів розширення щодо за час
Алгоритм-Гопкрофта-Карпа
|
Аналіз[ред. | ред. код]
Алгоритм знаходить найбільше парування в двочастковому графі за час .
Лема: Нехай буде найбільшим паруванням, і нехай буде будь-яким паруванням на Якщо довжина найкоротшого шляху розширення щодо дорівнює тоді .
Примітки[ред. | ред. код]
- ↑ Ahuja, Magnanti та Orlin, (1993), секція 12.3, задача потужності двочасткового парування, сторінки 469–470.
Посилання[ред. | ред. код]
- Алгоритми парування (багато графіки) на сайті Римського університету ла Сапієнца (англ.)
- Парування в графах [Архівовано 22 грудня 2014 у Wayback Machine.] на сайті Інституту Математичних Наук у Ченнаї (англ.)
- Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), Network Flows: Theory, Algorithms and Applications, Prentice-Hall.
- Джек Едмондс (1965), Шляхи, Дерева і Квіти, Канадський журнал з математики, 17: 449—467, doi:10.4153/CJM-1965-045-4, MR 0177907.
|