Хопкрофт-Карп алгоритам

У рачунарству, Хопцрофт-Карп алгоритам је алгоритам који као улаз има бипартитни граф, а као излаз даје упаривање са максималним бројем грана, највећи скуп грана које немају заједничке крајње тачке. Временска сложеност алгоритма је $O(|E|{\sqrt {|V|}})$ у најгорем случају, где је $E$ скуп грана, а $V$ скуп чворова графа. У случају густих графова сложеност постаје кључна $O(|V|^{2.5})$ , а за случајне графове је линеарна. Алгоритам су развили Јохн Хопцрофт и Рицхард Карп (1973 године). Као и претходни алгоритми који се односе на упаривање као сто су Мађарски алгоритам и рад Едмондс-а (1965), Хопцрофт-Карп алгоритам стално повећава величину делимичног упаривања проналажењем алтернирајућих путева. Међутим, уместо да проналази само један алтернирајући пут по итерацији, алгоритам проналази максимални скуп најкраћих алтернирајућих путева. Као резултат тога само $O({\sqrt {n}})$ итерација је потребно. Исти принцип је коришћен при развијању сложенијих алгоритама за не-бипартитно упаривање са истом асимптотском сложеношћу као и Хопцрофт-Карп алгоритам.

Алтернирајући путеви

Теме које не припада грани која се налази у скупу делимично упарених грана $M$, се зове слободно(неупарено) теме. Основни концепт на ком се алгоритам заснива је везан за алтернирајуће путеве, путеве који почињу и завршавају се неупареним чвором, а наизменично пролазе кроз гране које су ушле у скуп упарених и кроз оне које нису. Број грана на том путу мора бити непаран, јер поциње и завршава се неупареним чвором. Нека је $E$ скуп чворова са њиховим гранама, а $M$ скуп упарених чворова са њиховим гранама . Алтернирајући пут $P$ за дато упаривање $M$ је пут између два неупарена чвора, при чему су гране пута $P$ наизменично у $E/M$, односно $M$. Број грана које припадају скупу $E/M$ има за један више него оних које припадају скупу $M$ . Према томе, ако из упаривања избацимо све гране које припадају скупу $M$, а убацимо све оне које припадају скупу $E/M$, добићемо упаривање са једном граном више. Јасно је да ако за дато упаривање постоји алтернирајући пут, онда оно није оптимално. Испоставља се да је и обрнуто тврђење тачно. Упаривање је оптимално ако и само ако нема алтернирајући пут.

Алтернирајући пут у проблему упаривања је блиско повезан са алтернирајућим путевима у проблему максималног протока. Могуће је трансформисати проблем бипартитног упаривања у пример проблема максималног протока, тако сто алтернирајући путеви у проблему упаривања постану алтернирајући путеви у проблему протока. У ствари, генерализација технике која се користи у Хопцрофт-Карп алгоритму је позната као Диниц алгоритам.

Инпут: Бипартите грапх $G(U\cup V,E)$

Оутпут: Матцхинг $M\subseteq E$

$M\leftarrow \emptyset$

репеат

${\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}$ максималан скуп чворова који не припадају најкраћим алтернирајућим путевима

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

унтил ${\mathcal {P}}=\emptyset$

Алгоритам

Нека $U$ и $V$ буду два скупа у бипартитном графу $G$, и нека се упаривање из $U$ у $V$ у било које време може представити као скуп $M$. Алгоритам се ради у фазама. Свака фаза се састоји од следећих корака.

• БФС претрага дели партиције чворова графа на слојеве. Слободни чворови из $U$ се користе као полазна темена за претрагу, и формира се први слој партиције. Током првог нивоа претраге можемо проћи само кроз неупарене ивице (пошто слободни чворови из У по дефиницији не припадају упареним гранама), у наредним нивоима претраге, пролазићемо наизменично кроз упарене и неупарене гране. Приликом тражења суседних чворова почев од чворова из $U$ , можемо проћи једино кроз неупарене гране, док из чворова који припадају $V$ можемо проћи само кроз упарене гране. Претрага се завршава на првом слоју $K$ где су пронађени један или више слободних чворова из $V$.
• Сви слободни чворови из $V$ на слоју $k$ се налазе у скупу $F$. Цвор $v$ се налази у $F$ ако и само ако је крај најкраћег алтернирајућег пута.
• Алгоритам проналази максималан скуп чворова који не припадају алтернирајућим путевима дужине $k$. Овај скуп може бити направљен ДФС претрагом из $F$ до слободних чворова из $U$, коришћењем БФС слојева као водич, ДФС претрагом можемо проћи кроз гране које воде до непосећених чворова на претходном слоју, а ДФС стабло садржи наизменично упарене и неупарене гране. Чим је пронађен алтернирајући пут који садржи један од чворова из $F$, ДФС претрага се наставља из следећег почетног чвора.
• Сваки од путева који је пронађен на овај начин се користи за увећање $M$.

