Strahler-Filosofov szám

Egy matematikai fa Strahler -száma , Horton-Strahler- száma vagy Strahler-filozófiai száma [1]  az elágazás összetettségének numerikus mértéke.

Ezeket a számokat először Robert Horton [2] vezette be a hidrológiában 1945-ben. Strahler [3] [4] és egymástól függetlenül Filosofov a folyók dichotóm rendekre való felosztását javasolta (ahogyan Horton javasolta), de nem fogadtak el egy csatorna átkódolási eljárás a rendszer fő folyóinak azonosítására [1] . Ebben az alkalmazásban a számokat Strahler-patak sorrendjének nevezik, és egy patak méretének meghatározására szolgál a mellékfolyók hierarchiája alapján . A számok megjelennek az L-rendszerek elemzésében és a hierarchikus biológiai struktúrákban, mint a (biológiai) fák, valamint a légző- és keringési rendszerek, a regiszterek elosztásában a magas szintű programozási nyelvek összeállításánál , valamint a közösségi hálózatok elemzésében . . Shreve [5] [6] és Hodgkinson csoportja [7] alternatív áramlási rend rendszert dolgozott ki ] . A Strahler és Shreve rendszerek statisztikai összehasonlítását az áramlási hosszok elemzésével együtt Smart [8] adta meg .

Definíció

A cikkben szereplő összes fa a gyökértől a levelekig irányított grafikon . Más szóval, irányított fák . Egy fa csomópontjának foka egyszerűen a csomópont leszármazottainak száma. Strahler-számokat rendelhet a fa összes csomópontjához alulról felfelé az alábbiak szerint:

Egy fa Strahler-száma megegyezik gyökércsomópontjának Strahler-számával.

Algoritmikusan ezek a számok hozzárendelhetők úgy, hogy végrehajtunk egy mélységi keresést , és minden csomóponthoz hozzárendelünk egy Strahler-számot fordított sorrendben . Ugyanezek a számok metszéssel is előállíthatók, amelynek során a fa egy sor lépéssel egyszerűsödik. Minden lépésnél eltávolítják az összes lógó csomópontot és az összes, levelekhez vezető első fokú utat – a csomópont Strahler-száma megegyezik azzal a lépésszámmal, amelynél a csomópontot eltávolították, a fa Strahler-száma pedig egyenlő a szükséges lépések számával. távolítsa el az összes csomópontot. A fa egy másik ekvivalens Strahler-definíciója a legnagyobb teljes bináris fa magassága, amely homeomorf módon beágyazható egy adott fába. Egy fa csomópontjának Strahler-száma analóg a legnagyobb teljes fa magasságával, amely a csomópont alá ágyazható.

Minden i -es Strahler-számú csomópontnak legalább két i  -1-es Strahler-számú, legalább négy i  -2-es Strahler-számú gyermeknek kell lennie, stb., és legalább 2 i  -1- levelű gyermeknek. Így egy n csomópontú fában a Strahler-szám legnagyobb értéke log 2  n  + 1 [9] . Ha azonban a fa nem alkot teljes bináris fát, akkor a Strahler-száma kisebb lesz ennél az értéknél. Egy n csomóponttal rendelkező bináris fában, amelyet véletlenszerűen választunk ki az összes lehetséges bináris fa közül, egyenletes valószínűséggel , a várható gyökérindex nagy valószínűséggel nagyon közel van a log 4 n -hez [10] [9] .  

Alkalmazások

Folyóhálózat

Strahler áramlási sorrendjének hidrológiában történő alkalmazása során a patak vagy folyó minden szegmensét a fa csomópontjaként kezelik. Amikor két elsőrendű adatfolyam egyesül, egy második rendű adatfolyamot alkotnak . Amikor a másodrendű folyamok egyesülnek, harmadrendű folyamot alkotnak . Amikor az alacsonyabb rendű folyamok magasabb rendű folyamokká egyesülnek, a folyamok sorrendje nem változik. Így, ha egy elsőrendű adatfolyam egy másodrendű adatfolyamba egyesül, a második folyam másodrendű adatfolyam marad. De ha egy másodrendű áramlás összeolvad egy azonos rendű áramlással, akkor a második egy harmadik rendű folyammá válik. Így a matematikai fák esetében az i indexű szegmensnek legalább 2 i  − 1 különálló 1. sorrendi forrással kell rendelkeznie. Shreve megjegyezte, hogy Horton és Strahler törvényei minden topológiailag véletlenszerű eloszlásban elvárhatók. Az összefüggések későbbi vizsgálatai megerősítették ezeket az érveket, és megállapították, hogy az áramlások szerkezete vagy forrásai nem magyarázhatók [7] [11] .

