Dinamičko povezivanje

U računarstvu i teoriji grafova, struktura dinamičkog povezivanja je struktura podataka koja dinamički održava informacije o komponentama povezanosti grafa.

Skup čvorova V grafa je nepromenljiv, a skup grana E se može menjati. Tri slučaja za promenu skupa E, poređana po težini, su:

• Dodavanje grana u graf (može se nazivati inkrementno povezivanje);
• Brisanje grana iz grafa (može se nazivati dekrementno povezivanje);
• Dodavanje ili brisanje grana iz grafa (može se nazivati potpuno dinamičko povezivanje).

Nakon svakog dodavanja/brisanja grane, struktura dinamičkog povezivanja bi trebalo da se adaptira tako da može davati brze odgovore na upite tipa "da li postoji put između čvorova x i y?" (ekvivalentno: "da li čvorovi x i y pripadaju istoj komponenti povezanosti?").

Inkrementno povezivanje

Ako se grane mogu samo dodavati, problem dinamičkog povezivanja se može rešiti pomoću strukture disjunktnog skupa podataka. Svaki skup predstavlja komponentu povezanosti; postoji put između čvorova x i y ako i samo ako pripadaju istom skupu. Vremenska složenost operacije je $O(\alpha (n))$, gde je n broj čvorova, a α inverzna Akermanova funkcija, koja je približno konstantna.

Dekrementno povezivanje

Problem u slučaju u kome se grane mogu samo brisati su rešili Shimon Even i Yossi Shiloach.

Struktura koristi tabelu koja određuje, za svaki čvor, ime svake komponente kojoj pripada. Dakle, upit povezivanja zahteva konstantno vreme. Izazov je ažurirati tabelu kada je grana obrisana.

Aciklični grafovi (šume)

Kada je grana u-v obrisana iz šume, stablo, koje je sadržalo tu granu, je podeljeno na dva stabla: jedno od njih sadrži čvor u, a drugo sadrži čvor v. Tabela se ažurira na sledeći način.

• Pretraži stablo počevši od čvora u (koristeći bilo koji algoritam za pretragu, kao što je DFS).
• Pretraži stablo počevši od čvora v.
• Izvrši gore navedene korake paralelno, bilo pomoću dva paralelna procesa ili preplitanjem njihovih koraka (napravi korak prve pretrage, zatim korak druge pretrage, zatim korak prve pretrage i tako dalje).
• Pretpostavimo da je prva pretraga koja se zaustavi pretraga iz čvora u (tako da znamo da je stablo koje sadrži čvor u manje). Dodeli novo ime komponente svakom čvoru u podstablu u.

Pošto se svaki put manjoj potkomponenti menja ime, vremenska složenost za operaciju brisanja je $O(\log(n))$.

Opšti grafovi

Kada je grana izbrisana iz opšteg grafa, ne znamo da li graf ostaje povezan (jedna komponenta povezanosti) ili nepovezan (podeljen na dve komponente). Koristimo dva procesa koja rade paralelno (ili na ispreplitan način). Proces A proverava da li brisanje deli komponentu povezanosti i ako deli, oba procesa se zaustavljaju. Proces B proverava da li brisanje grane ne deli komponentu kojoj grana pripada i ako ne deli, oba procesa se zaustavljaju.

Proces A je sličan slučaju acikličnih grafova: postoje dva potprocesa koja obilaze graf sa oba kraja obrisane grane. Ako jedan od potprocesa završi pre nego što dođe do drugog kraja, ovo znači da je komponenta podeljena na dve potkomponente i naziv manje potkomponente je ažuriran, kao i ranije. Dakle, vremenska složenost operacije brisanja je opet $O(\log(n))$.

Proces B koristi strukturu obilaska u širinu (BFS) koja je inicijalizovana na sledeći način. Izabran je čvor r i BFS obilazak kreće od njega. Jedini čvor u nivou 0 je r. . Svi čvorovi udaljeni od korena za dužinu i su u nivou i. Ako graf G nije povezan, počinje se novi obilazak iz nekog neposećenog čvora v, v se stavlja u nivo 1 i nova, veštačka grana povezuje v sa korenom r; svi čvorovi na rastojanju dužine i od čvora v su sada na nivou i 1, itd. Veštačke grane se uvode kako bi sve komponente povezanosti bile prisutne u BFS stablu i koriste se isključivo u ovu svrhu. Očigledno, veštačke grane se koriste samo u procesu B.

Struktura ima sledeće karakteristike. Čvor v koji je u nivou i, i>0, ima tri vrste grana: povratne grane, koje ga povezuju sa nivoom i-1 (postoji bar jedna takva grana i može biti veštačka), poprečne grane, koje ga povezuju sa drugim granama u nivou i (postoji nula ili više takvih grana) ili direktne grane, koje ga povezuju sa granama u nivou i 1 (postoji nula ili više takvih grana). Za svaki čvor v, održavamo tri tipa grana (povratne, poprečne i direktne).

