Strahler-Filosofov nummer

Strahler- numret , Horton-Strahler- numret eller Strahler-filosofiska numret [1] för ett matematiskt träd  är ett numeriskt mått på förgreningskomplexitet.

Dessa siffror introducerades först i hydrologi av Robert Horton [2] 1945. Strahler [3] [4] och, oberoende av varandra, Filosofov föreslog att man skulle använda en dikotom uppdelning av floder i ordnar (som föreslog av Horton), men de antog inte en kanalomkodningsprocedur för att identifiera systemets huvudfloder [1] . I den här applikationen kallas siffrorna för Strahlers strömordning och används för att bestämma storleken på en ström baserat på en hierarki av bifloder . Siffror förekommer också i analysen av L-system och i hierarkiska biologiska strukturer som (biologiska) träd och andnings- och cirkulationssystemen, i distributionen av register vid sammanställningen av högnivåprogrammeringsspråk och i analysen av sociala nätverk . Shreve [5] [6] och Hodgkinsons grupp [7] utvecklade ett alternativt flödesordningssystem ] . En statistisk jämförelse av Strahler- och Shreve-systemen, tillsammans med en analys av flödeslängderna, gavs av Smart [8] .

Definition

Alla träd i artikelns sammanhang är riktade grafer riktade från roten till löven. Med andra ord, de är riktade träd . Graden av en nod i ett träd är helt enkelt antalet ättlingar till noden. Du kan tilldela Strahler-nummer till alla noder i trädet från botten till toppen enligt följande:

Strahler-numret för ett träd är lika med Strahler-numret för dess rotnod.

Algoritmiskt kan dessa nummer tilldelas genom att utföra en djupsökning först och tilldela varje nod ett Strahler-nummer i omvänd ordning . Samma siffror kan genereras genom beskärning, där trädet förenklas genom en rad steg. Vid varje steg tas alla dinglande noder och alla banor med grad ett som leder till löv bort – nodens Strahler-nummer är lika med stegnumret vid vilket noden tas bort, och trädets Strahler-nummer är lika med antalet steg som krävs för att ta bort alla noder. En annan likvärdig Strahler-definition av ett träd är höjden på det största kompletta binära trädet som kan vara homeomorft kapslat i ett givet träd. Strahler-numret för en nod i ett träd är analogt med höjden på det största kompletta trädet som kan kapslas under den noden.

Varje nod med Strahler nummer i måste ha minst två barn med Strahler nummer i  − 1, minst fyra barn med Strahler nummer i  − 2, etc., och minst 2 i  − 1 blad barn. I ett träd med n noder är alltså det största värdet på Strahler-talet log 2  n  + 1 [9] . Men om trädet inte bildar ett fullständigt binärt träd kommer dess Strahler-nummer att vara mindre än detta värde. I ett binärt träd med n noder, valt slumpmässigt bland alla möjliga binära träd med enhetlig sannolikhet , är det förväntade rotindexet mycket nära log 4  n [10] [9] med hög sannolikhet .

Applikationer

Flodnätverk

I Strahlers tillämpning av flödesordningar inom hydrologi, behandlas varje segment av en bäck eller flod som en nod i ett träd. När två första ordningens strömmar slås samman bildar de en andra ordningens ström . När andra ordningens flöden slås samman bildar de ett tredje ordningens flöde . När strömmar av lägre ordning smälter samman till en ström av högre ordning, ändras inte strömningsordningarna. Således, om en första ordningens ström smälter samman till en andra ordningens ström, förblir den andra ordningen en andra ordningens ström. Men om ett flöde av andra ordningen smälter samman till ett flöde av samma ordning, blir det andra ett flöde av tredje ordningen. Sålunda, för matematiska träd, måste segmentet med index i ha minst 2 i  − 1 distinkta ordningskällor 1. Shreve noterade att Hortons och Strahlers lagar är att förvänta i varje topologiskt slumpmässig fördelning. Efterföljande studier av sambanden bekräftade dessa argument och fastställde att strukturen eller källorna till flödena inte kunde förklaras [7] [11] .

Vattenflödet måste vara (som ett hydrologiskt fenomen) antingen tillfälligt eller inte tillfälligt . Intermittenta (eller "intermittenta") bäckar har vatten i sin kanal bara en del av året. Flödesindexet kan variera från 1 (flöde utan bifloder) till 12 (kraftigaste floder som Amazonas vid dess mynning). Ohio har en ordning på 8, och Mississippi har en ordning på 10. Cirka 80 % av planetens flöden uppskattas ha en ordning på ett till tre [12]

