В інформатиці, алгоритм Гопкрофта—Карпа отримує на вході двочастковий граф і видає на виході парування найбільшої потужності – множину, що містить якнайбільше ребер з властивістю, що жодна двійка ребер не має спільної вершини. Виконується за час у найгіршому випадку, де це множина ребер і це множина вершин графа. У випадку часові рамки набувають вигляду , для випадкових графів час виконання майже лінійний.
Алгоритм винайшли Джон Гопкрофт and Річард Карп (1973). Як і в попередніх методах для парування як-от Угорський алгоритм і роботі Едмондс, (1965), алгоритм Гопкрофта—Карпа багаторазово збільшує часткове парування через знаходження шляху розширення. Однак, замість пошуку одного шляху розширення, алгоритм шукає найбільшу множину найкоротших шляхів розширення. У результаті, потрібно лише ітерацій. Цей принцип використовували для розробки складніших алгоритмів для недвочасткового парування з таким самим часом виконання як у алгоритму Гопкрофта—Карпа.
Шляхи розширення
У висліді маємо нове парування потужність якого на одиницю більша. Вершина, яка не є кінцем жодного ребра в певному частковому паруванні називається вільна вершина. В основі алгоритму лежить поняття шлях розширення, шлях який починається у вільній вершині і закінчується вільною вершиною, також він чергує ребро з парування з ребрами, що не входять до парування. Якщо це парування і це шлях розширення щодо , тоді симетрична різниця двох множин ребер, , буде парування розміру . Отже, знаходженням шляхів доповнення, алгоритм може збільшувати розмір парування.
І навпаки, припустимо, що не оптимальне, і нехай буде симетричною різницею де це оптимальне парування. Тоді, повинен утворювати набір неперетинних шляхів розширення і циклів або шляхів в яких вільні ребра і ребра з парування зустрічаються в однаковій кількості; різниця в розмірі між і це кількість шляхів розширення в Таким чином, якщо ми не можемо знайти шлях розширення, алгоритм може безпечно зупинитись, тому що в цьому випадку мусить бути оптимальним. Для докладнішого доведення дивись лему Берже.
Шлях розширення в задачі парування тісно пов'язаний із шляхом розширення в задачі про максимальний потік, тобто шляхом уздовж якого можна збільшити обсяг потоку між джерелом і стоком. Можливо перевести задачу парування двочасткового графа в задачу знаходження максимального потоку таким чином, що переміжні шляхи задачі парування стануть шляхами розширення задачі про максимальний потік. Насправді, узагальнення техніки використовуваної в алгоритмі Гопкрофта—Карпа для довільної потокової мережі відоме як алгоритм Дініца.
- Вхід: Двочастковий граф
- Вихід: Парування
- повторювати
- найбільша множина вершинно-неперетинних найкоротших шляхів розширення
- поки
Звичайний алгоритм
Нехай і будуть двома множинами у двоподілі де і нехай парування з у в будь-який час представлене як множина . Визначимо орієнтований граф як
ЗНАЙТИ-ШЛЯХ-РОЗШИРЕННЯ
|
Лема: Алгоритм ЗНАЙТИ-ШЛЯХ-РОЗШИРЕННЯ знаходить шлях тоді і тільки тоді, коли в існує шлях розширення щодо Більше того, і є шляхом розширення.
НАЙБІЛЬШЕ-ПАРУВАННЯ
|
Розмір найбільшого парування має верхню границю і на кожному кроці збільшується на 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
V informatici algoritm Gopkrofta Karpa otrimuye na vhodi dvochastkovij graf i vidaye na vihodi paruvannya najbilshoyi potuzhnosti mnozhinu sho mistit yaknajbilshe reber z vlastivistyu sho zhodna dvijka reber ne maye spilnoyi vershini Vikonuyetsya za chas O E V displaystyle O E sqrt V u najgirshomu vipadku de E displaystyle E ce mnozhina reber i V displaystyle V ce mnozhina vershin grafa U vipadku nasichenogo grafa chasovi ramki nabuvayut viglyadu O V 2 5 displaystyle O V 2 5 dlya vipadkovih grafiv chas vikonannya majzhe linijnij Algoritm vinajshli Dzhon Gopkroft and Richard Karp 1973 Yak i v poperednih metodah dlya paruvannya yak ot Ugorskij algoritm i roboti Edmonds 1965 algoritm Gopkrofta Karpa bagatorazovo zbilshuye chastkove paruvannya cherez znahodzhennya shlyahu rozshirennya Odnak zamist poshuku odnogo shlyahu rozshirennya algoritm shukaye najbilshu mnozhinu najkorotshih shlyahiv rozshirennya U rezultati potribno lishe O n displaystyle O sqrt n iteracij Cej princip vikoristovuvali dlya rozrobki skladnishih algoritmiv dlya nedvochastkovogo paruvannya z takim samim chasom vikonannya yak u algoritmu Gopkrofta Karpa Zmist 1 Shlyahi rozshirennya 2 Zvichajnij algoritm 3 Vlasne algoritm Gopkrofta Karpa 4 Analiz 5 Primitki 6 PosilannyaShlyahi rozshirennyared nbsp Zbilshennya paruvannya b displaystyle b nbsp cherez znahodzhennya shlyahu rozshirennya a b c displaystyle a b c nbsp i zastosuvannya simetrichnoyi riznici dlya dvoh mnozhin U vislidi mayemo nove paruvannya a c displaystyle a c nbsp potuzhnist yakogo na odinicyu bilsha Vershina yaka ne ye kincem zhodnogo rebra v pevnomu chastkovomu paruvanni M displaystyle M nbsp nazivayetsya vilna vershina V osnovi algoritmu lezhit ponyattya shlyah rozshirennya shlyah yakij pochinayetsya u vilnij vershini i zakinchuyetsya vilnoyu vershinoyu takozh vin cherguye rebro z paruvannya z rebrami sho ne vhodyat do paruvannya Yaksho M displaystyle M nbsp ce paruvannya i P displaystyle P nbsp ce shlyah rozshirennya shodo M displaystyle M nbsp todi simetrichna riznicya dvoh mnozhin reber M P displaystyle M oplus P nbsp bude paruvannya rozmiru M 1 displaystyle M 1 nbsp Otzhe znahodzhennyam shlyahiv dopovnennya algoritm mozhe zbilshuvati rozmir paruvannya I navpaki pripustimo sho M displaystyle M nbsp ne optimalne i nehaj P displaystyle P nbsp bude simetrichnoyu rizniceyu M M displaystyle M oplus M nbsp de M displaystyle M nbsp ce optimalne paruvannya Todi P displaystyle P nbsp povinen utvoryuvati nabir neperetinnih shlyahiv rozshirennya i cikliv abo shlyahiv v yakih vilni rebra i rebra z paruvannya zustrichayutsya v odnakovij kilkosti riznicya v rozmiri mizh M displaystyle M nbsp i M displaystyle M nbsp ce kilkist shlyahiv rozshirennya v P displaystyle P nbsp Takim chinom yaksho mi ne mozhemo znajti shlyah rozshirennya algoritm mozhe bezpechno zupinitis tomu sho v comu vipadku M displaystyle M nbsp musit buti optimalnim Dlya dokladnishogo dovedennya divis lemu Berzhe Shlyah rozshirennya v zadachi paruvannya tisno pov yazanij iz shlyahom rozshirennya v zadachi pro maksimalnij potik tobto shlyahom uzdovzh yakogo mozhna zbilshiti obsyag potoku mizh dzherelom i stokom Mozhlivo perevesti zadachu paruvannya dvochastkovogo grafa v zadachu znahodzhennya maksimalnogo potoku takim chinom sho peremizhni shlyahi zadachi paruvannya stanut shlyahami rozshirennya zadachi pro maksimalnij potik 1 Naspravdi uzagalnennya tehniki vikoristovuvanoyi v algoritmi Gopkrofta Karpa dlya dovilnoyi potokovoyi merezhi vidome yak algoritm Dinica Vhid Dvochastkovij graf G L R E displaystyle G L cup R E nbsp Vihid Paruvannya M E displaystyle M subseteq E nbsp M displaystyle M leftarrow emptyset nbsp povtoryuvatiP P 1 P 2 P k displaystyle mathcal P leftarrow P 1 P 2 dots P k nbsp najbilsha mnozhina vershinno neperetinnih najkorotshih shlyahiv rozshirennya M M P 1 P 2 P k displaystyle M leftarrow M oplus P 1 cup P 2 cup dots cup P k nbsp dd poki P displaystyle mathcal P emptyset nbsp Zvichajnij algoritmred Nehaj V 1 displaystyle V 1 nbsp i V 2 displaystyle V 2 nbsp budut dvoma mnozhinami u dvopodili G V E displaystyle G V E nbsp de V V 1 V 2 displaystyle V V 1 cup V 2 nbsp i nehaj paruvannya z V 1 displaystyle V 1 nbsp u V 2 displaystyle V 2 nbsp v bud yakij chas predstavlene yak mnozhina M displaystyle M nbsp Viznachimo oriyentovanij graf G M V 1 V 2 E M displaystyle G M V 1 cup V 2 E M nbsp yak E M v 1 v 2 v 1 v 2 E v 1 V 1 v 2 V 2 v 2 v 1 v 1 v 2 M v 1 V 1 v 2 V 2 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 nbsp ZNAJTI ShLYaH ROZShIRENNYa G V 1 V 2 E M displaystyle G V 1 cup V 2 E M nbsp V 1 displaystyle V 1 nbsp mnozhina vilnih vershin u V 1 displaystyle V 1 nbsp V 2 displaystyle V 2 nbsp mnozhina vilnih vershin u V 2 displaystyle V 2 nbsp pobuduvati oriyentovanij graf G M V 1 V 2 E M displaystyle G M V 1 cup V 2 E M nbsp znajti prostij shlyah p displaystyle p nbsp z V 1 displaystyle V 1 nbsp do V 2 displaystyle V 2 nbsp u G M displaystyle G M nbsp yaksho p displaystyle p nbsp ne isnuye todi povernuti N I L displaystyle NIL nbsp nemaye shlyahiv rozshirennya inakshe povernuti p displaystyle p nbsp p displaystyle p nbsp ce shlyah rozshirennya v G displaystyle G nbsp Lema Algoritm ZNAJTI ShLYaH ROZShIRENNYa znahodit shlyah p displaystyle p nbsp todi i tilki todi koli v G displaystyle G nbsp isnuye shlyah rozshirennya shodo M displaystyle M nbsp Bilshe togo p displaystyle p nbsp i ye shlyahom rozshirennya NAJBILShE PARUVANNYa G V 1 V 2 E displaystyle G V 1 cup V 2 E nbsp M displaystyle M emptyset nbsp povtoryuvati p displaystyle p nbsp ZNAJTI ShLYaH ROZShIRENNYa G M displaystyle G M nbsp yaksho p N I L displaystyle p neq NIL nbsp todiM M p displaystyle M M oplus p nbsp dd poki povernuti M displaystyle M nbsp Rozmir najbilshogo paruvannya maye verhnyu granicyu V 2 displaystyle V 2 nbsp i na kozhnomu kroci zbilshuyetsya na 1 otzhe cikl vikonayetsya ne bilshe O V displaystyle O V nbsp raz Takozh nam potribno O E displaystyle O E nbsp chasu shob znajti shlyah rozshirennya otzhe algoritm potrebuye O V E displaystyle O V E nbsp chasu Vlasne algoritm Gopkrofta Karpared Zadlya garantuvannya sho dovzhina shlyahu rozshirennya zrostaye vid fazi do fazi mi v kozhnij fazi budemo buduvati najbilshu mozhlivu mnozhinu shlyahiv rozshirennya P displaystyle P nbsp Vvedemo poznachennya M P M p P p displaystyle M oplus P M oplus oplus p in P p nbsp Lema Nehaj k displaystyle k nbsp bude dovzhinoyu najkorotshogo shlyahu rozshirennya shodo M displaystyle M nbsp i nehaj P displaystyle P nbsp bude najbilshoyu mnozhinoyu najkorotshih neperetinnih shlyahiv shodo M displaystyle M nbsp todi dovzhina najkorotshogo shlyahu rozshirennya shodo M P displaystyle M oplus P nbsp bilsha nizh k displaystyle k nbsp Navedemo proceduru sho buduye mnozhinu P displaystyle P nbsp Procedura bazuyetsya na poshuku v glibinu ChASTKOVIJ DFS G v T displaystyle G v T nbsp zapustiti DFS G v displaystyle mbox DFS G v nbsp dopoki ne znajdena persha vershina z T displaystyle T nbsp vidaliti usi vershini vidvidani pid chas D F S displaystyle DFS nbsp z grafa G displaystyle G nbsp yaksho isnuye shlyah p displaystyle p nbsp z v displaystyle v nbsp do T displaystyle T nbsp todi povernuti p displaystyle p nbsp inakshe povernuti N I L displaystyle NIL nbsp Vidalennya vershin garantuye neperetinnist zi shlyahami sho mi znajdemo piznishe Mi vikoristovuvatimemo cyu proceduru dlya bagatosharovogo grafa G M displaystyle bar G M nbsp yakij mi buduyemo z G M displaystyle G M nbsp Nehaj V 1 displaystyle V 1 nbsp bude mnozhinoyu vilnih vershin z V 1 displaystyle V 1 nbsp Nehaj d V N displaystyle d V to mathbb N nbsp bude vidstan d v displaystyle d v nbsp vershini v displaystyle v nbsp vid vershin z V 1 displaystyle V 1 nbsp Graf G M V 1 V 2 E V displaystyle bar G M V 1 cup V 2 bar E V nbsp mistit taki rebra E M u v u v E M d u 1 d v displaystyle bar E M u v u v in E M d u 1 d v nbsp Lema Kozhen shlyah u G M displaystyle bar G M nbsp sho pochinayetsya v V 1 displaystyle V 1 nbsp ce najkorotshij shlyah v G M displaystyle G M nbsp MAKSIMALNA MNOZhINA ShLYaHIV G V 1 V 2 E M displaystyle G V 1 cup V 2 E M nbsp P displaystyle P emptyset nbsp pobuduvati graf G M V 1 V 2 E M displaystyle bar G M V 1 cup V 2 bar E M nbsp nehaj V 1 displaystyle V 1 nbsp bude mnozhinoyu vilnih vershin u V 1 displaystyle V 1 nbsp dlya v V 1 displaystyle v in V 1 nbsp vikonati p displaystyle p nbsp ChASTKOVIJ DFS G M v V 2 displaystyle bar G M v V 2 nbsp yaksho p N I L displaystyle p neq NIL nbsp todiP P p displaystyle P P cup p nbsp dd povernuti P displaystyle P nbsp Lema Procedura MAKSIMALNA MNOZhINA ShLYaHIV znahodit najbilshu mnozhinu najkorotshih vershinno neperetinnih shlyahiv rozshirennya shodo M displaystyle M nbsp za chas O E displaystyle O E nbsp Algoritm Gopkrofta Karpa G V 1 V 2 E displaystyle G V 1 cup V 2 E nbsp M displaystyle M emptyset nbsp povtoryuvati P displaystyle P nbsp MAKSIMALNA MNOZhINA ShLYaHIV G V 1 V 2 E M displaystyle G V 1 V 2 E M nbsp yaksho P N I L displaystyle P neq NIL nbsp todiM M P displaystyle M M oplus P nbsp dd poki P N I L displaystyle P NIL nbsp povernuti M displaystyle M nbsp Analizred Algoritm znahodit najbilshe paruvannya v dvochastkovomu grafi za chas O V E displaystyle O sqrt V E nbsp Lema Nehaj M displaystyle M nbsp bude najbilshim paruvannyam i nehaj M displaystyle M nbsp bude bud yakim paruvannyam na G displaystyle G nbsp Yaksho dovzhina najkorotshogo shlyahu rozshirennya shodo M displaystyle M nbsp dorivnyuye k displaystyle k nbsp todi M M V k displaystyle M M leq frac V k nbsp Primitkired Ahuja Magnanti ta Orlin 1993 sekciya 12 3 zadacha potuzhnosti dvochastkovogo paruvannya storinki 469 470 Posilannyared Algoritmi paruvannya bagato grafiki na sajti Rimskogo universitetu la Sapiyenca angl Paruvannya v grafah Arhivovano 22 grudnya 2014 u Wayback Machine na sajti Institutu Matematichnih Nauk u Chennayi angl Ahuja Ravindra K Magnanti Thomas L Orlin James B 1993 Network Flows Theory Algorithms and Applications Prentice Hall Dzhek Edmonds 1965 Shlyahi Dereva i Kviti Kanadskij zhurnal z matematiki 17 449 467 doi 10 4153 CJM 1965 045 4 MR 0177907 Otrimano z https uk wikipedia org w index php title Algoritm Gopkrofta Karpa amp oldid 35851245