Back

ⓘ Hopkroft-Karp algoritam




                                     

ⓘ Hopkroft-Karp algoritam

U računarstvu, Hopcroft-Karp algoritam je algoritam koji kao ulaz ima bipartitni graf, a kao izlaz daje uparivanje sa maksimalnim brojem grana, najveći skup grana koje nemaju zajedničke krajnje tačke. Vremenska složenost algoritma je O {\displaystyle O} u najgorem slučaju, gde je E {\displaystyle E} skup grana, a V {\displaystyle V} skup čvorova grafa. U slučaju gustih grafova složenost postaje ključna O {\displaystyle O}, za slučajne grafove je linearna. Algoritam su razvili John Hopcroft i Richard Karp. Kao i prethodni algoritmi koji se odnose na uparivanje kao sto su Madarski algoritam i rad Edmonds-a, Hopcroft-Karp algoritam stalno povećava veličinu delimičnog uparivanja pronalaženjem alternirajućih puteva. Medutim, umesto da pronalazi samo jedan alternirajući put po iteraciji, algoritam pronalazi maksimalni skup najkraćih alternirajućih puteva. Kao rezultat toga samo O {\displaystyle O} iteracija je potrebno. Isti princip je korišćen pri razvijanju složenijih algoritama za ne-bipartitno uparivanje sa istom asimptotskom složenošću kao i Hopcroft-Karp algoritam.

                                     

1. Alternirajući putevi

Teme koje ne pripada grani koja se nalazi u skupu delimično uparenih grana M {\displaystyle M}, se zove slobodnoneupareno teme. Osnovni koncept na kom se algoritam zasniva je vezan za alternirajuće puteve, puteve koji počinju i završavaju se neuparenim čvorom, a naizmenično prolaze kroz grane koje su ušle u skup uparenih i kroz one koje nisu. Broj grana na tom putu mora biti neparan, jer pocinje i završava se neuparenim čvorom. Neka je E {\displaystyle E} skup čvorova sa njihovim granama, a M {\displaystyle M} skup uparenih čvorova sa njihovim granama. Alternirajući put P {\displaystyle P} za dato uparivanje M {\displaystyle M} je put izmedu dva neuparena čvora, pri čemu su grane puta P {\displaystyle P} naizmenično u E / M {\displaystyle E/M}, odnosno M {\displaystyle M}. Broj grana koje pripadaju skupu E / M {\displaystyle E/M} ima za jedan više nego onih koje pripadaju skupu M {\displaystyle M}. Prema tome, ako iz uparivanja izbacimo sve grane koje pripadaju skupu M {\displaystyle M}, a ubacimo sve one koje pripadaju skupu E / M {\displaystyle E/M}, dobićemo uparivanje sa jednom granom više. Jasno je da ako za dato uparivanje postoji alternirajući put, onda ono nije optimalno. Ispostavlja se da je i obrnuto tvrdenje tačno. Uparivanje je optimalno ako i samo ako nema alternirajući put.

Alternirajući put u problemu uparivanja je blisko povezan sa alternirajućim putevima u problemu maksimalnog protoka. Moguće je transformisati problem bipartitnog uparivanja u primer problema maksimalnog protoka, tako sto alternirajući putevi u problemu uparivanja postanu alternirajući putevi u problemu protoka. U stvari, generalizacija tehnike koja se koristi u Hopcroft-Karp algoritmu je poznata kao Dinic algoritam.

Input: Bipartite graph G U ∪ V, E {\displaystyle GU\cup V,E} Output: Matching M ⊆ E {\displaystyle M\subseteq E} M ← ∅ {\displaystyle M\leftarrow \emptyset } repeat P ← { P 1, P 2, …, P k } {\displaystyle {\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots,P_{k}\}} maksimalan skup čvorova koji ne pripadaju najkraćim alternirajućim putevima M ← M ⊕ P 1 ∪ P 2 ∪ ⋯ ∪ P k {\displaystyle M\leftarrow M\oplus P_{1}\cup P_{2}\cup \dots \cup P_{k}} until P = ∅ {\displaystyle {\mathcal {P}}=\emptyset }
                                     

2. Algoritam

