Stralerov broj

С Википедије, слободне енциклопедије
Dijagram prikazuje redosled Stralerovog toka

U matematici, Stralerov broj (engl. Strahler number) ili Horton-Stralerov broj predstavlja kompleksnost grananja stabla (teorija grafova).

Brojevi su prvi put primenjeni u Hidrologiji osmišljeni od strane Roberta E. Hortona (1945) i Artur Njuvel Stralera (1952, 1957). Poznati su i kao Stralerova veličina toka i koriste se da opišu tok reke u zavisnosti od njene hijearhije pritoka (manje reke koje se ulivaju u veću). Takođe se sreću u analizi hijearhije bioloških struktura kao što su (biološko) drvo, respiratorni trakt, cirkulatorni sistem, u alokaciji procesorskih registra pri kompilaciji programskih jezika visokog nivoa i u analizi društvenih mreža

Abstraktna stabla[уреди | уреди извор]

Sva stabla u ovom kontekstu predstavljaju orijentisani graf ili digraf. Graf je orijentisan od korena prema listovima. Podsetimo se stepen čvora stabla predstavlja broj njegove dece. Svakom čvoru možemo dodeliti alternativni broj, Stralerov broj krećući se odozdo na gore i poštujući sledći patern:

  • Stralerov broj svih listova je jedan.
  • Ako deca čvora imaju različite Stralerove brojeve s1, s2, s3, ... ,sn onda je Stralerov broj = max{s1, s2, s3, ... ,sn} (maksimum od brojeva dece)
  • Ako sva deca imaju isti Stralerov broj recimo n onda je Stralerov broj čvora za jedan veći to jest =n+1.

Stralerov broj stabla predstavlja Stralerov broj korena stabla.

Algoritamski ovi brojevi mogu biti dodeljeni preko metoda Pretrage u dubinu (engl. Depth-first search - DFS), pri čemu dodeljujemo brojeve svakom čvoru u (engl. postorder)redosledu.

Još jedan pristup bi bio da se korak po korak numerišu pa odsecaju čvorovi najnižeg stepena. U tom slučaju broj poslednjeg koraka odsecanja bi predstavljao Stralerov broj stabla.

Još jedna ekvivalentna definicija Stralerovog broja stabla je da predstavlja visinu kompletnog binarnog stabla koje se može ugnježditi u originalno stablo kao homeomorfizam. Isto definišemo Stralerov broj čvora kao kompletno binarno stablo koje se kao homeomorfizam može ugraditi ispod tog čvora.

Svaki čvor sa Stralerovim brojem i mora da ima bar dva potomka sa Stralerovim brojem i − 1, i barem četiri potomka sa stralerovim brojem i − 2, itd... I barem 2i − 1 listova. Iz toga sledi da kompletno binarno stablo sa n čvorova Stralerov broj log2 n, dok za stabla koja nisu striktno kompletna važi da će Stralerov broj biti ≤ log2 n. Takođe pokazano je da je velika verovatnoća da će random generisano binarno stablo imati Stralerov broj vrlo blizu log4 n. [1]

Odnos bifurkacije (račvanja)[уреди | уреди извор]

Povezano sa Stralerovim brojem stabla je i odnos bifurkacije (račvanja). To jest broj koji opisuje koliko je stablo balansirano. Za svaki stepen i u hijearhiji i-to račvanje je:

gde ni predstavlja broj čvorova stpena i.

Odnos bifurkacije cele hijearhije se može izmeriti kao računanje proseka bifurkacije izračunate za različite stepene. U potpunom binarnom stablu stepen bifurkacije je 2 dok drug stabla imaju manji stepen bifurkacije.

Druge aplikacije[уреди | уреди извор]

Stralerov broj je primenljiv na statističku analizu hijearhije bilo kog sistema, ne samo reka. Arenas et al. 2004 opisuje aplikaciju primenljivu u analizi socijalnih mreža. Takođe je primnljivo u biologiji kod grananja drveća [2] i kod resipiratornog trakta i cirkulatornog sistema.[3]

Pri prevođenju programskih jezika visokog nivoa u asembler minimalni broj procesorskih registara potrebnih za evaluiranje stabla koje sadrži matematički izraz je upravo Stralerov broj. [4] Algoritam koji potrebnu optimizaciju stablo matematičkog izraza je Seti–Ulmanov algoritam.

Reference[уреди | уреди извор]

  1. ^ Devroye & Kruszewski 1995
  2. ^ Borchert & Slade 1981
  3. ^ Horsfield 1976
  4. ^ Flajolet, Raoult & Vuillemin 1979

Literatura[уреди | уреди извор]

  • Arenas, A.; Danon, L.; Díaz-Guilera, A.; Gleiser, P. M.; Guimerá, R. (2004), „Community analysis in social networks”, The European Physical Journal B - Condensed Matter and Complex Systems, 38 (2): 373—380, doi:10.1140/epjb/e2004-00130-1 .
  • Borchert, Rolf; Slade, Norman A. (1981), „Bifurcation ratios and the adaptive geometry of trees”, Botanical Gazette, 142 (3): 394—401, JSTOR 2474363, doi:10.1086/337238 .
  • Devroye, Luc; Kruszewski, Paul (1995), „A note on the Horton-Strahler number for random trees”, Information Processing Letters, 56 (2): 95—99, doi:10.1016/0020-0190(95)00114-R .
  • Gleyzer, A.; Denisyuk, M.; Rimmer, A.; Salingar, Y. (2004), „A fast recursive GIS algorithm for computing Strahler stream order in braided and nonbraided networks”, Journal of the American Water Resources Association, 40 (4): 937—946, doi:10.1111/j.1752-1688.2004.tb01057.x .
  • Lanfear, K. J. (1990), „A fast algorithm for automatically computing Strahler stream order”, Journal of the American Water Resources Association, 26 (6): 977—981, doi:10.1111/j.1752-1688.1990.tb01432.x .
  • Waugh, David (2002), Geography, An Integrated Approach (3rd изд.), Nelson Thornes .

Vidi još[уреди | уреди извор]