Strahler-Filosofov nummer

Strahler -tallet , Horton-Strahler- tallet eller Strahler-filosofiske tal [1] for et matematisk træ  er et numerisk mål for forgrening kompleksitet.

Disse tal blev først introduceret i hydrologi af Robert Horton [2] i 1945. Strahler [3] [4] og uafhængigt af hinanden foreslog Filosofov at bruge en dikotom opdeling af floder i ordener (som foreslået af Horton), men de vedtog ikke en kanal omkodningsprocedure for at identificere systemets vigtigste floder [1] . I denne applikation kaldes tallene Strahlers strømrækkefølge og bruges til at bestemme størrelsen af ​​en strøm baseret på et hierarki af bifloder . Tal optræder også i analysen af ​​L-systemer og i hierarkiske biologiske strukturer såsom (biologiske) træer og de respiratoriske og kredsløbssystemer, i distributionen af ​​registre ved kompilering af programmeringssprog på højt niveau og i analysen af ​​sociale netværk . Shreve [5] [6] og Hodgkinsons gruppe [7] udviklede et alternativt flowordresystem ] . En statistisk sammenligning af Strahler- og Shreve-systemerne, sammen med en analyse af flowlængderne, blev givet af Smart [8] .

Definition

Alle træer i artiklens sammenhæng er rettede grafer rettet fra roden til bladene. Med andre ord, de er rettet træer . Graden af ​​en node i et træ er simpelthen antallet af efterkommere af noden. Du kan tildele Strahler-numre til alle noder i træet fra bund til top som følger:

Strahler-tallet for et træ er lig med Strahler-tallet for dets rodknude.

Algoritmisk kan disse numre tildeles ved at udføre en dybde-først-søgning og tildele hver knude et Strahler-nummer i omvendt rækkefølge . De samme tal kan genereres ved beskæring, hvor træet forenkles gennem en række trin. Ved hvert trin fjernes alle dinglende knudepunkter og alle stier med grad et, der fører til blade - knudepunktets Strahler-nummer er lig med det trinnummer, hvor knudepunktet fjernes, og træets Strahler-nummer er lig med det antal trin, der kræves for at fjern alle noder. En anden ækvivalent Strahler-definition af et træ er højden af ​​det største komplette binære træ , der kan være homeomorphically indlejret i et givet træ. Strahler-tallet for en knude i et træ er analog med højden af ​​det største komplette træ, der kan indlejres under det knudepunkt.

Enhver node med Strahler nummer i skal have mindst to børn med Strahler nummer i  − 1, mindst fire børn med Strahler nummer i  − 2 osv., og mindst 2 i  − 1 blade børn. I et træ med n noder er den største værdi af Strahler-tallet således log 2  n  + 1 [9] . Men hvis træet ikke danner et komplet binært træ, vil dets Strahler-tal være mindre end denne værdi. I et binært træ med n noder, valgt tilfældigt blandt alle mulige binære træer med ensartet sandsynlighed , er det forventede rodindeks meget tæt på log 4  n [10] [9] med høj sandsynlighed .

Ansøgninger

Flodnetværk

I Strahlers anvendelse af strømningsordrer i hydrologi behandles hvert segment af en å eller en flod som en knude i et træ. Når to førsteordens streams smelter sammen, danner de en andenordens stream . Når andenordens flows flettes, danner de et tredjeordens flow . Når strømme af lavere orden smelter sammen til en strøm af højere orden, ændres strømrækkefølgerne ikke. Således, hvis en førsteordens strøm smelter sammen til en andenordens strøm, forbliver den anden strøm en andenordens strøm. Men hvis et flow af anden orden smelter sammen i et flow af samme orden, bliver det andet et flow af tredje orden. For matematiske træer skal segmentet med indeks i have mindst 2 i  − 1 distinkte kilder til orden 1. Shreve bemærkede, at Hortons og Strahlers love kan forventes i enhver topologisk tilfældig fordeling. Efterfølgende undersøgelser af forbindelserne bekræftede disse argumenter og fastslog, at strukturen eller kilderne til strømmene ikke kunne forklares [7] [11] .

Vandstrømmen skal være (som et hydrologisk fænomen) enten flygtig eller ikke flygtig . Intermitterende (eller "intermitterende") vandløb har kun vand i deres kanal en del af året. Strømningsindekset kan variere fra 1 (strøm uden bifloder) til 12 (de mest kraftfulde floder såsom Amazonas ved dens udmunding). Ohio har en ordre på 8, og Mississippi har en ordre på 10. Omkring 80 % af planetens strømninger anslås at have en størrelsesorden på en til tre [12]

