Algoritam maksimalnog uparivanja

Algoritam maksimalnog uparivanja (engl. Blossom algorithm) je algoritam u teoriji grafova i koristi se za konstruisanje maksimalnog poklapanja na grafu. Algoritam je otkrio Džek Edmonds 1961. godine, a objavio 1965. Posmatrajući neusmereni graf graph G = (V, E), algoritam pronalazi odgovarajuće M takvo da svaki čvor u V je zajednički sa najmanje jednom granom u M i |M| je uvećano. Uparivanje je zamišljeno kao iterativno popunjavanje inicijalno praznog uparivanja duž povećavajućeg puta u grafu.

Glavni razlog važnosti ovog algoritma je da je bio prvi dokaz da se maksimalno uparivanje može naći u polinomijalnom vremenu. Drugi razlog je što je doveo do linearnog programiranja polihedralnog opisa odgovarajućeg politopa, što je dalje dalo algoritam za minimalnu težinu podudaranja. Kako je obrazložio Aleksandar Šrijver, dalji značaj dolazi iz činjenice da je ovo prvi politop čiji dokaz integralnosti „ne dolazi samo iz ukupne unimodularnosti i njegov opis je bio napredak u poliedarskoj kombinatorici.“

Povećavajući put

Imajući u vidu G = (V, E) i odgovarajuće M iz G, čvor v je izdvojen, ako ne postoji ni jedna grana u M koja sadrži v. Put u G je naizmenični put, ako njegove grane naizmenično nisu u M i jesu u M (ili jesu u M i nisu u M). Povećavajući put P je naizmeničan put koji počinje i završava se u dva različita izdvojena čvora. Povećavajuće uparivanje duž povećavajućeg puta P je operacija zamene M novim podudaranjem $M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)$.

Možemo da dokažemo da je uparivanje M maksimalno akko nema daljeg M koje uvećva povećavajući put u G. Odatle sledi da, ili je uparivanje maksimalno, ili može biti povećano. Dakle, počev od inicijlnog uparivanja, možemo izračunati maksimalno uparivanje tako što ćemo povećavati trenutno upareno sa povećavajućim putem dokle god možemo da nađemo taj put, i vratimo se kad god ga ne nađemo. Možemo da formallizujemo algoritam na sledeći način:

   УЛАЗ:  Граф G, иницијално упаривање M на G
   ИЗЛАЗ: максимално упаривање M* на G
A1 function нађи_максимално_упаривање(G, M ) : M*
A2     P ← нађи_повећавајући_пут(G, M )
A3     if P је непразно then
A4          return нађи_максимално_упаривање(G, повећај M дуж P )
A5     else
A6          return M
A7     end if
A8 end function

Još nam je ostalo da opišemo kako efikasno možemo pronaći povećavajući put. Potprogram za to koristi cvetove(uklanjanje čvorova) i kontrahovanje (uklanjanje grane kako bi se dva čvora spojila u jedan).

Cvetovi i kontrahovanje

Imajući u vidu G = (V, E) i odgovarajuće M iz G, cvet B je ciklus u G koji se sastoji od 2k + 1 grane od kojih tačno k grana pripada M i gde jedno od temena v ciklusa (baza) je takvo da postoji naizmenični put jednake dužine (stabljika) od v do izdvojenog čvora w.

Definišemo kontrahovani graf G’ kao graf dobijen od G pomoću kontrahovanja svake grane iz B i definišemo kontrahovano uparivanje M’ kao uparivanje u G’ koje odgovara M.

Možemo pokazati da G’ ima povećavajući put M’ akko G ima povećavajući put M i da bilo koji povećavajući put M’ P’ u G’ može biti povećan do povećavajućeg puta M u G tako što će se poništiti kontrahovanje B-om, tako da segment iz P’ (ako postoji) obilaska v_B je zamenjen bilo kojim odgovarajućim segmentom obilaska B. Ili detaljnije:

