Алгоритм Гопкрофта — Карпа

В інформатиці, алгоритм Гопкрофта—Карпа отримує на вході двочастковий граф і видає на виході парування найбільшої потужності – множину, що містить якнайбільше ребер з властивістю, що жодна двійка ребер не має спільної вершини. Виконується за час ${\displaystyle O(|E|{\sqrt {|V|}})}$ у найгіршому випадку, де ${\displaystyle E}$ це множина ребер і ${\displaystyle V}$ це множина вершин графа. У випадку насиченого графа часові рамки набувають вигляду ${\displaystyle O(|V|^{2.5})}$, для випадкових графів час виконання майже лінійний.

Алгоритм винайшли Джон Гопкрофт and Річард Карп (1973). Як і в попередніх методах для парування як-от Угорський алгоритм і роботі Едмондс, (1965), алгоритм Гопкрофта—Карпа багаторазово збільшує часткове парування через знаходження шляху розширення. Однак, замість пошуку одного шляху розширення, алгоритм шукає найбільшу множину найкоротших шляхів розширення. У результаті, потрібно лише ${\displaystyle O({\sqrt {n}})}$ ітерацій. Цей принцип використовували для розробки складніших алгоритмів для недвочасткового парування з таким самим часом виконання як у алгоритму Гопкрофта—Карпа.

Шляхи розширення

Збільшення парування ${\displaystyle \{b\}}$ через знаходження шляху розширення ${\displaystyle \{a,b,c\}}$ і застосування симетричної різниці для двох множин

У висліді маємо нове парування ${\displaystyle \{a,c\},}$ потужність якого на одиницю більша. Вершина, яка не є кінцем жодного ребра в певному частковому паруванні ${\displaystyle M}$ називається вільна вершина. В основі алгоритму лежить поняття шлях розширення, шлях який починається у вільній вершині і закінчується вільною вершиною, також він чергує ребро з парування з ребрами, що не входять до парування. Якщо ${\displaystyle M}$ це парування і ${\displaystyle P}$ це шлях розширення щодо ${\displaystyle M}$, тоді симетрична різниця двох множин ребер, ${\displaystyle M\oplus P}$, буде парування розміру ${\displaystyle |M|+1}$. Отже, знаходженням шляхів доповнення, алгоритм може збільшувати розмір парування.

І навпаки, припустимо, що ${\displaystyle M}$ не оптимальне, і нехай ${\displaystyle P}$ буде симетричною різницею ${\displaystyle M\oplus M^{*}}$ де ${\displaystyle M^{*}}$ це оптимальне парування. Тоді, ${\displaystyle P}$ повинен утворювати набір неперетинних шляхів розширення і циклів або шляхів в яких вільні ребра і ребра з парування зустрічаються в однаковій кількості; різниця в розмірі між ${\displaystyle M}$ і ${\displaystyle M^{*}}$ це кількість шляхів розширення в ${\displaystyle P.}$ Таким чином, якщо ми не можемо знайти шлях розширення, алгоритм може безпечно зупинитись, тому що в цьому випадку ${\displaystyle M}$ мусить бути оптимальним. Для докладнішого доведення дивись лему Берже.

Шлях розширення в задачі парування тісно пов'язаний із шляхом розширення в задачі про максимальний потік, тобто шляхом уздовж якого можна збільшити обсяг потоку між джерелом і стоком. Можливо перевести задачу парування двочасткового графа в задачу знаходження максимального потоку таким чином, що переміжні шляхи задачі парування стануть шляхами розширення задачі про максимальний потік.^[1] Насправді, узагальнення техніки використовуваної в алгоритмі Гопкрофта—Карпа для довільної потокової мережі відоме як алгоритм Дініца.

Вхід: Двочастковий граф ${\displaystyle G(L\cup R,E)}$

Вихід: Парування ${\displaystyle M\subseteq E}$

${\displaystyle M\leftarrow \emptyset }$

повторювати

${\displaystyle {\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}}$ найбільша множина вершинно-неперетинних найкоротших шляхів розширення

