Numărul Strahler-Filosofov

Numărul Strahler , numărul Horton-Strahler sau numărul Strahler-Filosofic [1] al unui arbore matematic  este o măsură numerică a complexității ramificației.

Aceste numere au fost introduse pentru prima dată în hidrologie de Robert Horton [2] în 1945. Strahler [3] [4] și, în mod independent, Filosofov au propus utilizarea unei împărțiri dihotomice a râurilor în ordine (după cum sugerează Horton), dar nu au adoptat o procedura de codificare a canalului pentru identificarea principalelor râuri ale sistemului [1] . În această aplicație, numerele sunt numite ordinea fluxului lui Strahler și sunt folosite pentru a determina dimensiunea unui flux pe baza unei ierarhii a afluenților . Numerele apar și în analiza sistemelor L și în structurile biologice ierarhice precum arborii (biologici) și sistemele respiratorii și circulatorii, în distribuția registrelor în compilarea limbajelor de programare de nivel înalt și în analiza rețelelor sociale. . Shreve [5] [6] și grupul lui Hodgkinson [7] au dezvoltat un sistem alternativ de ordine a fluxului ] . O comparație statistică a sistemelor Strahler și Shreve, împreună cu o analiză a lungimilor de curgere, a fost dată de Smart [8] .

Definiție

Toți copacii în contextul articolului sunt grafice direcționate direcționate de la rădăcină la frunze. Cu alte cuvinte, sunt arbori direcționați . Gradul unui nod dintr-un arbore este pur și simplu numărul de descendenți ai nodului. Puteți atribui numere Strahler tuturor nodurilor arborelui de jos în sus, după cum urmează:

Numărul Strahler al unui arbore este egal cu numărul Strahler al nodului său rădăcină.

Din punct de vedere algoritmic , aceste numere pot fi atribuite efectuând o căutare în profunzime și atribuind fiecărui nod un număr Strahler în ordine inversă . Aceleași numere pot fi generate prin tăiere, în care arborele este simplificat printr-o serie de pași. La fiecare pas, toate nodurile suspendate și toate căile cu gradul unu care duc la frunze sunt eliminate - numărul Strahler al nodului este egal cu numărul pasului la care este îndepărtat nodul, iar numărul Strahler al arborelui este egal cu numărul de pași necesari pentru eliminați toate nodurile. O altă definiție echivalentă Strahler a unui arbore este înălțimea celui mai mare arbore binar complet care poate fi imbricat homeomorf într-un arbore dat. Numărul Strahler al unui nod dintr-un arbore este analog cu înălțimea celui mai mare arbore complet care poate fi imbricat sub acel nod.

Orice nod cu numărul Strahler i trebuie să aibă cel puțin doi copii cu numărul Strahler i  − 1, cel puțin patru copii cu numărul Strahler i  − 2 etc. și cel puțin 2 i  − 1 copii frunză. Astfel, într-un arbore cu n noduri, cea mai mare valoare a numărului Strahler este log 2  n  + 1 [9] . Cu toate acestea, dacă arborele nu formează un arbore binar complet, numărul său Strahler va fi mai mic decât această valoare. Într -un arbore binar cu n noduri, ales aleatoriu dintre toți arborii binari posibili cu probabilitate uniformă , indicele rădăcină așteptat este foarte apropiat de log 4  n [10] [9] cu probabilitate mare .

Aplicații

Rețeaua fluvială

În aplicarea de către Strahler a ordinelor de curgere în hidrologie, fiecare segment al unui râu sau râu este tratat ca un nod într-un copac. Când două fluxuri de ordinul întâi se îmbină, ele formează un flux de ordine al doilea . Când fluxurile de ordinul doi se îmbină, ele formează un flux de ordinul al treilea . Când fluxurile de ordin inferior se îmbină într-un flux de ordin superior, ordinele fluxurilor nu se modifică. Astfel, dacă un flux de ordinul întâi se îmbină într-un flux de ordinul doi, al doilea flux rămâne un flux de ordinul doi. Dar dacă un flux de ordinul doi se contopește într-un flux de același ordin, al doilea devine un flux de ordinul al treilea. Astfel, pentru arbori matematici, segmentul cu indicele i trebuie să aibă cel puțin 2 i  − 1 surse distincte de ordin 1. Shreve a remarcat că legile lui Horton și Strahler sunt de așteptat în orice distribuție topologic aleatorie. Studiile ulterioare ale conexiunilor au confirmat aceste argumente, stabilind că structura sau sursele fluxurilor nu au putut fi explicate [7] [11] .