Алгоритам се завршава када БФС претрагом није пронађен ни један алтернирајући пут.

Анализа

Свака фаза се састоји од једне БФС претраге и једне ДФС претраге. Дакле, временска сложеност једне фазе је линеарна. Сложеност првих ${\sqrt {|V|}}$ фаза у графу са $|V|$ чворова и $|E|$ грана је $O(|E|{\sqrt {|V|}})$ . Може се показати да свака фаза повећава дужину најкраћег алтернирајућег пута за најмање један, фаза проналази максималан скуп алтернирајућих путева задате дужине, тако да остали алтернирајући путеви морају бити дужи. Зато, када се почетних ${\sqrt {|V|}}$ фаза алгоритма заврши, преостали најкраћи алтернирајући пут има најмање ${\sqrt {|V|}}$ грана .Међутим, симетрична разлика евентуално оптималног упаривања и делимичног упаривања $M$ током првих фаза формира колекцију чворова и грана које су дисјунктне алтернирајућим путевима и наизменичним циклусима. Уколико је сваки пут у колекцији бар дужине ${\sqrt {|V|}}$ , може бити највисе ${\sqrt {|V|}}$ путева у колекцији, и велицина оптималног упаривања се може разликовати од велицине $M$ за највисе ${\sqrt {|V|}}$ грана. Пошто свака фаза алгоритма повећава величину упаривања за барем један, може постојати највише ${\sqrt {|V|}}$ додатних фаза пре него што се алгоритам заврши. Пошто алгоритам има највише $2{\sqrt {|V|}}$ фаза, његова сложеност је у најгорем случају $O(|E|{\sqrt {|V|}})$ . У многим случајевима,алгоритам има бољу временску сложеност. На пример, у просечном случају, за случајне оскудне бипартитне графове, Баст ет ал. Је показао да са великом вероватноћом сва неоптимална упаривања имају алтернирајуће путеве логаритамске дужине. Као последица, за ове графове, Хопцрофт-Карп алгоритам има $O(\log |V|)$ фаза, а укупна сложеност је $O(|E|\log |V|)$ .

Не-бипартитни графови

Иста идеја о проналажењу максималног скупа најкраћих алтернирајућих путева се користи и за проналажење максималног упаривања у не-бипартитним графовима, и из истих разлога, алгоритам базиран на овој идеји има $O({\sqrt {|V|}})$ фаза. Међутим, за не-бипартитне графове је теже пронаћи алтернирајуће путеве у свакој фази. Надовезујући се на рад неколико споријих претходника, Мицали и Вазирани (1980) су показали како се може имплементирати појединачна фаза са линеарном сложеношћу, што је резултовало алгоритмом који има исту временску сложеност као Хопцрофт-Карп алгоритам за бипартитне графове. Мицали-Вазирани техника је комплексна и њени аутори немају комплетан доказ, алтернативне методе за овај проблем су касније описали други аутори.

Псеудокод

 
 1 //G = G1 ∪ G2 ∪ {NIL}
 2 //G1 i G2 su particije grafa a NIL specijalni null čvor
 3 
 4 
 5    function BFS ()
 6    for v in G1
 7        if Pair_G1[v] == NIL
 8            Dist[v] = 0
 9           Enqueue(Q,v)
 10       else
 11           Dist[v] = ∞
 12    Dist[NIL] = ∞
 13    while Empty(Q) == false
 14        v = Dequeue(Q)
 15        if Dist[v] < Dist[NIL] 
 16            for each u in Adj[v]
 17                if Dist[ Pair_G2[u] ] == ∞
 18                    Dist[ Pair_G2[u] ] = Dist[v] + 1
 19                    Enqueue(Q,Pair_G2[u])
 20    return Dist[NIL] != ∞

 1    function DFS (v)
 2    if v != NIL
 3        for each u in Adj[v]
 4            if Dist[ Pair_G2[u] ] == Dist[v] + 1
 5                if DFS(Pair_G2[u]) == true
 6                    Pair_G2[u] = v
 7                    Pair_G1[v] = u
 8                    return true
 9        Dist[v] = ∞
 10           return false
 11   return true

 1    function Hopcroft-Karp
 2        for each v in G
 3            Pair_G1[v] = NIL
 4            Pair_G2[v] = NIL
 5        matching = 0
 6        while BFS() == true
 7            for each v in G1
 8                if Pair_G1[v] == NIL
 9                    if DFS(v) == true
 10                       matching = matching + 1
 11    return matching