Ojlerov obilazak

Ojlerov obilazak, nazvan po Leonardu Ojleru, je način predstavljanja stabala u teoriji grafova. Stablo se posmatra kao usmereni graf koji sadrži dve usmerene grane za svaku granu u stablu. Stablo onda može biti predstavljeno kao Ojlerov kružni put usmerenog grafa, poznat kao predstavljanje stabla Ojlerovim obilaskom (eng. ETR). Uveden je od strane Tajrana i Viškina 1984. god.

Konstrukcija

Za dato neusmereno stablo predstavljeno skupom ivica, predstavljanje stabla Ojlerovim obilaskom se može konstruisati na sledeći način:

• Konstruišemo simetričnu listu usmerenih grana:

for svaka neusmerena grana (u,v) u stablu do
                          ubaci (u,v) u listu grana; 
                          ubaci (v,u) u listu grana; 

• Sortirati listu grana leksikografski (Pretpostavljamo da su čvorovi stabla numerisani redom, i da je koren prvi element u tom redosledu).
• Konstruisati liste susedstva za svaki čvor (next) i mapu od čvorova do prvih ulaza listi susedstva (first):

 for svaka grana (u,v) u listi do
                  if za prethodnu granu (x,y) x != u //  počinje od drugog čvora
                          postavi first(u) = (u,v); 
                  else if x = u //  počinje od istog čvora
                          postavi next(x,y) = (u,v); 

Konstruisati listu grana (succ) u redosledu Ojlerovog obilaska postavljanjem pokazivača succ(u,v) za sve grane (u,v) uporedo na sledeći način:

$succ(u,v)={\begin{cases}next(v,u),&{\mbox{next(v,u) }}\neq {\mbox{ nil}}\\first(v),&{\mbox{inace}}\end{cases}}$

Rezultujuća lista biće kružna.

Vremenska složenost je W(n)=O(sort(n)) (vreme potrebno za uporedo sortiranje n stavki) ukoliko stablo ima n čvorova (broj grana je za jedan manji od broja čvorova).

Koreni, napredujuće i nazadujuće grane

Ukoliko stablo ima koren, možemo podeliti kružnu listu succ na mestu korena. U tom slučaju, možemo govoriti o napredujućim i nazadujućim granama: za dat par čvorova u,v, prvo pojavljivanje bilo (u,v) ili (v,u) u ETR-u je napredujuća grana, a drugo pojavljivanje je nazadujuća grana. Intuicijski gledano prvi put je takav da se pri obilasku grane razdaljina od korena povećava, a drugi put se razdaljina smanjuje.

Aplikacije

Izmena korena stabla se može izvesti za konstantno vreme O(1), razdvajanjem kružne liste succ na mestu novog korena. Svi od navedenih problema se mogu rešiti za O(Prefix sum(n)) (vreme potrebno za rešavanje problema prefiksne sume liste od n stavki):

1. Klasifikovanje napredujućih i nazadujućih grana: Uraditi rang liste ETR-a i čuvati rezultat u dvodimenzionom nizu A. Onda je (u,v) napredujuća grana ako je A(u,v) < A(v,u) i nazadujuća grana inače.
2. Određivanje nivoa svakog čvora: Uraditi prefiksnu sumu ETR-a, gde se svaka napredujuća grana računa kao 1, a nazadujuća kao -1. Onda je vrednost napredujuće grane (u,v) nivo čvora v.
3. Broj čvorova u podstablu sa korenom u čvoru v: Odrediti uporedo napredujuću granu (u,v) i nazadujuću granu (u,v), i onda odrediti broj napredujućih grana između (u,v) i (u,v) korišćenjem prefiksne sume.
4. DFS (pretraga u dubinu) indeks čvora v: Odrediti broj napredujućih grana unapred uključujući i (u,v).