Stralerov broj
U matematici, Stralerov broj () 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 (), pri čemu dodeljujemo brojeve svakom čvoru u ()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.

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.  opisuje aplikaciju primenljivu u analizi socijalnih mreža. Takođe je primnljivo u biologiji kod grananja drveća  i kod resipiratornog trakta i cirkulatornog sistema.

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.  Algoritam koji potrebnu optimizaciju stablo matematičkog izraza je Seti–Ulmanov algoritam.

Reference

Literatura 
 .
 .
 .
 .
 .
 .

Vidi još 
 Seti–Ulmanov algoritam

Бројеви
Теорија графова
U matematici , Stralerov broj ( ) ili Horton-Stralerov broj predstavlja kompleksnost grananja stabla ( teorija grafova ) . Brojevi su prvi put primenjeni u Hidrologiji osmišljeni od strane Roberta E . Hortonai Artur Njuvel Stralera 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 ( ) , pri čemu dodeljujemo brojeve svakom čvoru u ( ) 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 − i barem četiri potomka sa stralerovim brojem i − itd ... I barem −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 . 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 jedok drug stabla imaju manji stepen bifurkacije . Druge aplikacije Stralerov broj je primenljiv na statističku analizu hijearhije bilo kog sistema , ne samo reka. opisuje aplikaciju primenljivu u analizi socijalnih mreža . Takođe je primnljivo u biologiji kod grananja drveća i kod resipiratornog trakta i cirkulatornog sistema . 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 . Algoritam koji potrebnu optimizaciju stablo matematičkog izraza je Seti–Ulmanov algoritam . Reference Literatura \ . \ . \ . \ . \ . \ . Vidi još Seti–Ulmanov algoritam Бројеви Теорија графова