Strahlerovo číslo - Strahler number

v matematika, Strahlerovo číslo nebo Horton – Strahlerovo číslo matematické strom je číselná míra jeho větvové složitosti.
Tato čísla byla poprvé vyvinuta v hydrologie podle Robert E. Horton (1945 ) a Arthur Newell Strahler (1952, 1957 ); v této aplikaci se označují jako Strahlerova objednávka proudu a slouží k definování velikosti proudu na základě hierarchie přítoky. Vznikají také při analýze L-systémy a hierarchických biologických struktur, jako jsou (biologické) stromy a respirační a oběhové systémy zvířat, v přidělení registru pro sestavení z programovací jazyky na vysoké úrovni a při analýze sociální sítě. Alternativní systémy pro objednávání streamů byly vyvinuty Shreve[1][2] a Hodgkinson et al.[3] Smart uvádí statistické srovnání systémů Strahler a Shreve spolu s analýzou délek stream / link.[4]
Definice
Všechny stromy v této souvislosti jsou řízené grafy, orientovaný od kořene směrem k listům; jinými slovy, jsou stromové scény. The stupeň uzlu na stromě je jen jeho počet dětí. Jeden může přiřadit Strahlerovo číslo všem uzlům stromu v pořadí zdola nahoru, a to následovně:
- Pokud je uzlem list (nemá žádné potomky), je jeho Strahlerovo číslo jedna.
- Pokud má uzel jedno dítě se Strahlerovým číslem ia všechny ostatní děti mají Strahlerovy počty menší než i, pak Strahlerovo číslo uzlu je i znovu.
- Pokud má uzel dvě nebo více dětí se Strahlerovým číslem i, a žádné děti s větším počtem, pak Strahlerovo číslo uzlu je i + 1.
Strahlerovo číslo stromu je číslo jeho kořenového uzlu.
Algoritmicky, tato čísla lze přiřadit provedením a hloubkové vyhledávání a přiřazení čísla každého uzlu postorder Stejná čísla lze také generovat pomocí procesu prořezávání, při kterém je strom zjednodušen v posloupnosti fází, kdy v každé fázi jeden odstraní všechny listové uzly a všechny cesty uzlů prvního stupně vedoucí k listům: Strahlerovo číslo uzlu je fáze, ve které by byl tímto procesem odstraněn, a Strahlerovo číslo stromu je počet fází potřebných k odstranění všech jeho uzlů. Další ekvivalentní definice Strahlerova čísla stromu je, že je to výška největšího kompletní binární strom to může být homeomorfně vložené do daného stromu; Strahlerovo číslo uzlu ve stromu je podobně výška největšího úplného binárního stromu, který lze vložit pod tento uzel.
Libovolný uzel se Strahlerovým číslem i musí mít alespoň dva potomky se Strahlerovým číslem i - 1, nejméně čtyři potomci se Strahlerovým číslem i - 2 atd. A alespoň 2i − 1 potomci listů. Proto na stromě s n uzly, největší možné Strahlerovo číslo je log2 n + 1.[5] Pokud však strom netvoří úplný binární strom, jeho Strahlerovo číslo bude menší než toto vázané. V n-uzel binární strom, zvoleno rovnoměrně náhodně mezi všemi možnými binárními stromy, očekávaný index kořene je s vysokou pravděpodobností velmi blízko logu4 n.[6]
Aplikace
Říční sítě
V aplikaci Strahler pořadí streamů hydrologicky je každý segment potoka nebo řeky v říční síti považován za uzel ve stromu, přičemž další segment po proudu je jeho mateřský. Když dva první objednávka proudy se spojují, tvoří a druhá objednávka proud. Když se dva proudy druhého řádu spojí, vytvoří a třetího řádu proud. Proudy nižšího řádu připojující se k proudu vyššího řádu nemění pořadí vyššího proudu. Pokud se tedy proud prvního řádu připojí k proudu druhého řádu, zůstane proudem druhého řádu. Teprve až se proud druhého řádu kombinuje s jiným proudem druhého řádu, stává se proudem třetího řádu. Stejně jako u matematických stromů, segment s indexem i musí být krmeny alespoň 2i − 1 různé přítoky indexu 1. Shreve poznamenal, že Hortonovy a Strahlerovy zákony lze očekávat od jakékoli topologicky náhodné distribuce. Pozdější revize vztahů tento argument potvrdila a stanovila, že z vlastností, které zákony popisují, nelze vyvodit žádný závěr, který by vysvětlil strukturu nebo původ datové sítě.[3][7]
Aby se hydrologický prvek kvalifikoval jako proud, musí být buď opakující se, nebo trvalka. Opakující se (nebo „přerušované“) toky mají vodu v kanálu alespoň po část roku. Index toku nebo řeky se může pohybovat od 1 (tok bez přítoků) do 12 (celosvětově nejmocnější řeka, Amazonka, u úst). The Ohio řeka je řádu osm a řeka Mississippi je řádu 10. Odhady jsou, že 80% proudů na planetě je prvního až třetího řádu toky horního toku.[8]
Pokud je poměr rozvětvení říční sítě nízký, pak existuje větší šance na zaplavení, protože voda bude spíše koncentrována v jednom kanálu než rozložena, jak by naznačoval vyšší poměr rozvětvení. Poměr bifurkace může také ukázat, které části povodí jsou pravděpodobně zaplaveny, a to porovnáním, při pohledu na jednotlivé poměry. Většina britských řek má poměr rozvětvení mezi 3 a 5.[9]

