Strahler-Filosofovo číslo

Strahlerovo číslo , Horton-Strahlerovo číslo nebo Strahlerovo-filozofické číslo [1] matematického stromu  je numerickou mírou složitosti větvení.

Tato čísla byla poprvé zavedena v hydrologii Robertem Hortonem [2] v roce 1945. Strahler [3] [4] a nezávisle Filosofov navrhli použít dichotomické rozdělení řek do řádů (jak navrhl Horton), ale nepřijali postup překódování kanálů k identifikaci hlavních řek systému [1] . V této aplikaci se čísla nazývají Strahlerovo pořadí toků a používají se k určení velikosti toku na základě hierarchie přítoků . Čísla se také objevují v analýze L-systémů a v hierarchických biologických strukturách, jako jsou (biologické) stromy a dýchací a oběhové systémy, v distribuci registrů při kompilaci programovacích jazyků na vysoké úrovni a v analýze sociálních sítí. . Shreve [5] [6] a Hodgkinsonova skupina [7] vyvinuli alternativní systém uspořádání toku ] . Statistické srovnání systémů Strahler a Shreve spolu s analýzou délek proudění provedl Smart [8] .

Definice

Všechny stromy v kontextu článku jsou orientované grafy směřující od kořene k listům. Jinými slovy, jsou to řízené stromy . Stupeň uzlu ve stromu je jednoduše počet potomků uzlu. Strahlerova čísla můžete přiřadit všem uzlům stromu zdola nahoru následovně:

Strahlerovo číslo stromu se rovná Strahlerovu číslu jeho kořenového uzlu.

Algoritmicky lze tato čísla přiřadit provedením hloubkového vyhledávání a přiřazením každého uzlu Strahlerovo číslo v opačném pořadí . Stejná čísla lze vygenerovat prořezáváním, při kterém se strom zjednoduší řadou kroků. V každém kroku jsou odstraněny všechny visící uzly a všechny cesty se stupněm jedna vedoucí k listům – Strahlerovo číslo uzlu se rovná číslu kroku, ve kterém je uzel odstraněn, a Strahlerovo číslo stromu se rovná počtu kroků potřebných k odstranit všechny uzly. Další ekvivalentní Strahlerova definice stromu je výška největšího kompletního binárního stromu , který může být homeomorfně vnořen do daného stromu. Strahlerovo číslo uzlu ve stromu je analogické výšce největšího úplného stromu, který lze pod daným uzlem vnořit.

Každý uzel se Strahlerovým číslem i musí mít alespoň dvě děti se Strahlerovým číslem i  − 1, alespoň čtyři děti se Strahlerovým číslem i  − 2 atd. a alespoň 2 i  − 1 listové děti. Ve stromu s n uzly je tedy největší hodnota Strahlerova čísla log 2  n  + 1 [9] . Pokud však strom netvoří úplný binární strom, jeho Strahlerovo číslo bude menší než tato hodnota. V binárním stromu s n uzly, vybranými náhodně ze všech možných binárních stromů s jednotnou pravděpodobností , je očekávaný kořenový index velmi blízký log 4  n [10] [9] s vysokou pravděpodobností .

Aplikace

Říční síť

Ve Strahlerově aplikaci tokových řádů v hydrologii je každý segment potoka nebo řeky považován za uzel stromu. Když se dva toky prvního řádu sloučí, vytvoří tok druhého řádu . Když se toky druhého řádu sloučí, vytvoří tok třetího řádu . Když se proudy nižšího řádu spojí do proudu vyššího řádu, pořadí proudů se nezmění. Pokud se tedy tok prvního řádu spojí do toku druhého řádu, druhý tok zůstane tokem druhého řádu. Ale pokud se tok druhého řádu spojí s tokem stejného řádu, druhý se stane tokem třetího řádu. Pro matematické stromy tedy musí mít segment s indexem i alespoň 2 i  − 1 odlišné zdroje řádu 1. Shreve poznamenal, že Hortonovy a Strahlerovy zákony lze očekávat v jakémkoli topologicky náhodném rozdělení. Následné studie souvislostí tyto argumenty potvrdily a prokázaly, že strukturu nebo zdroje toků nelze vysvětlit [7] [11] .

Proudění vody musí být (jako hydrologický jev) buď efemérní, nebo ne efemérní . Přerušované (nebo „přerušované“) toky mají vodu ve svém kanálu pouze část roku. Index průtoku se může pohybovat od 1 (průtok bez přítoků) do 12 (nejmocnější řeky, jako je Amazonka u jejího ústí). Ohio má řád 8 a Mississippi řád 10. Odhaduje se, že asi 80 % toků planety má řád jeden až tři [12].