Kada je grana u-v obrisana, postoje dve opcije: ili su čvorovi u i v u istom nivou ili su u nivoima koji se razlikuju za 1.

Slučaj 1: čvorovi u i v su u istom nivou. U ovom slučaju brisanje ne može da promeni komponente. Grana je jednostavno obrisana iz skupa poprečnih grana, i proces B se zaustavlja (i proces A se zaustavlja). Struktura obilaska u širinu je i dalje validna.

Slučaj 2: čvorovi u i v su na različitim nivoima. Bez gubitka opštosti pretpostavljamo da je čvor u na nivou i-1, a čvor v na nivou i; otuda, trebalo bi ukloniti po granu iz skupa diretnih grana iz čvora u i iz skupa povratnih grana iz čvora v.

Slučaj 2.1: Ako novi skup povratnih grana iz čvora v nije prazan, onda se komponente povezanosti nisu promenile: postoje druge grane koje povezuju v povratno. Proces B se zaustavlja, kao i proces A.

Slučaj 2.2: Ako novi skup povratnih grana iz čvora v' jeste prazan, onda v nije više povezan sa nivoom i-1, tako da njegova udaljenost od korena nije više i; mora biti najmanje i 1. Dodatno, moraju postojati i drugi čvorovi povezani sa v, čije se udaljenosti od korena uvećavaju kao posledica brisanja. Da bismo izračunali ažurirane udaljenosti, koristimo red Q, koji inicijalno sadrži samo čvor v.

While Q nije prazan:

1. w := dequeue(Q)
2. Izbaci w sa njegovog nivoa (npr. j), i stavi ga na sledeći nivo (j 1).
3. Ažuriraj lokalne susede:
   • Za svaku granu w-x iz skupa poprečnih grana iz čvora w, obriši je iz skupa poprečnih grana iz čvora x i stavi u skup direktnih grana iz x.
   • Skupu povratnih grana iz w dodeli vrednost skupa poprečnih grana iz w.
4. Ažuriraj direktne susede:
   • Za svaku granu w-x iz skupa direktnih grana iz w, obriši je iz skupa povratnih grana iz čvora x i stavi u skup poprečnih grana iz x; ako je novi skup povratnih grana iz x prazan, stavi x na red Q.
   • Skupu poprečnih grana iz w dodeli vrednost skupa direktnih grana iz w.
   • Skupu direktnih grana iz w dodeli prazan skup.
5. Ako je novi skup povratnih grana iz w prazan, opet stavi w na red Q.

Ako brisanje grane ne slomi ni jednu komponentu i mi smo u slučaju 2.2, onda se vremenom procedura zaustavlja. U ovom slučaju je lako videti da BFS struktura ostaje pravilno održavana. Ako njeno brisanje slomi komponentu, onda se procedura neće zaustaviti sama od sebe. Ipak, proces A, prepoznajući lomljenje, će se zaustaviti i oba procesa će se zaustaviti. U ovom slučaju sve izmene napravljene u BFS strukturi se ignorišu i vraćamo se na BFS strukturu koju smo imali pred brisanje, osim sto je obrisana grana zamenjena veštačkom. Očigledno je da je u ovom slučaju v koren stabla koji sadrži novu komponentu i možda dodatne komponente, ili neke druge veštačke grane. Takođe, nema grana koje povezuju pretke čvora v sa bilo kojim čvorovima koji nisu preci čvora v, osim veštačke grane u-v.

Kad god je grana obrađena u proceduri, nivo jednog od njenih krajeva opadne za jedan. Kako je najniži nivo koji čvor može dostići u pokretanjima koje zaustavlja proces B |V|-1, cena po grani je ograničena sa 2|V|. Stoga je vremenska složenost po operaciji brisanja $O(n)$.

Potpuno dinamičko povezivanje

Aciklični grafovi (šume)

Šuma može biti predstavljena ili kolekcijom link-cut stabala ili stabala Ojlerovog obilaska. Tada problem dinamičkog povezivanja može biti rešen lako, pošto za svaka dva čvora x, y, x je povezan sa y ako i samo ako PronađiKoren(x) = PronađiKoren(y). Vremenska složenost ažuriranja i vreme upita su O(log(n)).

Opšti grafovi

Opšti graf može biti predstavljen svojim razapinjućim stablom – stablom koje sadrži podstablo za svaku komponentu povezanosti grafa. Ovo nazivamo razapinjućim stablom F. F može biti predstavljen šumom stabala Ojlerovog obilaska.