• ako P’ obilazi segment u → v_B → w u G’, onda se ovaj segment menja segmentom u → (u’ → ... → w’ ) → w u G, gde cvetni čvorovi u’ i w’ i strana B, (u’ → ... → w’ ), od u’ do w’ su birani tako da bi se osiguralo da je novi put i dalje naizmeničan (u’ je izdvojeno po pravilu $M\cap B$, $\{w',w\}\in E\setminus M$).

• ako P’ ima krajnju tačku v_B, onda je segment puta u → v_B u G’ zamenjen segmentom u → (u’ → ... → v’ ) u G, gde cvetni čvorovi u’ i v’ i strana B, (u’ → ... → v’ ), od u’ do v’ su birani tako da bi se osiguralo da je novi put i dalje naizmeničan (v’ je izdvojeno, $\{u',u\}\in E\setminus M$).

Dakle, cvetovi mogu biti kontrahovani i pretraživanje se vrši u kontrahovanim grafovima. Ovo smanjenje je srž Edmondsovog algoritma.

Pronalaženje povećavajućeg puta

Potraga za povećavajućim putem koristi pomoćnu strukturu podataka koja se sastoji od šume F čija individualna stabla odgovaraju određenim delovima grafa G. U stvari, šuma F je ista koja će se koristiti za pronalaženje makimalnog uparivanja u bipartitnom grafu (bez potrebe za smanjenjem cvetova). U svakoj interakciji algoritam ili (1) pronađe povećavajući put, (2) pronađe cvet i rekurzivno poziva odgovarajući kontrahovani graf, ili (3) zaključi da nema povećavajućeg puta. Pomoćna struktura je izgrađena od povećavajućeg procesa o kome će se raspravljati u daljem tekstu.

Procedura konstrukcije uzima u obzir čvorove v i grane e u G i postepeno ažurira F po potrebi. Ako je v u stablu T šume, dozvolimo da koren(v) bude označen kao koren od T. Ako su oba u i v u istom stablu T u F, dozvolimo da razdaljina(u,v) budeo označena kao dužina jedinstvenog puta od u do v u T.

    УЛАЗ:  Граф G, упаривање M на G
    ИЗЛАЗ: повећавајући пут P у G или празна путања ако није нађена
B01 function нађи_повећавајући_пут(G, M ) : P
B02    F ← празна шума
B03    демаркирај све чворове и гране у G, означи све гране у M
B05    for each издвојени чвор v do
B06        направи singleton дрво { v } и додај дрво у F
B07    end for
B08    while постоји демаркиран чвор v у F са раздаљина(v, корен(v ) ) do
B09        while постоји демаркирана грана e = { v, w } do
B10            if w није у F then
                   // Ажурирај F.
B11                x ← чвор упарен са w у M
B12                додај гране { v, w } и { w, x } дрвету у v
B13            else
B14            if раздаљина(w, корен(w ) ) је непарна then
B15                не ради ништа
B16            else
B17            if корен(v ) ≠ корен(w ) then
                   // Пријави повећавајући пут у F $\cup$ { e }.
B18                P ← пут (корен(v ) → ... → v ) → (w → ... → корен(w ) )
B19                return P
B20            else
                   // Контрахуј цвет у G и потражи пут у контрахованом графу.
B21                B ← цвет формиран од e и грана у путу v → w у T
B22                G’, M’ ← контраховано G и M од B
B23                P’ ← нађи_повећавајући_пут(G’, M’ )
B24                P ← повећај P’ до G
B25                return P
B26            end if
B27            означи грану e
B28        end while
B29        означи чвор v
B30    end while
B31    return празан пут
B32 end function

Primeri

Naredne četiri slike ilustruju izvršenje algoritma. Isprekidane linije su korištene za predstavljanje grana koje trenutno nisu u šumi. Prvo, algoritam obrađuje grane na spoljnjem delu šume koje izaziva širenje trenutne šume (linije koda B10 - B12).

Dalje, algoritam detektuje cvet i kontrahue graf (linije B20 - B22).

Na kraju, locira povećavajući put P′ u kontrahovanom grafu (linija B23) i podiže ga na originalni graf (linija B24). Treba imati na umu da je od ključnog značaja sposobnost algoritma da kontrahuje cvetove; algoritam ne može da nađe P direktno u originalnom grafu jer samo spoljne grane šume između čvorova jednake razdaljine od korena ulaze u razmatranje u liniji koda B17 ovog algoritma.

Analiza

Šuma F konstruisana funkcijom nađi_povećavajući_put() je naizmenična šuma.

• stablo T u G je naizmenično stablo prema M, ako
  • T sadrži tačno jedan izdvojeni čvor r koji se zove koren stabla
  • svaki čvor na neparnom rastojanju od korena ima tačno dve odgovarajuće grane u T, i
  • sve putanje iz r u T imaju iste dužine, njegove neparne grane nisu u M, a njegove parne jesu u M.
• šuma F u G je naizmenična šuma prema M, ako
  • su njene spojene komponente naizmenična stabla, i
  • svaki izdvojeni čvor u G je koren naizmeničnog stabla u F.

Svaka iteracija petlje počevši od linije B09 ili dodaje stablu T u F (linija B10) ili pronalazi povećavajući put (linija B17) ili pronalazi cvet (linija B21). Sada vidimo da je vreme izvršavanja $O(|V|^{4})$. Mikali i Vazirani su predstavili algoritam koji konstruiše maksimalno uparivanje u $O(|E||V|^{1/2})$ vremenu.

Bipartitino uparivanje

Algoritam se svodi na standardni algoritam uparivanja u bipartitnim grafovima kada je G bipartitno. Kako nema neparnih ciklusa u G u tom slučaju cvetovi neće biti nađeni i zbog toga mogu biti uklonjene linije B21 - B29 ovog algoritma.

Težinsko podudaranje

Problem uparivanja može biti generalizovan dodeljivanjem težina granama u G i tražeći M koje će sačinjavati maksimalno (minimalno) uparivanje ukupne težine. Problem težinskog podudaranja može biti rešen kombinatornim algoritmom koji koristi netežinski Edmondsov algoritam kao potprogram. Kolmogorov je obezbedio efikasnu C++ implementaciju.

Literatura

• Schrijver, Alexander. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. 24. Springer.