Hispanopedia Wiki
Articulo de referencia

Número de Strahler

Diagrama que muestra el orden de la corriente de Strahler En matemáticas , el número de Strahler o número de Horton-Strahler de un árbol matemático es una medida numérica de la ...

Hispanopedia WikiContenido en espanolLectura gratuita
Diagrama que muestra el orden de la corriente de Strahler

En matemáticas , el número de Strahler o número de Horton-Strahler de un árbol matemático es una medida numérica de la complejidad de sus ramificaciones.

Estos números fueron desarrollados inicialmente en hidrología , como una forma de medir la complejidad de ríos y arroyos, por Robert E. Horton ( 1945 ) y Arthur Newell Strahler ( 1952 , 1957 ) . En esta aplicación, se les conoce como el orden de arroyo de Strahler y se utilizan para definir el tamaño de un arroyo en función de una jerarquía de afluentes . Estos mismos números también aparecen en el análisis de sistemas L y de estructuras biológicas jerárquicas como árboles (biológicos) y sistemas respiratorios y circulatorios animales, en la asignación de registros para la compilación de lenguajes de programación de alto nivel y en el análisis de redes sociales .  

Definición

En este contexto, todos los árboles son grafos dirigidos , orientados desde la raíz hacia las hojas; en otras palabras, son arborescencias . El grado de un nodo en un árbol es simplemente el número de sus hijos. Se puede asignar un número de Strahler a todos los nodos de un árbol, en orden ascendente, de la siguiente manera:

  • Si el nodo es una hoja (no tiene hijos), su número de Strahler es uno.
  • Si el nodo tiene un hijo con número de Strahler i , y todos los demás hijos tienen números de Strahler menores que i , entonces el número de Strahler del nodo vuelve a ser i .
  • Si el nodo tiene dos o más hijos con número de Strahler i , y ningún hijo con un número mayor, entonces el número de Strahler del nodo es i  +  1.

El número de Strahler de un árbol es el número de su nodo raíz.

Algorítmicamente , estos números se pueden asignar realizando una búsqueda en profundidad y asignando el número de cada nodo en postorden . Los mismos números también se pueden generar mediante un proceso de poda en el que el árbol se simplifica en una secuencia de etapas, donde en cada etapa se eliminan todos los nodos hoja y todos los caminos de nodos de grado uno que conducen a hojas: el número de Strahler de un nodo es la etapa en la que se eliminaría mediante este proceso, y el número de Strahler de un árbol es el número de etapas necesarias para eliminar todos sus nodos. Otra definición equivalente del número de Strahler de un árbol es que es la altura del árbol binario completo más grande que se puede incrustar homeomórficamente en el árbol dado; el número de Strahler de un nodo en un árbol es de manera similar la altura del árbol binario completo más grande que se puede incrustar debajo de ese nodo.

Cualquier nodo con número de Strahler i debe tener al menos dos descendientes con número de Strahler i − 1, al menos cuatro descendientes con número de Strahler i − 2, etc., y al menos 2 i − 1 descendientes hoja. Por lo tanto, en un árbol con n nodos, el mayor número de Strahler posible es log 2 n + 1. [ 1 ] Sin embargo, a menos que el árbol forme un árbol binario completo, su número de Strahler será menor que este límite. En un árbol binario de n nodos , elegido uniformemente al azar entre todos los árboles binarios posibles , el índice esperado de la raíz es con alta probabilidad muy cercano a log 4 n . [ 2 ]          

Aplicaciones

redes fluviales

En la aplicación del orden de corrientes de Strahler a la hidrología, cada segmento de un arroyo o río dentro de una red fluvial se trata como un nodo en un árbol, con el siguiente segmento aguas abajo como su padre. Cuando dos arroyos de primer orden se unen, forman un arroyo de segundo orden . Cuando dos arroyos de segundo orden se unen, forman un arroyo de tercer orden . Los arroyos de menor orden que se unen a un arroyo de mayor orden no cambian el orden de este último. Por lo tanto, si un arroyo de primer orden se une a un arroyo de segundo orden, permanece como un arroyo de segundo orden. Solo cuando un arroyo de segundo orden se combina con otro arroyo de segundo orden se convierte en un arroyo de tercer orden. Al igual que con los árboles matemáticos, un segmento con índice i debe ser alimentado por al menos 2 i − 1   afluentes diferentes de índice 1. Shreve señaló que las leyes de Horton y Strahler deberían esperarse de cualquier distribución topológicamente aleatoria. Una revisión posterior de las relaciones confirmó este argumento, estableciendo que, a partir de las propiedades que describen las leyes, no se puede extraer ninguna conclusión para explicar la estructura o el origen de la red fluvial. [ 3 ] [ 4 ]

