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

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

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

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

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

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

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

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

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

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

$M\leftarrow \mathrm{\varnothing }$

повторювати

$𝒫\leftarrow \{P_1,P_2,\dots ,P_k\}$ найбільша множина вершинно-неперетинних найкоротших шляхів розширення

$M\leftarrow M\oplus (P_1\cup P_2\cup \dots \cup P_k)$

поки $𝒫=\mathrm{\varnothing }$

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

Нехай $V_1$ і $V_2$ будуть двома множинами у двоподілі $G=(V,E),$ де $V=V_1\cup V_2,$ і нехай парування з $V_1$ у $V_2$ в будь-який час представлене як множина $M$. Визначимо орієнтований граф $G_M=(V_1\cup V_2,E_M)$ як

$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\}.$

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

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

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

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

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

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

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

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

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

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

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

Ми використовуватимемо цю процедуру для багатошарового графа ${\overline{G}}_M,$ який ми будуємо з $G_M$. Нехай ${V_1}^{\prime }$ буде множиною вільних вершин з $V_1.$ Нехай $d:V\to \mathbb{N}$ буде відстань $d(v)$ вершини $v$ від вершин з ${V_1}^{\prime }$. Граф ${\overline{G}}_M=(V_1\cup V_2,{\overline{E}}_V)$ містить такі ребра:

${\overline{E}}_M=\{(u,v):(u,v)\in E_M|d(u)+1=d(v)\}$.

Лема: Кожен шлях у ${\overline{G}}_M,$ що починається в ${V_1}^{\prime }$ це найкоротший шлях в $G_M.$

МАКСИМАЛЬНА-МНОЖИНА-ШЛЯХІВ$(G=(V_1\cup V_2,E),M)$ $P=\mathrm{\varnothing }$ побудувати граф ${\overline{G}}_M=(V_1\cup V_2,{\overline{E}}_M)$ нехай ${V_1}^{\prime }$ буде множиною вільних вершин у $V_1$ для $v\in {V_1}^{\prime }$виконати $p=$ ЧАСТКОВИЙ-DFS$({\overline{G}}_M,v,{V_2}^{\prime })$ якщо $p\ne NIL$ тоді $P=P\cup p$ повернути $P$

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

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

Аналіз

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

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

Посилання

• Алгоритми парування (багато графіки) на сайті Римського університету ла Сапієнца Шаблон:Ref-en
• Парування в графах Шаблон:Webarchive на сайті Інституту Математичних Наук у Ченнаї Шаблон:Ref-en
• Шаблон:Citation.
• Шаблон:Citation.