A vízáramlásnak (mint hidrológiai jelenségnek) vagy efemernek, vagy nem efemernek kell lennie . Az időszakos (vagy "szakaszos") patakok csatornájában csak az év egy részében van víz. Az áramlási index 1-től (mellékfolyók nélküli áramlás) 12-ig terjedhet (a legerősebb folyók, mint például az Amazon a torkolatánál). Ohióban 8-as, Mississippiben pedig 10-es nagyságrendű. A bolygó fluxusainak körülbelül 80%-a a becslések szerint egy-három nagyságrendű [12].

Ha a vízáramlások bifurkációs aránya alacsony, akkor nagy az elöntés esélye, mivel a víz egy csatornában gyűlik össze, és nem oszlik szét, mint a magas bifurkációs arány esetén. A bifurkációs arány azt is megmutathatja, hogy a vízgyűjtő mely részei veszélyesebbek (az elöntés lehetőségét tekintve). A legtöbb brit folyó bifurkációs aránya 3 és 5 között van [13] .

Glazer, Denisyuk, Rimmer és Salingar [14] leírták, hogyan kell kiszámítani a Strahler-féle áramlási sorrend értékét a GIS -ben . Ezt az algoritmust a RivEX rendszerben, az ESRI ArcGIS 10.2.1 -es eszközrendszerében valósították meg. Algoritmusuk bemenete a vízáramlások központi vonalainak hálózata, amelyeket csomópontokat összekötő ívek (vagy élek) képviselnek. A tóhatárokat és a folyópartokat nem szabad ívként használni, mivel általában szabálytalan topológiájú hálózatot alkotnak.

Egyéb hierarchikus rendszerek

A Strahler-számozás bármely hierarchikus rendszer statisztikai elemzésére alkalmazható, nem csak a folyók esetében.

Regisztráció kiosztása

Magas szintű programozási nyelvek assembly nyelvre történő fordításakor a kifejezésfa végrehajtásához szükséges minimális regiszterszám pontosan megegyezik a Strahler-számmal. Ebben az összefüggésben a Strahler-szám a regiszterek számának nevezhető [19] [20] .

A rendelkezésre állónál több regisztert igénylő kifejezésfák esetében a Seth-Ullman algoritmus használható a kifejezésfa gépi utasítások sorozatává alakítására, amely a lehető leghatékonyabban használja a regisztereket, minimalizálva a köztes regiszterek főmemóriába történő írásának számát és a teljes utasítások száma a lefordított kódban.

Kapcsolódó paraméterek

Bifurkációs reláció

A fák Strahler-számaihoz kapcsolódnak bifurkációs relációk , amelyek leírják, hogy egy fa milyen közel van egy kiegyensúlyozott fához. A hierarchiában minden i rendre az i -edik bifurkációs reláció az

,

ahol n i az i rendű csomópontok számát jelenti .

A teljes hierarchia bifurkációs arányaként a bifurkációs arányok átlagát vehetjük fel. Egy teljes bináris fában az elágazási arány 2 lesz, de más fáknak kisebb a bifurkációs aránya. A bifurkációs arány dimenzió nélküli mennyiség.

Nyomtáv

Egy tetszőleges irányítatlan G gráf útvonala a legkisebb w számként definiálható úgy, hogy van egy H intervallumgráf , amely G -t részgráfként tartalmazza úgy, hogy H legnagyobb klikkjének w  + 1 csúcsa van . A fák esetében (amelyeket irányítatlan gráfként kezelnek az orientáció és a gyökér figyelmen kívül hagyásával) az útvonal szélessége eltérhet a Strahler-számtól, de szorosan összefügg vele - egy w útvonalszélességű és s Strahler -számú fában ez a két mennyiség a egyenlőtlenség [21]

w ≤ s ≤ 2 w + 2.

Az a képesség, hogy nem csak fákkal, hanem ciklussal rendelkező grafikonokkal is dolgozhatunk, további rugalmasságot ad az útvonalnak a Strahler-számhoz képest. A Strahler-számtól eltérően azonban az útvonal szélessége csak a teljes gráfra van definiálva, nem a gráf egyes csomópontjaira.

Jegyzetek

  1. ↑ 1 2 Ananiev, Simonov, Spiridonov, 1992 , p. 102.
  2. ↑ Horton, 1945 .
  3. ↑ Strahler, 1952 .
  4. ↑ Strahler, 1957 .
  5. ↑ Shreve, 1966 , p. 17–37.
  6. ↑ Shreve, 1967 , p. 178–186.
  7. ↑ 1 2 Hodgkinson, McLoughlin, Cox, 2006 , p. 394–407.
  8. ↑ Okos, 1968 , p. 1001–1014.
  9. ↑ 1 2 Devroye, Kruszewski, 1996 .
  10. ↑ Devroye, Kruszewski, 1995 .
  11. ↑ Kirchner, 1993 , p. 591–594.
  12. ↑ Patakok sorrendje – A patakok és folyók osztályozása . Letöltve: 2011. december 11.
  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 és Schlund ( Luttenberger, Schlund 2011 ) egy fa "dimenziójának" definícióját használta, amely eggyel kisebb, mint a Strahler-szám.

Irodalom