Operacije upita i dodavanja su implementirane korišćenjem odgovarajućih operacija nad ET stablima koje predstavljaju F. Operacija koje je najveći izazov je brisanje, konkretnije, brisanje grane koja je sadržana u jednom od razapinjućih stabala od F. Ovo lomi razapinjuće stablo na dva stabla, ali je moguće da postoji druga grana koja ih povezuje. Izazov je brzo naći takvu granu, ako ona postoji. Ovo zahteva kompleksniju strukturu podataka. Nekoliko ovakvih struktura su opisane ispod.

Nivo struktura

Svakoj grani grafa se dodeljuje nivo. Neka je L=lg n. Nivo svake grane dodate u grafu je inicijalizovan na L i može opadati ka 0 tokom operacija brisanja.

Za svako i između 0 i L, definiši Gi kao podgraf, sadržan od grana koje su na nivoima i ili niže, i Fi kao razapinjuće stablo Gi. Naša šuma F od ranije se sad naziva FL. Nastavićemo da umanjujemo sekvencu šuma FL ⊆ ... ⊆ F0.

Operacije

Operacije upita i ubacivanja koriste samo najveće šume FL.Manji podgrafovi se koriste samo pri operaciji brisanja, konkretno, brisanjem grane koja je sadržana u jednom od razapinjućih stabala od FL.

Kada je takva grana e = x-y obrisana, prvo je uklonjena iz FL FL i iz svih manjih razapinjućih stabala kojima pripada, na primer iz svakog Fi gde je i veće ili jednako nivou grane e. Onda tražimo granu kojom ćemo je zameniti.

Počinjemo od najmanjeg razapinjućeg stabla šume koja je sadržala e, naime, Fi gde je i jednako nivou grane e. Grana e pripada određenom stablu T⊆Fi. Nakon brisanja grane e, stablo T je podeljeno na dva manja stabla: Tx koje sadrži čvor x i Ty koje sadrži čvor y. Grana iz Gi je grana koju ćemo uzeti kao zamenu ako i samo ako ona povezuje čvor u Tx sa čvorom u Ty. Pretpostavimo, bez gubitka opštosti, da je Tx manje stablo (npr. sadrži najviše pola čvorova iz T; možemo uvideti veličinu svakog podstabla preko beleške dodate u Ojlerova stabla).

Iteriramo preko svih čvorova ε sa nivoom i i sa bar jednim čvorom u Tx:

• Ako je drugi čvor ε u Ty, onda je grana za zamenu nađena. Dodaj ovu granu u Fi i sa svima koji sadrže šume do FL završi. Razapinjuće šume su popravljene.
• Ako je drugi čvor ε u Tx, onda ovo nije grana za zamenu i, kako bi je "kaznili" zbog utrošenog vremena, smanjimo joj nivo za jedan.

Analiza

Nivo svake grane će se smanjiti najviše lg n Zašto? Zato što svakim smanjenjem, stablo postaje duplo manje od stabla u prethodnom koraku. Tako je broj čvorova na nivou i, u svakoj komponenti povezanosti, najviše 2^i. Otuda je nivo svake grane bar 0.

Potrebno je $O(lgn)$ vremena da se pronađe grana čiji nivo treba biti umanjen (koristeći ET operacije stabla). Ukupno, za svaku umetnutu granu troši se $O(lg^{2}n)$ vremena za brisanje, pa je prosečno vreme brisanja grane $O(lg^{2}n)$. Preostali deo brisanja grana, takođe ima vremensku složenost $O(lg^{2}n)$, jer treba da obrišemo grane sa najviše $O(lgn)$ nivoa, a brisanje na svakom nivou ima vremensku složenost $O(lgn)$ (ponovo koristeći ET operacije stabla).

Ukupno, prosečna vremenska složenost ažuriranja je $O(lg^{2}n)$. Vremenska složenost po upitu se može poboljšati do $O(lgn/lglgn)$.

Međutim, u najgorem slučaju vremenska složenost ažuriranja može biti $O(n)$. Problem poboljšanja vremenske složenosti najgoreg slučaja je bilo otvoreno pitanje sve dok se nije pojavio bipartitni graf kao rešenje.

Bipartitni graf

Neka je dat graf G(V, E) i podskup čvorova T ⊆ V, bipartitni graf(T) definišemo kao skup grana koje povezuju skup čvorova T sa skupom čvorova V\T. Bipartitni graf je struktura podataka, koja, bez čuvanja celog grafa u memoriji, brzo pronalazi granu u bipartitnom grafu, ako takva grana postoji.

Svakom čvoru grafa se dodeljuje broj. Pretpostavimo da ima n čvorova; onda ćemo svaki čvor obeležiti brojem koji je zapisan u binarnom sistemu dužine lg(n). Zatim ćemo dodeliti broj svakoj grani; broj grane se dobija spajanjem brojeva svojih temena, zapisan je u binarnom sistemu dužine 2lg(n).

