Back

ⓘ Ojlerov obilazak




Ojlerov obilazak
                                     

ⓘ 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. Uveden je od strane Tajrana i Viškina 1984. god.

                                     

1. 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 listu grana;
  • Konstruisati liste susedstva za svaki čvor next i mapu od čvorova do prvih ulaza listi susedstva first
  • Sortirati listu grana leksikografski Pretpostavljamo da su čvorovi stabla numerisani redom, i da je koren prvi element u tom redosledu.
for svaka grana u,v u listi do if za prethodnu granu x,y x!= u // počinje od drugog čvora postavi firstu = u,v; else if x = u // počinje od istog čvora postavi nextx,y = u,v;

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

s u c u, v = { n e x t v, u, nextv,u ≠ nil f i r s t v, inace {\displaystyle succu,v={\begin{cases}nextv,u,&{\mbox{nextv,u }}\neq {\mbox{ nil}}\\firstv,&{\mbox{inace}}\end{cases}}}

Rezultujuća lista biće kružna.

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

                                     

2. 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 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.

                                     

3. Aplikacije

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

  • 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.
  • Odredivanje 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.
  • 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 izmedu u,v i u,v korišćenjem prefiksne sume.
  • DFS pretraga u dubinu indeks čvora v: Odrediti broj napredujućih grana unapred uključujući i u,v.


                                     
  • описује моделе овог типа објављен је 2007. године заједно са решењем. Ојлерова карактеристика Мебијусове траке је нула. Мебијусова трака има неколико
  • 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

Users also searched:

...