Debitul de apă trebuie să fie (ca fenomen hidrologic) fie efemer, fie nu efemer . Pârâurile intermitente (sau „intermitente”) au apă în canal doar o parte a anului. Indicele debitului poate varia de la 1 (debit fără afluenți) la 12 (cele mai puternice râuri, cum ar fi Amazonul la gura sa). Ohio are un ordin de 8, iar Mississippi are un ordin de 10. Se estimează că aproximativ 80% din fluxurile planetei au un ordin de la unu la trei [12]

Dacă raportul de bifurcare a fluxurilor de apă este scăzut, atunci există o șansă mare de inundație, deoarece apa va fi colectată într-un canal și nu va fi dispersată, ca în cazul unui raport de bifurcare mare. Raportul de bifurcație poate arăta și ce părți ale bazinului hidrografic sunt mai periculoase (din punct de vedere al posibilității de inundație). Majoritatea râurilor din Marea Britanie au rapoarte de bifurcare între 3 și 5 [13] .

Glazer, Denisyuk, Rimmer și Salingar [14] au descris cum se calculează valoarea ordinii de curgere a lui Strahler în GIS . Acest algoritm este implementat în sistemul RivEX , un sistem de instrumente ArcGIS 10.2.1 de la ESRI. Intrarea în algoritmul lor este o rețea de linii centrale ale fluxurilor de apă, reprezentate de arce (sau margini) care leagă noduri. Limitele lacurilor și malurile râurilor nu trebuie folosite ca arce, deoarece în general formează o rețea cu topologie neregulată.

Alte sisteme ierarhice

Numerotarea Strahler poate fi aplicată analizei statistice a oricărui sistem ierarhic, nu doar a râurilor.

Înregistrează alocare

Când traduceți limbaje de programare de nivel înalt în limbaj de asamblare, numărul minim de registre necesare pentru a executa un arbore de expresii este exact egal cu numărul lui Strahler. În acest context, numărul Strahler poate fi numit numărul de registre [19] [20] .

Pentru arborii de expresie care necesită mai multe registre decât sunt disponibile, algoritmul Seth-Ullman poate fi utilizat pentru a converti arborele de expresie într-o secvență de instrucțiuni de mașină care utilizează registrele cât mai eficient posibil, reducând la minimum numărul de scrieri intermediare ale registrelor în memoria principală și totalul numărul de instrucțiuni din codul compilat.

Parametri înrudiți

Relația de bifurcație

Legate de numerele Strahler pentru copaci sunt relații de bifurcare care descriu cât de aproape este un copac de un copac echilibrat. Pentru fiecare ordin i din ierarhie, relația de bifurcație i -a este

,

unde n i înseamnă numărul de noduri de ordinul i .

Ca raport de bifurcație al întregii ierarhii, putem lua media rapoartelor de bifurcație. Într-un arbore binar complet, raportul de bifurcație va fi 2, dar alți arbori vor avea un raport de bifurcație mai mic. Raportul de bifurcație este o mărime adimensională.

Lățimea pistei

Lățimea de cale a unui grafic arbitrar nedirecționat G poate fi definită ca cel mai mic număr w astfel încât să existe un grafic de interval H care conține G ca subgraf, astfel încât cea mai mare clică a lui H are w  + 1 vârfuri. Pentru copaci (tratați ca grafice nedirecționate, ignorând orientarea și rădăcina), lățimea căii poate diferi de numărul Strahler, dar este strâns legată de acesta - într-un arbore cu o lățime de cale w și un număr Strahler s , aceste două mărimi sunt legate prin inegalitate [21]

w ≤ s ≤ 2 w + 2.

Abilitatea de a lucra cu grafice care au un ciclu, și nu doar cu copaci, oferă lățimii de cale o flexibilitate suplimentară în comparație cu numărul Strahler. Cu toate acestea, spre deosebire de numărul Strahler, lățimea de cale este definită doar pentru întregul grafic, nu pentru fiecare nod din grafic.

Note

  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. ↑ Smart, 1968 , p. 1001–1014.
  9. ↑ 1 2 Devroye, Kruszewski, 1996 .
  10. ↑ Devroye, Kruszewski, 1995 .
  11. ↑ Kirchner, 1993 , p. 591–594.
  12. ↑ Stream Order - The Classification of Streams and Rivers . Preluat: 11 decembrie 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. ↑ Erșov, 1958 .
  20. ↑ Flajolet, Raoult, Vuillemin, 1979 .
  21. ↑ Luttenberger și Schlund ( Luttenberger, Schlund 2011 ) au folosit o definiție a „dimensiunii” unui copac, care este cu o mai mică decât numărul Strahler.

Literatură