Para ser considerado un arroyo, un cuerpo de agua debe ser recurrente o perenne . Los arroyos recurrentes (o intermitentes) tienen agua en su cauce durante al menos parte del año. El índice de un arroyo o río puede variar de 1 (un arroyo sin afluentes) a 12 (el río más caudaloso del mundo, el Amazonas , en su desembocadura). El río Ohio es de orden ocho y el río Misisipi es de orden 10. Se estima que el 80 % de los arroyos del planeta son arroyos de cabecera de primer a tercer orden . [ 5 ]

Si la relación de bifurcación de una red fluvial es alta, entonces hay una mayor probabilidad de inundación. También habría un menor tiempo de concentración. [ 6 ] La relación de bifurcación también puede mostrar qué partes de una cuenca hidrográfica tienen mayor probabilidad de inundarse, comparativamente, al observar las relaciones individuales. La mayoría de los ríos británicos tienen una relación de bifurcación de entre 3 y 5. [ 7 ]

Comparación de la conversión incorrecta y correcta de cuerpos de agua a una red de árboles.

Gleyzer et al. (2004) describen cómo calcular los valores de orden de corriente de Strahler en una aplicación SIG . Este algoritmo se implementa mediante RivEX, una herramienta de ESRI ArcGIS Pro 3.6.x. La entrada del algoritmo es una red de las líneas centrales de los cuerpos de agua, representadas como arcos (o aristas) unidos en nodos. Los límites de los lagos y las riberas de los ríos no deben usarse como arcos, ya que generalmente formarán una red no arbórea con una topología incorrecta.

Shreve [ 8 ] [ 9 ] y Hodgkinson et al. [ 3 ] desarrollaron sistemas alternativos de ordenación de corrientes. Smart [ 10 ] ofrece una comparación estadística de los sistemas de Strahler y Shreve, junto con un análisis de las longitudes de las corrientes/enlaces.

Otros sistemas jerárquicos

La numeración de Strahler puede aplicarse en el análisis estadístico de cualquier sistema jerárquico, no solo a los ríos.

  • Arenas et al. (2004) describen una aplicación del índice de Horton-Strahler en el análisis de redes sociales .
  • Ehrenfeucht, Rozenberg y Vermeir (1981) aplicaron una variante de la numeración de Strahler (que comienza con cero en las hojas en lugar de uno), que llamaron rango de árbol , al análisis de los sistemas L.
  • La numeración de Strahler también se ha aplicado a jerarquías biológicas como las estructuras ramificadas de los árboles [ 11 ] y de los sistemas respiratorio y circulatorio de los animales. [ 12 ]

Asignación de registro

Al traducir un lenguaje de programación de alto nivel a lenguaje ensamblador, el número mínimo de registros necesarios para evaluar un árbol de expresiones es precisamente su número de Strahler. En este contexto, el número de Strahler también puede denominarse número de registro . [ 13 ]

Para árboles de expresiones que requieren más registros de los disponibles, se puede utilizar el algoritmo de Sethi-Ullman para traducir un árbol de expresiones en una secuencia de instrucciones de máquina que utilice los registros de la manera más eficiente posible, minimizando la cantidad de veces que se transfieren valores intermedios de los registros a la memoria principal y la cantidad total de instrucciones en el código compilado resultante.

Lenguajes formales

El número de Strahler puede utilizarse en la teoría del lenguaje formal como parámetro en los árboles de derivación de gramáticas libres de contexto , especialmente aquellas en forma normal de Chomsky . Esta noción se ha estudiado bajo el nombre de índice de un árbol de derivación, y algunas propiedades del lenguaje de una gramática libre de contexto pueden comprenderse al observar los árboles de derivación de índice acotado. [ 14 ]

Relación de bifurcación

Asociados a los números de Strahler de un árbol se encuentran los índices de bifurcación , números que describen qué tan cerca del equilibrio está un árbol. Para cada orden i en una jerarquía, el i- ésimo índice de bifurcación es

norteinortei+1{\displaystyle {\frac {n_{i}}{n_{i+1}}}}

donde n i denota el número de nodos con orden i .