Za svaki čvor vse računa i čuva rezultat funkcije xor(v), koji se dobija primenjivanjem funkcije xor na sve brojeve grana susednih čvoru v.

Za svaki podskup čvorova T ⊆ V je sada moguće izračunati xor(T) = rezultat je broj koji se dobija primenjivanjem funkcije xor na sve brojeve čvorova skupa T. Razmotrimo sada granu e = u-v koja je unutrašnja grana skupa T (u i v pripadaju skupu T). Broj grane e je dva puta bio uključen u funkciju xor(T) – jednom za čvor u, a drugi put za čvor v. Kako je rezultat operacije xor primenjene na bilo koji broj sa samim sobom 0, onda grana e nestaje i ne utiče na xor(T). Dakle, xor(T) je zapravo xor primenjen na sve grane u bipartitnom grafu(T). Postoji nekoliko opcija:

• Ako je xor(T)=0, onda možemo potvrditi da je bipartitni graf (T) prazan skup.
• Ako je xor(T) broj koji odgovara nekoj stvarnoj grani e, verovatno je onda grana e jedina u bipartitnom grafu(T) i onda možemo vratiti e. Takođe, možemo pročitati krajnje čvorove grane e, tako što ćemo broj grane e podeliti na dva broja dužine lg(n).
• Treća opcija je kada xor(T) ne predstavlja broj nijedne postojeće grane stabla. Ovo se može desiti samo ako se u bipartitnom grafu(T) nalazi dve ili više grana, jer u tom slučaju xor(T) je xor od nekoliko brojeva različitih grana. Tada se prijavljuje "greška" pošto znamo da u strukturi postoji nekoliko grana, ali ne možemo da identifikujemo tačno jednu.

Sada nam je cilj da rešimo treću opciju.

Prvo se kreira sekvenca, od bipartitnog grafa, koja ima lg(n) nivoa, gde svaki nivo sadrži polovinu grana u odnosu na nivo iznad (tj. za svaki nivo se bira grana sa nivoa iznad sa verovatnoćom 1/2). Ako na prvom nivou xor(T) vrati nevažeću vrednost, to znači da bipartitni graf (T) ima dve ili više grana, i postoji šansa da na sledećem nivou, koji ima manje grana, xor(T) vrati važeću vrednost pošto će bipartitni graf (T) imati samo jednu granu. Ako xor(T) i dalje vraća nevažeću vrednost prelazimo na sledeći nivo, itd. Pošto se broj grana smanjuje, postoji dva slučaja:

• Dobar slučaj je kada nađemo nivo u kome bipartitni graf (T) sadrži samo jednu granu; tada vratimo tu granu i završavamo.
• Loš slučaj je kada pronađemo nivo u kome bipartitni graf (T) ne sadrži nijednu granu; tada prijavljujemo "grešku" pošto znamo da postoji više grana u bipartitnom grafu, ali ne možemo da identifikujemo tačno jednu.

Moguće je dokazati da je verovatnoća uspeha bar 1/9.

Potom kreiramo kolekciju C*lg(n) nezavisnih verzija nivoa strukture, gde je C konstanta. U svakoj verziji, uraditi nezavisno, slučajno uklanjanje grana po nivoima. Probati svaki upit na svakoj verziji sve dok jedna ne uspe. Verovatnoća da će sve verzije biti neuspešne je najviše: $(1-1/9)^{C\lg {n}}=2^{-0.17C\lg {n}}=n^{-0.17C}$ Pravilnim odabirom konstante C možemo verovatnoću neuspeha smannjiti do 0.

Operacije

Možemo dodati bipartitni graf u strukturu dinamičkog povezivanja.

Operacije dodavanja i brisanja u bipartitni graf se obavljaju na isti način: dodata/obrisana grana je XOR-ovana u oba njena čvora.

Kada se neka grana obriše iz razapinjućeg stabla koji se koristi u strukturi dinamičkog povezivanja, bipartitni graf se koristi kako bi se našla grana koja će zameniti obrisanu granu.

Analiza

Jedan bipartitni graf zahteva samo O(n*lg(n)) prostorne složenosti – samo jedan broj, dužine 2*lg(n) bita, za svaki od n čvorova. Za guste grafove, ovo je mnogo jeftinije nego čuvati čitav graf u memoriji.

Moramo čuvati lg(n) verzije, od kojih svaka sadrži lg(n) nivoa. Otuda, ukupna prostorna složenost je O(n lg^3 n).

Vremenska složenost upita je O(polylog(n)) u najgorem slučaju. Ovo je suprotno od strukture po nivoima, gde je prosečna vremenska složenost upita O(polylog(n)), a u najgorem slučaju O(n).

Vidi još

• Dynamic problem (algorithms)
• Partition refinement