Перегляд вихідного коду сторінки Алгоритм Гопкрофта — Карпа

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

Алгоритм винайшли {{harvs|first1=Джон|last1=Гопкрофт|author1-link=Джон Гопкрофт|first2=Річард|last2=Карп|author2-link=Річард Карп|txt|year=1973}}. Як і в попередніх методах для парування як-от [[Угорський алгоритм]] і роботі {{harvtxt|Едмондс|1965}}, алгоритм Гопкрофта—Карпа багаторазово збільшує часткове парування через знаходження шляху розширення. Однак, замість пошуку одного шляху розширення, алгоритм шукає найбільшу множину найкоротших шляхів розширення. У результаті, потрібно лише <math>O(\sqrt{n})</math> ітерацій. Цей принцип використовували для розробки складніших алгоритмів для недвочасткового парування з таким самим часом виконання як у алгоритму Гопкрофта—Карпа.

==Шляхи розширення==
[[Зображення:Matching_(graph_theory).png|thumb|right|Збільшення парування <math>\{b\}</math> через знаходження шляху розширення <math>\{a,b,c\}</math> і застосування [[Симетрична різниця множин|симетричної різниці для двох множин]]]]

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

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

Шлях розширення в задачі парування тісно пов'язаний із шляхом розширення в [[задача про максимальний потік|задачі про максимальний потік]], тобто шляхом уздовж якого можна збільшити обсяг потоку між джерелом і стоком. Можливо перевести задачу парування двочасткового графа в задачу знаходження максимального потоку таким чином, що переміжні шляхи задачі парування стануть шляхами розширення задачі про максимальний потік.<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, секція 12.3, задача потужності двочасткового парування, сторінки 469–470.</ref> Насправді, узагальнення техніки використовуваної в алгоритмі Гопкрофта—Карпа для довільної потокової мережі відоме як [[алгоритм Дініца]].

: '''Вхід''': Двочастковий граф <math>G(L \cup R, E)</math>
: '''Вихід''': Парування <math>M \subseteq E</math>
: <math>M \leftarrow \empty</math>
: '''повторювати'''
:: <math>\mathcal P \leftarrow \{P_1, P_2, \dots, P_k\}</math> ''найбільша множина вершинно-неперетинних найкоротших шляхів розширення''
:: <math>M \leftarrow M \oplus (P_1 \cup P_2 \cup \dots \cup P_k)</math>
: '''поки''' <math>\mathcal P = \empty</math>

==Звичайний алгоритм==
Нехай <math>V_1</math> і <math>V_2</math> будуть двома множинами у двоподілі <math>G=(V, E),</math> де <math>V = V_1 \cup V_2,</math> і нехай парування з <math>V_1</math> у <math>V_2</math> в будь-який час представлене як множина <math>M</math>. Визначимо орієнтований граф <math>G_M=(V_1 \cup V_2, E_M)</math> як
:<math>E_M=\{(v_1,v_2):v_1v_2\in E, v_1\in V_1, v_2\in V_2\}\cup\{(v_2,v_1):v_1v_2\in M,v_1\in V_1, v_2\in V_2\}.</math>

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

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

{| class="wikitable"
|-
| 
'''''НАЙБІЛЬШЕ-ПАРУВАННЯ''''' <math>G=(V_1 \cup V_2,E))</math>
* <math>M = \empty</math>
* '''повторювати'''
*:<math>p=</math>'''''ЗНАЙТИ-ШЛЯХ-РОЗШИРЕННЯ'''''<math>(G,M)</matH>
*:'''якщо''' <math>p \ne NIL</math> '''тоді'''
*::<math>M = M\oplus p</math>
*:'''поки'''
*:'''повернути''' <math>M</math>
|}

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

==Власне алгоритм Гопкрофта—Карпа==
Задля гарантування, що довжина шляху розширення зростає від фази до фази, ми, в кожній фазі, будемо будувати найбільшу можливу множину шляхів розширення <math>P.</math>

Введемо позначення <math>M\oplus P = M\oplus (\oplus_{p\in P}p).</math>

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

Наведемо процедуру, що будує множину <math>P</math>. Процедура базується на [[пошук у глибину|пошуку в глибину]].