${\displaystyle M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})}$

поки ${\displaystyle {\mathcal {P}}=\emptyset }$

Звичайний алгоритм

Нехай ${\displaystyle V_{1}}$ і ${\displaystyle V_{2}}$ будуть двома множинами у двоподілі ${\displaystyle G=(V,E),}$ де ${\displaystyle V=V_{1}\cup V_{2},}$ і нехай парування з ${\displaystyle V_{1}}$ у ${\displaystyle V_{2}}$ в будь-який час представлене як множина ${\displaystyle M}$. Визначимо орієнтований граф ${\displaystyle G_{M}=(V_{1}\cup V_{2},E_{M})}$ як

${\displaystyle E_{M}=\{(v_{1},v_{2}):v_{1}v_{2}\in E,v_{1}\in V_{1},v_{2}\in V_{2}\}\cup \{(v_{2},v_{1}):v_{1}v_{2}\in M,v_{1}\in V_{1},v_{2}\in V_{2}\}.}$

ЗНАЙТИ-ШЛЯХ-РОЗШИРЕННЯ ${\displaystyle (G=(V_{1}\cup V_{2},E),M)}$ ${\displaystyle V_{1}'=}$ множина вільних вершин у ${\displaystyle V_{1}}$ ${\displaystyle V_{2}'=}$ множина вільних вершин у ${\displaystyle V_{2}}$ побудувати орієнтований граф ${\displaystyle G_{M}=(V_{1}\cup V_{2},E_{M})}$ знайти простий шлях ${\displaystyle p}$ з ${\displaystyle V_{1}'}$ до ${\displaystyle V_{2}'}$ у ${\displaystyle G_{M}}$ якщо ${\displaystyle p}$ не існує тоді повернути ${\displaystyle NIL}$ (немає шляхів розширення) інакше повернути ${\displaystyle p}$ (${\displaystyle p}$ це шлях розширення в ${\displaystyle G}$)

Лема: Алгоритм ЗНАЙТИ-ШЛЯХ-РОЗШИРЕННЯ знаходить шлях ${\displaystyle p}$ тоді і тільки тоді, коли в ${\displaystyle G}$ існує шлях розширення щодо ${\displaystyle M.}$ Більше того, ${\displaystyle p}$ і є шляхом розширення.

НАЙБІЛЬШЕ-ПАРУВАННЯ ${\displaystyle G=(V_{1}\cup V_{2},E))}$ ${\displaystyle M=\emptyset }$ повторювати ${\displaystyle p=}$ЗНАЙТИ-ШЛЯХ-РОЗШИРЕННЯ${\displaystyle (G,M)}$ якщо ${\displaystyle p\neq NIL}$ тоді ${\displaystyle M=M\oplus p}$ поки повернути ${\displaystyle M}$

Розмір найбільшого парування має верхню границю ${\displaystyle |V|/2}$ і на кожному кроці збільшується на 1, отже цикл виконається не більше ${\displaystyle O(|V|)}$ раз. Також нам потрібно ${\displaystyle O(|E|)}$ часу, щоб знайти шлях розширення, отже алгоритм потребує ${\displaystyle O(|V||E|)}$ часу.

Власне алгоритм Гопкрофта—Карпа

Задля гарантування, що довжина шляху розширення зростає від фази до фази, ми, в кожній фазі, будемо будувати найбільшу можливу множину шляхів розширення ${\displaystyle P.}$

Введемо позначення ${\displaystyle M\oplus P=M\oplus (\oplus _{p\in P}p).}$

Лема: Нехай ${\displaystyle k}$ буде довжиною найкоротшого шляху розширення щодо ${\displaystyle M}$ і нехай ${\displaystyle P}$ буде найбільшою множиною найкоротших неперетинних шляхів щодо ${\displaystyle M,}$ тоді довжина найкоротшого шляху розширення щодо ${\displaystyle M\oplus P}$ більша ніж ${\displaystyle k.}$