La razón de bifurcación de una jerarquía general se puede obtener promediando las razones de bifurcación en diferentes órdenes. En un árbol binario completo, la razón de bifurcación será 2, mientras que otros árboles tendrán razones de bifurcación mayores. Es un número adimensional.

Ancho de trayectoria

El ancho de camino de un grafo no dirigido arbitrario G puede definirse como el número más pequeño w tal que existe un grafo de intervalo H que contiene a G como subgrafo, con la mayor camarilla en H teniendo w  +  1 vértices. Para los árboles (vistos como grafos no dirigidos olvidando su orientación y raíz) el ancho de camino difiere del número de Strahler, pero está estrechamente relacionado con él: en un árbol con ancho de camino w y número de Strahler s , estos dos números están relacionados por las desigualdades [ 15 ].

w ≤ s ≤ 2 w + 2.

La capacidad de manejar grafos con ciclos, y no solo árboles, otorga al ancho de camino una versatilidad adicional en comparación con el número de Strahler. Sin embargo, a diferencia del número de Strahler, el ancho de camino se define únicamente para todo el grafo, y no por separado para cada nodo del mismo.

Véase también

Notas

  1. ↑ Devroye y Kruszewski (1996) .
  2. ↑ Devroye y Kruszewski ( 1995 , 1996 ) . 
  3. 1 2 Hodgkinson, JH, McLoughlin, S. y Cox, ME 2006. La influencia de la estructura granular en el drenaje en una subcuenca metamórfica: Laceys Creek, sureste de Queensland, Australia. Geomorphology, 81: 394–407.
  4. ↑ Kirchner, JW, 1993. Inevitabilidad estadística de las leyes de Horton y la aparente aleatoriedad de las redes de canales fluviales. Geology 21, 591–594.
  5. ↑ "Orden de los arroyos: la clasificación de arroyos y ríos" . Archivado del original el 27 de noviembre de 2011. Consultado el 11 de diciembre de 2011 .
  6. ↑ Bogale, Alemsha (2021). "Análisis morfométrico de una cuenca hidrográfica utilizando un sistema de información geográfica en la cuenca de Gilgel Abay, cuenca del lago Tana, cuenca alta del Nilo Azul, Etiopía" . Applied Water Science . 11 (7) 122. Bibcode : 2021ApWS...11..122B . doi : 10.1007/s13201-021-01447-9 . S2CID 235630850 . 
  7. ↑ Waugh (2002) .
  8. ↑ Shreve, RL, 1966. Ley estadística del número de arroyos. Journal of Geology 74, 17–37.
  9. ↑ Shreve, RL, 1967. Redes de canales topológicamente aleatorios infinitos. Journal of Geology 75, 178–186.
  10. ↑ Smart, JS 1968, Propiedades estadísticas de las longitudes de los arroyos, Water Resources Research, 4, No 5. 1001–1014
  11. ↑ Borchert y Slade (1981)
  12. ↑ Horsfield (1976) .
  13. ↑ Ershov (1958) ; Flajolet, Raoult y Vuillemin (1979) .
  14. ↑ Esparza, Javier; Lutenberger, Michael; Schlund, Maximilian (2014), "Una breve historia de los números de Strahler" , Apuntes de conferencias sobre informática , Cham: Springer International Publishing, sec. 2.2, ISBN 978-3-319-04920-5, consultado el 22 de diciembre de 2025{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
  15. ↑ Luttenberger y Schlund (2011) , utilizando una definición de la "dimensión" de un árbol que es uno menos que el número de Strahler.

Referencias

  • Arenas, A.; Danón, L.; Díaz-Guilera, A.; Gleiser, PM; Guimerá, R. (2004), "Análisis comunitario en redes sociales", European Physical Journal B , 38 (2): 373– 380, arXiv : cond-mat/0312040 , Bibcode : 2004EPJB...38..373A , doi : 10.1140/epjb/e2004-00130-1 , S2CID 9764926 .
  • Borchert, Rolf; Slade, Norman A. (1981), "Relación de bifurcación y geometría adaptativa de los árboles", Botanical Gazette , 142 (3): 394–401 , doi : 10.1086/337238 , hdl : 1808/9253 , JSTOR 2474363 , S2CID 84145477  .
  • Devroye, Luc ; Kruszewski, Paul (1995), "Una nota sobre el número de Horton-Strahler para árboles aleatorios", Information Processing Letters , 56 (2): 95–99 , doi : 10.1016/0020-0190(95)00114-R.
  • Devroye, L .; Kruszewski, P. (1996), "Sobre el número de Horton-Strahler para intentos aleatorios" , RAIRO Informatique Théorique et Applications , 30 (5): 443– 456, doi : 10.1051/ita/1996300504431 , MR 1435732 
  • Ehrenfeucht, A.; Rozenberg , G.; Vermeir, D. (1981), "Sobre sistemas ETOL con rango de árbol finito", SIAM Journal on Computing , 10 (1): 40–58 , doi : 10.1137/0210004 , MR 0605602 .
  • Ershov, AP (1958), "Sobre la programación de operaciones aritméticas", Communications of the ACM , 1 (8): 3– 6, doi : 10.1145/368892.368907 , S2CID 15986378 .
  • Flajolet, P .; Raoult, JC; Vuillemin, J. (1979), "El número de registros necesarios para evaluar expresiones aritméticas", Theoretical Computer Science , 9 (1): 99–125 , doi : 10.1016/0304-3975(79)90009-4.
  • Gleyzer, A.; Denisyuk, M.; Rimmer, A.; Salingar, Y. (2004), "Un algoritmo SIG recursivo rápido para calcular el orden de Strahler de los arroyos en redes trenzadas y no trenzadas", Journal of the American Water Resources Association , 40 (4): 937– 946, Bibcode : 2004JAWRA..40..937G , doi : 10.1111/j.1752-1688.2004.tb01057.x , S2CID 128399321 .
  • Horsfield, Keith (1976), "Algunas propiedades matemáticas de los árboles ramificados con aplicación al sistema respiratorio", Bulletin of Mathematical Biology , 38 (3): 305–315 , doi : 10.1007/BF02459562 , PMID 1268383 , S2CID 189888885  .
  • Horton, RE (1945), "Desarrollo erosivo de arroyos y sus cuencas de drenaje: enfoque hidrofísico para la morfología cuantitativa" , Boletín de la Sociedad Geológica de América , 56 (3): 275–370 , doi : 10.1130/0016-7606(1945)56 [ 275:EDOSAT ] 2.0.CO ; 2 , S2CID 129509551 .
  • Lanfear, KJ (1990), "Un algoritmo rápido para el cálculo automático del orden de corrientes de Strahler", Journal of the American Water Resources Association , 26 (6): 977– 981, Bibcode : 1990JAWRA..26..977L , doi : 10.1111/j.1752-1688.1990.tb01432.x.
  • Lutenberger, Michael; Schlund, Maxmilian (2011), Una extensión del teorema de Parikh más allá de la idempotencia , arXiv : 1112.2864 , Bibcode : 2011arXiv1112.2864L
  • Strahler, AN (1952), "Análisis hipsométrico (área-altitud) de la topología erosiva", Boletín de la Sociedad Geológica de América , 63 (11): 1117– 1142, doi : 10.1130/0016-7606(1952)63 [ 1117:HAAOET ] 2.0.CO ; 2.
  • Strahler, AN (1957), "Análisis cuantitativo de la geomorfología de cuencas hidrográficas", Transactions of the American Geophysical Union , 38 (6): 913–920 , Bibcode : 1957TrAGU..38..913S , doi : 10.1029/tr038i006p00913.
  • Waugh, David (2002), Geografía: Un enfoque integrado (3.ª  ed.), Nelson Thornes.
Lecturas relacionadas
6 articulos
MatemáticasMatemáticasLas matemáticas son un campo de estudio que descubre y organiza métodos, teorías y teoremas que se desarrollan y prueban para las necesidades de la...Árbol (teoría de grafos)Árbol (teoría de grafos)En teoría de grafos , un árbol es un grafo no dirigido en el que dos vértices cualesquiera están conectados por exactamente un camino , o equivalen...HidrologíaHidrologíaLa hidrología (del griego antiguo ὕδωρ ( húdōr ) 'agua' y -λογία ( -logía ) 'estudio de') es el estudio científico del movimiento, la distribución ...Robert E. HortonRobert E. HortonRobert Elmer Horton (18 de mayo de 1875 - 22 de abril de 1945) fue un hidrólogo , geomorfólogo , ingeniero civil y edafólogo estadounidense , consi...Arthur Newell StrahlerDiagrama que muestra el orden de la corriente de Strahler Arthur Newell Strahler (20 de febrero de 1918 - 6 de diciembre de 2002) fue un profesor d...AfluenteAfluenteUn afluente , [1] o un afluente , [2] es un arroyo o río que desemboca en un arroyo más grande ( cauce principal o "madre" ), río o lago . [3] Un a...