{| class="wikitable"
|-
| '''''ЧАСТКОВИЙ-DFS'''''<math>(G,v,T)</math>
* запустити <math>\mbox{DFS}(G,v)</math> допоки не знайдена перша вершина з <math>T</math>
* видалити усі вершини відвідані під час <math>DFS</math> з графа <math>G</math>
* '''якщо''' існує шлях <math>p</math> з <math>v</math> до <math>T</math> '''тоді'''
*:'''повернути''' <math>p</math>
*'''інакше'''
*:'''повернути''' <math>NIL</math> 
|}
Видалення вершин гарантує неперетинність зі шляхами, що ми знайдемо пізніше.

Ми використовуватимемо цю процедуру для багатошарового графа <math>\bar G_M,</math> який ми будуємо з <math>G_M</math>. Нехай <math>V_1'</math> буде множиною вільних вершин з <math>V_1.</math> Нехай <math>d:V\to \mathbb{N}</math> буде відстань <math>d(v)</math> вершини <math>v</math> від вершин з <math>V_1'</math>. Граф <math>\bar G_M=(V_1\cup V_2,\bar E_V)</math> містить такі ребра:
:<math>\bar E_M= \{(u,v):(u,v)\in E_M|d(u)+1=d(v)\}</math>.

'''Лема:''' Кожен шлях у <math>\bar G_M,</math> що починається в <math>V_1'</math> це найкоротший шлях в <math>G_M.</math>

{| class="wikitable"
|-
| '''''МАКСИМАЛЬНА-МНОЖИНА-ШЛЯХІВ'''''<math>(G=(V_1\cup V_2,E),M)</math>
*<math>P=\empty</math>
*побудувати граф <math>\bar G_M=(V_1\cup V_2,\bar E_M)</math>
*нехай <math>V_1'</math> буде множиною вільних вершин у <math>V_1</math>
*'''для''' <math>v\in V_1'</math>'''виконати'''
*:<math>p=</math> '''''ЧАСТКОВИЙ-DFS'''''<math>(\bar G_M,v,V_2')</math>
*:'''якщо''' <math>p\ne NIL</math> '''тоді'''
*::<math>P=P\cup p</math>
*'''повернути''' <math>P</math>
|}

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

{| class="wikitable"
|-
| '''''Алгоритм-Гопкрофта-Карпа'''''<math>(G=(V_1\cup V_2,E))</math>
*<math>M=\empty</math>
*'''повторювати'''
*:<math>P=</math> '''''МАКСИМАЛЬНА-МНОЖИНА-ШЛЯХІВ'''''<math>(G=(V_1,V_2,E),M)</math>
*:'''якщо''' <math>P\ne NIL</math> '''тоді'''
*::<math>M=M\oplus P</math>
*:'''поки''' <math>P=NIL</math>
*'''повернути''' <math>M</math>
|}

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

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

== Примітки ==
{{reflist}}

== Посилання ==
* [https://web.archive.org/web/20141211011352/http://www.dis.uniroma1.it/~leon/tcs/lecture2.pdf Алгоритми парування (багато графіки)] на сайті [[Римський університет ла Сапієнца|Римського університету ла Сапієнца]] {{ref-en}}
* [http://www.imsc.res.in/~meena/matching/hopcroft-karp.pdf Парування в графах] {{Webarchive|url=https://web.archive.org/web/20141222174228/http://www.imsc.res.in/~meena/matching/hopcroft-karp.pdf |date=22 грудня 2014 }} на сайті Інституту Математичних Наук у Ченнаї {{ref-en}}
*{{citation|first1=Ravindra K.|last1=Ahuja|first2=Thomas L.|last2=Magnanti|first3=James B.|last3=Orlin|title=Network Flows: Theory, Algorithms and Applications|publisher=Prentice-Hall|year=1993}}.
*{{citation | doi = 10.4153/CJM-1965-045-4 | last = Джек Едмондс | author-link = Джек Едмондс | journal = Канадський журнал з математики | pages = 449–467 | title = Шляхи, Дерева і Квіти | volume = 17 | year = 1965 | mr = 0177907}}.
{{Алгоритми на графах}}
[[Категорія:Алгоритми на графах]]
[[Категорія:Парування]]