Hvis bifurkationsforholdet af vandstrømmene er lavt, så er der stor risiko for oversvømmelse, da vandet vil blive opsamlet i én kanal og ikke spredt, som i tilfældet med et højt bifurkationsforhold. Bifurkationsforholdet kan også vise, hvilke dele af vandløbsoplandet, der er farligere (i forhold til muligheden for oversvømmelse). De fleste floder i Storbritannien har bifurkationsforhold mellem 3 og 5 [13] .

Glazer, Denisyuk, Rimmer og Salingar [14] beskrev, hvordan man beregner Strahlers flowordreværdi i GIS . Denne algoritme er implementeret i RivEX -systemet, et ArcGIS 10.2.1 værktøjssystem fra ESRI. Input til deres algoritme er et netværk af centrale linjer af vandstrømme, repræsenteret af buer (eller kanter) forbinder noder. Søgrænser og flodbredder bør ikke bruges som buer, da de generelt danner et netværk med uregelmæssig topologi.

Andre hierarkiske systemer

Strahler-nummerering kan anvendes til den statistiske analyse af ethvert hierarkisk system, ikke kun floder.

Registertildeling

Når du oversætter programmeringssprog på højt niveau til assemblersprog, er det mindste antal registre , der kræves for at udføre et udtrykstræ, nøjagtigt lig med dets Strahler-nummer. I denne sammenhæng kan Strahler-nummeret kaldes antallet af registre [19] [20] .

For udtrykstræer, der kræver flere registre, end der er tilgængelige, kan Seth-Ullman-algoritmen bruges til at konvertere udtrykstræet til en sekvens af maskininstruktioner, der bruger registre så effektivt som muligt, hvilket minimerer antallet af mellemliggende registerskrivninger til hovedhukommelsen og det samlede antal antal instruktioner i kompileret kode.

Relaterede parametre

Bifurkationsforhold

Relateret til Strahler-tallene for træer er bifurkationsrelationer, der beskriver, hvor tæt et træ er på et balanceret træ. For hver orden i i hierarkiet er den i -te bifurkationsrelation

,

hvor n i betyder antallet af noder af orden i .

Som bifurkationsforholdet for hele hierarkiet kan vi tage gennemsnittet af bifurkationsforholdene. I et komplet binært træ vil bifurkationsforholdet være 2, men andre træer vil have et mindre bifurkationsforhold. Bifurkationsforholdet er en dimensionsløs størrelse.

Sporbredde

Stibredden af ​​en vilkårlig ikke- rettet graf G kan defineres som det mindste tal w , således at der er en intervalgraf H , der indeholder G som en undergraf, således at den største klike af H har w  + 1 hjørner. For træer (behandlet som urettede grafer ved at ignorere orientering og rod), kan stibredden afvige fra Strahler-tallet, men er tæt relateret til det - i et træ med en stibredde w og et Strahler-tal s , er disse to størrelser forbundet med ulighed [21]

w ≤ s ≤ 2 w + 2.

Evnen til at arbejde med grafer, der har en cyklus, og ikke kun med træer, giver stibredden yderligere fleksibilitet sammenlignet med Strahler-tallet. I modsætning til Strahler-nummeret er stibredden dog kun defineret for hele grafen, ikke for hver node i grafen.

Noter

  1. ↑ 1 2 Ananiev, Simonov, Spiridonov, 1992 , s. 102.
  2. ↑ Horton, 1945 .
  3. ↑ Strahler, 1952 .
  4. ↑ Strahler, 1957 .
  5. ↑ Shreve, 1966 , s. 17-37.
  6. ↑ Shreve, 1967 , s. 178-186.
  7. ↑ 1 2 Hodgkinson, McLoughlin, Cox, 2006 , s. 394-407.
  8. ↑ Smart, 1968 , s. 1001-1014.
  9. ↑ 1 2 Devroye, Kruszewski, 1996 .
  10. ↑ Devroye, Kruszewski, 1995 .
  11. ↑ Kirchner, 1993 , s. 591-594.
  12. ↑ Strømrækkefølge - Klassificeringen af ​​vandløb og floder . Hentet: 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 og Schlund ( Luttenberger, Schlund 2011 ) brugte en definition af "dimensionen" af et træ, som er én mindre end Strahler-tallet.

Litteratur