Наведемо процедуру, що будує множину ${\displaystyle P}$. Процедура базується на пошуку в глибину.

ЧАСТКОВИЙ-DFS${\displaystyle (G,v,T)}$ запустити ${\displaystyle {\mbox{DFS}}(G,v)}$ допоки не знайдена перша вершина з ${\displaystyle T}$ видалити усі вершини відвідані під час ${\displaystyle DFS}$ з графа ${\displaystyle G}$ якщо існує шлях ${\displaystyle p}$ з ${\displaystyle v}$ до ${\displaystyle T}$ тоді повернути ${\displaystyle p}$ інакше повернути ${\displaystyle NIL}$

Видалення вершин гарантує неперетинність зі шляхами, що ми знайдемо пізніше.

Ми використовуватимемо цю процедуру для багатошарового графа ${\displaystyle {\bar {G}}_{M},}$ який ми будуємо з ${\displaystyle G_{M}}$. Нехай ${\displaystyle V_{1}'}$ буде множиною вільних вершин з ${\displaystyle V_{1}.}$ Нехай ${\displaystyle d:V\to \mathbb {N} }$ буде відстань ${\displaystyle d(v)}$ вершини ${\displaystyle v}$ від вершин з ${\displaystyle V_{1}'}$. Граф ${\displaystyle {\bar {G}}_{M}=(V_{1}\cup V_{2},{\bar {E}}_{V})}$ містить такі ребра:

${\displaystyle {\bar {E}}_{M}=\{(u,v):(u,v)\in E_{M}|d(u)+1=d(v)\}}$.

Лема: Кожен шлях у ${\displaystyle {\bar {G}}_{M},}$ що починається в ${\displaystyle V_{1}'}$ це найкоротший шлях в ${\displaystyle G_{M}.}$

МАКСИМАЛЬНА-МНОЖИНА-ШЛЯХІВ${\displaystyle (G=(V_{1}\cup V_{2},E),M)}$ ${\displaystyle P=\emptyset }$ побудувати граф ${\displaystyle {\bar {G}}_{M}=(V_{1}\cup V_{2},{\bar {E}}_{M})}$ нехай ${\displaystyle V_{1}'}$ буде множиною вільних вершин у ${\displaystyle V_{1}}$ для ${\displaystyle v\in V_{1}'}$виконати ${\displaystyle p=}$ ЧАСТКОВИЙ-DFS${\displaystyle ({\bar {G}}_{M},v,V_{2}')}$ якщо ${\displaystyle p\neq NIL}$ тоді ${\displaystyle P=P\cup p}$ повернути ${\displaystyle P}$

Лема: Процедура МАКСИМАЛЬНА-МНОЖИНА-ШЛЯХІВ знаходить найбільшу множину найкоротших вершинно-неперетинних шляхів розширення щодо ${\displaystyle M}$ за час ${\displaystyle O(E).}$

Алгоритм-Гопкрофта-Карпа${\displaystyle (G=(V_{1}\cup V_{2},E))}$ ${\displaystyle M=\emptyset }$ повторювати ${\displaystyle P=}$ МАКСИМАЛЬНА-МНОЖИНА-ШЛЯХІВ${\displaystyle (G=(V_{1},V_{2},E),M)}$ якщо ${\displaystyle P\neq NIL}$ тоді ${\displaystyle M=M\oplus P}$ поки ${\displaystyle P=NIL}$ повернути ${\displaystyle M}$

Аналіз

Алгоритм знаходить найбільше парування в двочастковому графі за час ${\displaystyle O({\sqrt {|V|}}|E|)}$.

Лема: Нехай ${\displaystyle M^{*}}$ буде найбільшим паруванням, і нехай ${\displaystyle M}$ буде будь-яким паруванням на ${\displaystyle G.}$ Якщо довжина найкоротшого шляху розширення щодо ${\displaystyle M}$ дорівнює ${\displaystyle k,}$ тоді ${\displaystyle |M^{*}|-|M|\leq {\frac {|V|}{k}}}$.

Примітки

1. 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.