Ојлеров обилазак

Ојлеров обилазак, назван по Леонарду Ојлеру, је начин представљања стабала у теорији графова. Стабло се посматра као усмерени граф који садржи две усмерене гране за сваку грану у стаблу. Стабло онда може бити представљено као Ојлеров кружни пут усмереног графа, познат као представљање стабла Ојлеровим обиласком (енг. ЕТР). Уведен је од стране Тајрана и Вишкина 1984. год.

Конструкција

За дато неусмерено стабло представљено скупом ивица, представљање стабла Ојлеровим обиласком се може конструисати на следећи начин:

• Конструишемо симетричну листу усмерених грана:

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

• Сортирати листу грана лексикографски (Претпостављамо да су чворови стабла нумерисани редом, и да је корен први елемент у том редоследу).
• Конструисати листе суседства за сваки чвор (неxт) и мапу од чворова до првих улаза листи суседства (фирст):

 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); 

Конструисати листу грана (суцц) у редоследу Ојлеровог обиласка постављањем показивача суцц(у,в) за све гране (у,в) упоредо на следећи начин:

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

Резултујућа листа биће кружна.

Временска сложеност је W(н)=О(сорт(н)) (време потребно за упоредо сортирање н ставки) уколико стабло има н чворова (број грана је за један мањи од броја чворова).

Корени, напредујуће и назадујуће гране

Уколико стабло има корен, можемо поделити кружну листу суцц на месту корена. У том случају, можемо говорити о напредујућим и назадујућим гранама: за дат пар чворова у,в, прво појављивање било (у,в) или (в,у) у ЕТР-у је напредујућа грана, а друго појављивање је назадујућа грана. Интуицијски гледано први пут је такав да се при обиласку гране раздаљина од корена повећава, а други пут се раздаљина смањује.

Апликације

Измена корена стабла се може извести за константно време О(1), раздвајањем кружне листе суцц на месту новог корена. Сви од наведених проблема се могу решити за О(Префиx сум(н)) (време потребно за решавање проблема префиксне суме листе од н ставки):

1. Класификовање напредујућих и назадујућих грана: Урадити ранг листе ЕТР-а и чувати резултат у дводимензионом низу А. Онда је (у,в) напредујућа грана ако је А(у,в) < А(в,у) и назадујућа грана иначе.
2. Одређивање нивоа сваког чвора: Урадити префиксну суму ЕТР-а, где се свака напредујућа грана рачуна као 1, а назадујућа као -1. Онда је вредност напредујуће гране (у,в) ниво чвора в.
3. Број чворова у подстаблу са кореном у чвору в: Одредити упоредо напредујућу грану (у,в) и назадујућу грану (у,в), и онда одредити број напредујућих грана између (у,в) и (у,в) коришћењем префиксне суме.
4. ДФС (претрага у дубину) индекс чвора в: Одредити број напредујућих грана унапред укључујући и (у,в).