Número de Strahler

Em matemática, o número de Strahler ou número de Horton–Strahler de uma árvore (grafo conexo sem ciclos) é uma medida quantitativa da sua complexidade de ramificação.

Diagrama que mostra o número de Strahler associado a cada aresta de um grafo

Esta numeração foi introduzida em hidrologia por Robert E. Horton (1945) e Arthur Newell Strahler (1952, 1957). Neste domínio é conhecida como ordem sequencial de Strahler e é usada para definir o tamanho de um trecho da rede fluvial, baseando-se na hierarquia dos afluentes. Também é usado na análise de outro tipo de estruturas hierárquicas em outros campos, por exemplo a biologia, o estudo dos sistemas respiratório e circulatório, na atribuição de registos para compilação de linguagens de programação de alto nível ou na análise das ligações entre aderentes a redes sociais.

Outros sistemas de numeração da ramificação de grafos do tipo árvore foram desenvolvidos por R.L. Shreve e Hodgkinson et al.

Definição

Segundo a teoria dos grafos, pode-se atribuir o número de Strahler a todos os nós de uma árvore desde as extremidades até à raiz, do seguinte modo:

1. Se o nó for a extremidade de uma aresta / arco, sem qualquer outra ligação (= uma folha na teoria dos grafos), o seu número de Strahler é 1 ;
2. Se o nó tem um arco/aresta ramificado com o número de Strahler i, e todos os outros arcos/arestas têm números de Strahler inferiores a i, o número de Strahler do nó é i também;
3. Se o nó tem dois arcos/arestas ramificados com o número de Strahler i, e nenhum outro com número de Strahler maior, o seu número de Strahler é i + 1.

Bibliogafia

• Arenas, A.; Danon, L.; Díaz-Guilera, A.; Gleiser, P. M.; Guimerá, R. (2004), «Community analysis in social networks», European Physical Journal B, 38 (2): 373–380, doi:10.1140/epjb/e2004-00130-1 .
• Borchert, Rolf; Slade, Norman A. (1981), «Bifurcation ratios and the adaptive geometry of trees», Botanical Gazette, 142 (3): 394–401, JSTOR 2474363, doi:10.1086/337238 .
• Devroye, Luc; Kruszewski, Paul (1995), «A note on the Horton-Strahler number for random trees», Information Processing Letters, 56 (2): 95–99, doi:10.1016/0020-0190(95)00114-R .
• Ehrenfeucht, A.; Rozenberg, G.; Vermeir, D. (1981), «On ETOL systems with finite tree-rank», SIAM Journal on Computing, 10 (1): 40–58, MR 605602, doi:10.1137/0210004 .
• Ershov, A. P. (1958), «On programming of arithmetic operations», Communications of the ACM, 1 (8): 3–6, doi:10.1145/368892.368907 .
• Flajolet, P.; Raoult, J. C.; Vuillemin, J. (1979), «The number of registers required for evaluating arithmetic expressions», Theoretical Computer Science, 9 (1): 99–125, doi:10.1016/0304-3975(79)90009-4 .
• Gleyzer, A.; Denisyuk, M.; Rimmer, A.; Salingar, Y. (2004), «A fast recursive GIS algorithm for computing Strahler stream order in braided and nonbraided networks», Journal of the American Water Resources Association, 40 (4): 937–946, doi:10.1111/j.1752-1688.2004.tb01057.x .
• Horsfield, Keith (1976), «Some mathematical properties of branching trees with application to the respiratory system», Bulletin of Mathematical Biology, 38 (3): 305–315, PMID 1268383, doi:10.1007/BF02459562 .
• Horton, R. E. (1945), «Erosional development of streams and their drainage basins: hydro-physical approach to quantitative morphology», Geological Society of America Bulletin, 56 (3): 275–370, doi:10.1130/0016-7606(1945)56[275:EDOSAT]2.0.CO;2 .
• Lanfear, K. J. (1990), «A fast algorithm for automatically computing Strahler stream order», Journal of the American Water Resources Association, 26 (6): 977–981, doi:10.1111/j.1752-1688.1990.tb01432.x .
• Luttenberger, Michael; Schlund, Maxmilian (2011), An extension of Parikh’s theorem beyond idempotence, arXiv:1112.2864 
• Strahler, A. N. (1952), «Hypsometric (area-altitude) analysis of erosional topology», Geological Society of America Bulletin, 63 (11): 1117–1142, doi:10.1130/0016-7606(1952)63[1117:HAAOET]2.0.CO;2 .
• Strahler, A. N. (1957), «Quantitative analysis of watershed geomorphology», Transactions of the American Geophysical Union, 38 (6): 913–920, doi:10.1029/tr038i006p00913 .
• Waugh, David (2002), Geography, An Integrated Approach 3rd ed. , Nelson Thornes .