Om vattenflödenas bifurkationsförhållande är lågt, så finns det en stor risk för översvämning, eftersom vattnet kommer att samlas i en kanal och inte sprids, som i fallet med ett högt bifurkationsförhållande. Bifurkationskvoten kan också visa vilka delar av avrinningsområdet som är farligare (i fråga om möjligheten till översvämning). De flesta floder i Storbritannien har bifurkationsförhållanden mellan 3 och 5 [13] .

Glazer, Denisyuk, Rimmer och Salingar [14] beskrev hur man beräknar Strahlers flödesordningsvärde i GIS . Denna algoritm är implementerad i RivEX- systemet, ett ArcGIS 10.2.1- verktygssystem från ESRI. Ingången till deras algoritm är ett nätverk av centrala linjer av vattenflöden, representerade av bågar (eller kanter) som förbinder noder. Sjögränser och flodbankar bör inte användas som bågar, eftersom de i allmänhet bildar ett nätverk med oregelbunden topologi.

Andra hierarkiska system

Strahler-numrering kan tillämpas på den statistiska analysen av alla hierarkiska system, inte bara floder.

Registertilldelning

När man översätter programmeringsspråk på hög nivå till assemblerspråk är det minsta antalet register som krävs för att exekvera ett uttrycksträd exakt lika med dess Strahler-nummer. I detta sammanhang kan Strahler-numret kallas antalet register [19] [20] .

För uttrycksträd som kräver fler register än vad som är tillgängligt kan Seth-Ullman-algoritmen användas för att konvertera uttrycksträdet till en sekvens av maskininstruktioner som använder register så effektivt som möjligt, vilket minimerar antalet mellanregisterskrivningar till huvudminnet och det totala antalet antal instruktioner i kompilerad kod.

Relaterade parametrar

Bifurkationsrelation

Relaterade till Strahler-talen för träd är bifurkationsrelationer som beskriver hur nära ett träd är ett balanserat träd. För varje ordning i i hierarkin är den i -te bifurkationsrelationen

,

där n i betyder antalet noder av ordning i .

Som bifurkationskvoten för hela hierarkin kan vi ta medelvärdet av bifurkationskvoterna. I ett komplett binärt träd kommer bifurkationsförhållandet att vara 2, men andra träd kommer att ha ett mindre bifurkationsförhållande. Bifurkationsförhållandet är en dimensionslös storhet.

Spårbredd

Vägbredden för en godtycklig oriktad graf G kan definieras som det minsta antalet w så att det finns en intervallgraf H som innehåller G som en subgraf så att den största klicken av H har w  + 1 hörn. För träd (behandlas som oriktade grafer genom att ignorera orientering och rot), kan vägbredden skilja sig från Strahler-talet, men är nära relaterat till det - i ett träd med en vägbredd w och ett Strahler-tal s , är dessa två storheter relaterade till ojämlikhet [21]

w ≤ s ≤ 2 w + 2.

Möjligheten att arbeta med grafer som har en cykel, och inte bara med träd, ger vägbredden ytterligare flexibilitet jämfört med Strahler-numret. Men till skillnad från Strahler-numret definieras vägbredden endast för hela grafen, inte för varje nod i grafen.

Anteckningar

  1. ↑ 1 2 Ananiev, Simonov, Spiridonov, 1992 , sid. 102.
  2. ↑ Horton, 1945 .
  3. ↑ Strahler, 1952 .
  4. ↑ Strahler, 1957 .
  5. ↑ Shreve, 1966 , sid. 17–37.
  6. ↑ Shreve, 1967 , sid. 178–186.
  7. ↑ 1 2 Hodgkinson, McLoughlin, Cox, 2006 , sid. 394–407.
  8. ↑ Smart, 1968 , sid. 1001–1014.
  9. ↑ 1 2 Devroye, Kruszewski, 1996 .
  10. ↑ Devroye, Kruszewski, 1995 .
  11. ↑ Kirchner, 1993 , sid. 591–594.
  12. ↑ Strömordning - Klassificeringen av bäckar och floder . Hämtad: 11 december 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 och Schlund ( Luttenberger, Schlund 2011 ) använde en definition av "dimensionen" av ett träd, vilket är en mindre än Strahler-talet.

Litteratur