Gleyzer a kol. (2004) popsat, jak vypočítat hodnoty pořadí Strahlerova proudu v a GIS aplikace. Tento algoritmus implementuje RivEX, ESRI ArcGIS 10.6.1 nástroj. Vstupem do jejich algoritmu je síť středových linií vodních útvarů, představovaných jako oblouky (nebo hrany) spojené v uzlech. Hranice jezer a břehy řek by neměly být používány jako oblouky, protože obvykle tvoří nestromovou síť s nesprávnou topologií.
Jiné hierarchické systémy
Strahlerovo číslování lze použít při statistické analýze jakéhokoli hierarchického systému, nejen u řek.
- Arenas a kol. (2004) popsat aplikaci Horton-Strahlerova indexu při analýze sociální sítě.
- Ehrenfeucht, Rozenberg & Vermeir (1981) aplikovali variantu Strahlerova číslování (počínaje nulou u listů místo jednoho), kterou nazvali stromová hodnost, k analýze L-systémy.
- Strahlerovo číslování bylo také použito na biologické hierarchie, jako jsou větvící se struktury stromů[10] a dýchacích a oběhových systémů zvířat.[11]
Registrace přidělení
Při překladu a programovací jazyk na vysoké úrovni na montážní jazyk minimální počet registry k vyhodnocení výrazového stromu je zapotřebí přesně jeho Strahlerovo číslo. V této souvislosti lze Strahlerovo číslo také nazývat registrační číslo.[12]
U stromů výrazů, které vyžadují více registrů, než je k dispozici, Sethi – Ullmanův algoritmus lze použít k překladu stromu výrazů do posloupnosti strojových instrukcí, které používají registry co nejefektivněji, čímž se minimalizuje počet případů, kdy se mezilehlé hodnoty rozlijí z registrů do hlavní paměti, a celkový počet pokynů ve výsledném kompilovaném kódu.
Související parametry
Poměr bifurkace
Spojeno s Strahlerovými čísly stromu bifurkační poměry, čísla popisující, jak blízko je vyvážený strom. Pro každou objednávku i v hierarchii ipoměr bifurkace je
kde ni označuje počet uzlů s objednávkou i.
Poměr rozdvojení celkové hierarchie lze získat zprůměrováním poměrů rozdvojení v různých řádech. V úplném binárním stromu bude poměr bifurkace 2, zatímco jiné stromy budou mít větší bifurkační poměry. Je to bezrozměrné číslo.
Šířka cesty
The šířka cesty libovolného neorientovaný graf G lze definovat jako nejmenší číslo w takové, že existuje intervalový graf H obsahující G jako podgraf, s největším klika v H mít w + 1 vrcholy. U stromů (zobrazeno jako neorientované grafy zapomenutím na jejich orientaci a kořen) se šířka cesty liší od Strahlerova čísla, ale s ním úzce souvisí: ve stromu s šířkou cesty w a Strahlerovo číslo s, tato dvě čísla souvisejí s nerovnostmi[13]
- w ≤ s ≤ 2w + 2.
Schopnost zpracovávat grafy s cykly a nejen stromy dává šířce cesty extra univerzálnost ve srovnání s Strahlerovým číslem. Na rozdíl od Strahlerova čísla je však šířka cesty definována pouze pro celý graf a ne samostatně pro každý uzel v grafu.
Viz také
- Hlavní stopka řeky, obvykle nalezené sledováním větve s nejvyšším Strahlerovým číslem
Poznámky
- ^ Shreve, R.L., 1966. Statistický zákon čísel proudů. Geologický časopis 74, 17–37.
- ^ Shreve, R.L., 1967. Nekonečné topologicky náhodné kanálové sítě. Geologický časopis 75, 178–186.
- ^ A b Hodgkinson, J.H., McLoughlin, S. & Cox, M.E. 2006. Vliv strukturního zrna na drenáž v metamorfním dílčím povodí: Laceys Creek, jihovýchod Queensland, Austrálie. Geomorphology, 81: 394–407.
- ^ Inteligentní, J.S. 1968, Statistické vlastnosti délek toků, Výzkum vodních zdrojů, 4, č. 5. 1001–1014
- ^ Devroye & Kruszewski (1996).
- ^ Devroye a Kruszewski (1995, 1996 ).
- ^ Kirchner, J.W., 1993. Statistická nevyhnutelnost Hortonových zákonů a zdánlivá náhodnost sítí proudových kanálů. Geologie 21, 591–594.
- ^ „Řád toku - klasifikace toků a řek“. Citováno 2011-12-11.
- ^ Waugh (2002).
- ^ Borchert & Slade (1981)
- ^ Horsfield (1976).
- ^ Ershov (1958); Flajolet, Raoult a Vuillemin (1979).
- ^ Luttenberger & Schlund (2011) pomocí definice „dimenze“ stromu, která je o jeden menší než Strahlerovo číslo.
Reference
- Arenas, A .; Danon, L .; Díaz-Guilera, A .; Gleiser, P. M .; Guimerá, R. (2004), „Komunitní analýza v sociálních sítích“, Evropský fyzický deník B, 38 (2): 373–380, arXiv:cond-mat / 0312040, Bibcode:2004EPJB ... 38..373A, doi:10.1140 / epjb / e2004-00130-1, S2CID 9764926.
- Borchert, Rolf; Slade, Norman A. (1981), „Bifurkační poměry a adaptivní geometrie stromů“, Botanický věstník, 142 (3): 394–401, doi:10.1086/337238, hdl:1808/9253, JSTOR 2474363.
- Devroye, Luc; Kruszewski, Paul (1995), „Poznámka k číslu Horton – Strahler pro náhodné stromy“, Dopisy o zpracování informací, 56 (2): 95–99, doi:10.1016 / 0020-0190 (95) 00114-R.
- Devroye, L.; Kruszewski, P. (1996), „Na Hortonově – Strahlerově čísle pro náhodné pokusy“, RAIRO Informatique Théorique et Applications, 30 (5): 443–456, doi:10.1051 / ita / 1996300504431, PAN 1435732
- Ehrenfeucht, A.; Rozenberg, G.; Vermeir, D. (1981), „Na systémech ETOL s konečným stromovým hodnocením“, SIAM Journal on Computing, 10 (1): 40–58, doi:10.1137/0210004, PAN 0605602.
- Ershov, A. P. (1958), „O programování aritmetických operací“, Komunikace ACM, 1 (8): 3–6, doi:10.1145/368892.368907, S2CID 15986378.
- Flajolet, P.; Raoult, J. C .; Vuillemin, J. (1979), „Počet registrů požadovaných pro hodnocení aritmetických výrazů“, Teoretická informatika, 9 (1): 99–125, doi:10.1016/0304-3975(79)90009-4.
- Gleyzer, A .; Denisyuk, M .; Rimmer, A .; Salingar, Y. (2004), „Rychlý rekurzivní GIS algoritmus pro výpočet pořadí Strahlerova proudu v pletených a nepletených sítích“, Journal of the American Water Resources Association, 40 (4): 937–946, Bibcode:2004JAWRA..40..937G, doi:10.1111 / j.1752-1688.2004.tb01057.x.
- Horsfield, Keith (1976), „Některé matematické vlastnosti větvených stromů s aplikací na dýchací systém“, Bulletin of Mathematical Biology, 38 (3): 305–315, doi:10.1007 / BF02459562, PMID 1268383, S2CID 189888885.
- Horton, R. E. (1945), „Erozní vývoj toků a jejich povodí: hydrofyzikální přístup ke kvantitativní morfologii“, Bulletin americké geologické společnosti, 56 (3): 275–370, doi:10.1130 / 0016-7606 (1945) 56 [275: EDOSAT] 2.0.CO; 2.
- Lanfear, K. J. (1990), „Rychlý algoritmus pro automatické počítání Strahlerova proudu“, Journal of the American Water Resources Association, 26 (6): 977–981, Bibcode:1990JAWRA..26..977L, doi:10.1111 / j.1752-1688.1990.tb01432.x.
- Luttenberger, Michael; Schlund, Maxmilian (2011), Rozšíření Parikhovy věty za idempotenci, arXiv:1112.2864, Bibcode:2011arXiv1112.2864L
- Strahler, A. N. (1952), „Hypsometrická (plošně-nadmořská výška) analýza erozní topologie“, Bulletin americké geologické společnosti, 63 (11): 1117–1142, doi:10.1130 / 0016-7606 (1952) 63 [1117: HAAOET] 2.0.CO; 2.
- Strahler, A. N. (1957), „Kvantitativní analýza geomorfologie povodí“, Transakce Americké geofyzikální unie, 38 (6): 913–920, Bibcode:1957TrAGU..38..913S, doi:10.1029 / tr038i006p00913.
- Waugh, David (2002), Geografie, integrovaný přístup (3. vyd.), Nelson Thornes.