Pokud je poměr rozvětvení vodních toků nízký, existuje vysoká pravděpodobnost zaplavení, protože voda se bude shromažďovat v jednom kanálu a nebude se rozptylovat, jako v případě vysokého poměru rozvětvení. Bifurkační poměr může také ukázat, které části povodí jsou nebezpečnější (z hlediska možnosti záplav). Většina řek v Británii má bifurkační poměry mezi 3 a 5 [13] .

Glazer, Denisyuk, Rimmer a Salingar [14] popsali, jak vypočítat Strahlerovu hodnotu řádu toku v GIS . Tento algoritmus je implementován v systému RivEX , nástrojovém systému ArcGIS 10.2.1 od ESRI. Vstupem do jejich algoritmu je síť centrálních linií vodních toků, reprezentovaných oblouky (nebo hranami) spojujícími uzly. Hranice jezer a břehy řek by neměly být používány jako oblouky, protože obecně tvoří síť s nepravidelnou topologií.

Jiné hierarchické systémy

Strahlerovo číslování lze aplikovat na statistickou analýzu jakéhokoli hierarchického systému, nejen řek.

Registrovat přidělení

Při překladu programovacích jazyků na vysoké úrovni do jazyka symbolických instrukcí se minimální počet registrů potřebných k provedení stromu výrazů přesně rovná jeho Strahlerovu číslu. V této souvislosti lze Strahlerovo číslo nazvat počtem registrů [19] [20] .

Pro stromy výrazů vyžadujících více registrů, než je k dispozici, lze použít Seth-Ullmanův algoritmus k převodu stromu výrazů na sekvenci strojových instrukcí, které používají registry co nejefektivněji, čímž se minimalizuje počet zápisů mezilehlých registrů do hlavní paměti a celkový počet instrukcí v kompilovaném kódu.

Související parametry

Bifurkační vztah

Se Strahlerovými čísly pro stromy souvisí bifurkační vztahy , které popisují, jak blízko je strom k vyváženému stromu. Pro každý řád i v hierarchii je i -tý bifurkační vztah

,

kde n i znamená počet uzlů řádu i .

Jako bifurkační poměr celé hierarchie můžeme vzít průměr bifurkačních poměrů. V úplném binárním stromu bude poměr bifurkace 2, ale ostatní stromy budou mít poměr bifurkace menší. Bifurkační poměr je bezrozměrná veličina.

Šířka stopy

Šířku cesty libovolného neorientovaného grafu G lze definovat jako nejmenší číslo w takové, že existuje intervalový graf H obsahující G jako podgraf tak, že největší klika z H má w  + 1 vrcholů. U stromů (zacházených jako neorientované grafy ignorováním orientace a kořene) se šířka cesty může lišit od Strahlerova čísla, ale úzce s ním souvisí - ve stromu se šířkou cesty w a Strahlerovým číslem s jsou tyto dvě veličiny ve vztahu pomocí nerovnost [21]

w ≤ s ≤ 2 w + 2.

Schopnost pracovat s grafy, které mají cyklus, a nejen se stromy, dává šířce cesty další flexibilitu ve srovnání se Strahlerovým číslem. Na rozdíl od Strahlerova čísla je však šířka cesty definována pouze pro celý graf, nikoli pro každý uzel v grafu.

Poznámky

  1. ↑ 1 2 Ananiev, Simonov, Spiridonov, 1992 , str. 102.
  2. ↑ Horton, 1945 .
  3. ↑ Strahler, 1952 .
  4. ↑ Strahler, 1957 .
  5. ↑ Shreve, 1966 , str. 17–37.
  6. ↑ Shreve, 1967 , str. 178–186.
  7. ↑ 1 2 Hodgkinson, McLoughlin, Cox, 2006 , str. 394–407.
  8. ↑ Smart, 1968 , str. 1001–1014.
  9. ↑ 1 2 Devroye, Kruszewski, 1996 .
  10. ↑ Devroye, Kruszewski, 1995 .
  11. ↑ Kirchner, 1993 , s. 591–594.
  12. ↑ Pořadí toků – Klasifikace toků a řek . Staženo: 11. prosince 2011.
  13. ↑ Waugh, 2002 .
  14. ↑ Gleyzer, Denisyuk, Rimmer, Salingar, 2004 .
  15. ↑ Arenas, Danon, Díaz-Guilera, Gleiser, Guimerá, 2004 .
  16. ↑ Ehrenfeucht, Rozenberg, Vermeir, 1981 .
  17. ↑ Borchert, Slade, 1981 .
  18. ↑ Horsfield, 1976 .
  19. ↑ Ershov, 1958 .
  20. ↑ Flajolet, Raoult, Vuillemin, 1979 .
  21. ↑ Luttenberger a Schlund ( Luttenberger, Schlund 2011 ) použili definici „rozměru“ stromu, která je o jednu menší než Strahlerovo číslo.

Literatura