Neka U {\displaystyle U} i V {\displaystyle V} budu dva skupa u bipartitnom grafu G {\displaystyle G}, i neka se uparivanje iz U {\displaystyle U} u V {\displaystyle V} u bilo koje vreme može predstaviti kao skup M {\displaystyle M}. Algoritam se radi u fazama. Svaka faza se sastoji od sledećih koraka.

  • Algoritam pronalazi maksimalan skup čvorova koji ne pripadaju alternirajućim putevima dužine k {\displaystyle k}. Ovaj skup može biti napravljen DFS pretragom iz F {\displaystyle F} do slobodnih čvorova iz U {\displaystyle U}, korišćenjem BFS slojeva kao vodič, DFS pretragom možemo proći kroz grane koje vode do neposećenih čvorova na prethodnom sloju, a DFS stablo sadrži naizmenično uparene i neuparene grane. Čim je pronaden alternirajući put koji sadrži jedan od čvorova iz F {\displaystyle F}, DFS pretraga se nastavlja iz sledećeg početnog čvora.
  • Svaki od puteva koji je pronaden na ovaj način se koristi za uvećanje M {\displaystyle M}.
  • Svi slobodni čvorovi iz V {\displaystyle V} na sloju k {\displaystyle k} se nalaze u skupu F {\displaystyle F}. Cvor v {\displaystyle v} se nalazi u F {\displaystyle F} ako i samo ako je kraj najkraćeg alternirajućeg puta.
  • BFS pretraga deli particije čvorova grafa na slojeve. Slobodni čvorovi iz U {\displaystyle U} se koriste kao polazna temena za pretragu, i formira se prvi sloj particije. Tokom prvog nivoa pretrage možemo proći samo kroz neuparene ivice pošto slobodni čvorovi iz U po definiciji ne pripadaju uparenim granama, u narednim nivoima pretrage, prolazićemo naizmenično kroz uparene i neuparene grane. Prilikom traženja susednih čvorova počev od čvorova iz U {\displaystyle U}, možemo proći jedino kroz neuparene grane, dok iz čvorova koji pripadaju V {\displaystyle V} možemo proći samo kroz uparene grane. Pretraga se završava na prvom sloju K {\displaystyle K} gde su pronadeni jedan ili više slobodnih čvorova iz V {\displaystyle V}.

Algoritam se završava kada BFS pretragom nije pronaden ni jedan alternirajući put.

                                     

3. Analiza

Svaka faza se sastoji od jedne BFS pretrage i jedne DFS pretrage. Dakle, vremenska složenost jedne faze je linearna. Složenost prvih | V | {\displaystyle {\sqrt {|V|}}} faza u grafu sa | V | {\displaystyle |V|} čvorova i | E | {\displaystyle |E|} grana je O | E | | V | {\displaystyle O|E|{\sqrt {|V|}}}. Može se pokazati da svaka faza povećava dužinu najkraćeg alternirajućeg puta za najmanje jedan, faza pronalazi maksimalan skup alternirajućih puteva zadate dužine, tako da ostali alternirajući putevi moraju biti duži. Zato, kada se početnih | V | {\displaystyle {\sqrt {|V|}}} faza algoritma završi, preostali najkraći alternirajući put ima najmanje | V | {\displaystyle {\sqrt {|V|}}} grana.Medutim, simetrična razlika eventualno optimalnog uparivanja i delimičnog uparivanja M {\displaystyle M} tokom prvih faza formira kolekciju čvorova i grana koje su disjunktne alternirajućim putevima i naizmeničnim ciklusima. Ukoliko je svaki put u kolekciji bar dužine | V | {\displaystyle {\sqrt {|V|}}}, može biti najvise | V | {\displaystyle {\sqrt {|V|}}} puteva u kolekciji, i velicina optimalnog uparivanja se može razlikovati od velicine M {\displaystyle M} za najvise | V | {\displaystyle {\sqrt {|V|}}} grana. Pošto svaka faza algoritma povećava veličinu uparivanja za barem jedan, može postojati najviše | V | {\displaystyle {\sqrt {|V|}}} dodatnih faza pre nego što se algoritam završi. Pošto algoritam ima najviše 2 | V | {\displaystyle 2{\sqrt {|V|}}} faza, njegova složenost je u najgorem slučaju O | E | | V | {\displaystyle O|E|{\sqrt {|V|}}}. U mnogim slučajevima,algoritam ima bolju vremensku složenost. Na primer, u prosečnom slučaju, za slučajne oskudne bipartitne grafove, Bast et al. Je pokazao da sa velikom verovatnoćom sva neoptimalna uparivanja imaju alternirajuće puteve logaritamske dužine. Kao posledica, za ove grafove, Hopcroft-Karp algoritam ima O log ⁡ | V | {\displaystyle O\log |V|} faza, a ukupna složenost je O | E | log ⁡ | V | {\displaystyle O|E|\log |V|}.



                                     

4. Ne-bipartitni grafovi

Ista ideja o pronalaženju maksimalnog skupa najkraćih alternirajućih puteva se koristi i za pronalaženje maksimalnog uparivanja u ne-bipartitnim grafovima, i iz istih razloga, algoritam baziran na ovoj ideji ima O | V | {\displaystyle O{\sqrt {|V|}}} faza. Medutim, za ne-bipartitne grafove je teže pronaći alternirajuće puteve u svakoj fazi. Nadovezujući se na rad nekoliko sporijih prethodnika, Micali i Vazirani 1980 su pokazali kako se može implementirati pojedinačna faza sa linearnom složenošću, što je rezultovalo algoritmom koji ima istu vremensku složenost kao Hopcroft-Karp algoritam za bipartitne grafove. Micali-Vazirani tehnika je kompleksna i njeni autori nemaju kompletan dokaz, alternativne metode za ovaj problem su kasnije opisali drugi autori.

                                     
  • 1982 Кен Томпсон  Денис Ричи 1983 Никлаус Вирт 1984 Ричард Карп 1985 Џон Хопкрофт Роберт Тарџан 1986 Џон Кок 1987 Ајван Садерланд 1988 Вилијам

Users also searched:

...