En matemáticas , el número de Strahler o el número de Horton-Strahler de un árbol matemático es una medida numérica de su complejidad ramificada.
Estos números fueron desarrollados por primera vez en hidrología por Robert E. Horton ( 1945 ) y Arthur Newell Strahler ( 1952 , 1957 ); en esta aplicación, se les conoce como el orden de las corrientes de Strahler y se utilizan para definir el tamaño de las corrientes en función de una jerarquía de afluentes . También surgen en el análisis de sistemas L y de estructuras biológicas jerárquicas como árboles (biológicos) y sistemas respiratorios y circulatorios de animales, en la asignación de registros para la compilación de lenguajes de programación de alto nivel y en el análisis deredes sociales . Shreve [1] [2] y Hodgkinson et al han desarrollado sistemas alternativos de ordenación de corrientes . [3] Smart ofrece una comparación estadística de los sistemas Strahler y Shreve, junto con un análisis de las longitudes de la transmisión / enlace. [4]
Definición
Todos los árboles en este contexto son gráficos dirigidos , orientados desde la raíz hacia las hojas; en otras palabras, son arborescencias . El grado de un nodo en un árbol es solo su número de 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 el 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 es i de nuevo.
- Si el nodo tiene dos o más hijos con el 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 pueden asignarse realizando una búsqueda en profundidad y asignando el número de cada nodo en el postorder . 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 uno elimina todos los nodos de hojas y todos los caminos de los nodos de grado uno que conducen a las 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 igualmente la altura del árbol binario completo más grande que se puede incrustar debajo de ese nodo.
Cualquier nodo con el número de Strahler i debe tener al menos dos descendientes con el número de Strahler i - 1, al menos cuatro descendientes con el número de Strahler i - 2, etc., y al menos 2 descendientes de hojas i - 1 . Por lo tanto, en un árbol con n nodos, el número de Strahler más grande posible es log 2 n + 1. [5] 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 . [6]
Aplicaciones
Redes fluviales
En la aplicación del orden de arroyos 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 corrientes de primer orden se unen, forman una corriente de segundo orden . Cuando dos corrientes de segundo orden se unen, forman una corriente de tercer orden . Las corrientes de orden inferior que se unen a una corriente de orden superior no cambian el orden de la corriente superior. Por lo tanto, si una secuencia de primer orden se une a una secuencia de segundo orden, permanece como una secuencia de segundo orden. No es hasta que un flujo de segundo orden se combina con otro flujo de segundo orden que se convierte en un flujo 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 tributarios diferentes del índice 1. Shreve señaló que las leyes de Horton y Strahler deben 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 sacar ninguna conclusión que explique la estructura u origen de la red de arroyos. [3] [7]
Para calificar como un arroyo, una característica hidrológica debe ser recurrente o perenne . Los arroyos recurrentes (o "intermitentes") tienen agua en el canal 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 poderoso del mundo, el Amazonas , en su desembocadura). El río Ohio es de orden ocho y el río Mississippi es de orden 10. Se estima que el 80% de los arroyos del planeta son arroyos de cabecera de primer a tercer orden . [8]
Si la relación de bifurcación de una red fluvial es baja, entonces hay una mayor probabilidad de inundación, ya que el agua se concentrará en un canal en lugar de esparcirse, como lo indicaría una relación de bifurcación más alta. El índice de bifurcación también puede mostrar qué partes de una cuenca de drenaje tienen más probabilidades de inundarse, comparativamente, al observar los índices separados. La mayoría de los ríos británicos tienen un índice de bifurcación de entre 3 y 5. [9]
Gleyzer y col. (2004) describen cómo calcular los valores de orden de las corrientes de Strahler en una aplicación GIS . Este algoritmo es implementado por RivEX , una herramienta ESRI ArcGIS 10.6.1. La entrada a su algoritmo es una red de las líneas centrales de los cuerpos de agua, representadas como arcos (o bordes) 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 sin árboles con una topología incorrecta.
Otros sistemas jerárquicos
La numeración de Strahler se puede aplicar 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 Horton-Strahler en el análisis de redes sociales .
- Ehrenfeucht, Rozenberg y Vermeir (1981) aplicaron una variante de Strahler numeración (empezando por cero en las hojas en lugar de uno), que llamaron árbol-rank , al análisis de sistemas-L .
- La numeración de Strahler también se ha aplicado a jerarquías biológicas como las estructuras ramificadas de los árboles [10] y de los sistemas respiratorio y circulatorio de los animales. [11]
Asignación de registros
Cuando se traduce un lenguaje de programación de alto nivel a lenguaje ensamblador el número mínimo de registros necesario para evaluar un árbol de expresión es exactamente su número de Strahler. En este contexto, el número de Strahler también puede denominarse número de registro . [12]
Para árboles de expresión que requieren más registros de los disponibles, el algoritmo Sethi-Ullman puede usarse para traducir un árbol de expresión en una secuencia de instrucciones de máquina que usa los registros de la manera más eficiente posible, minimizando la cantidad de veces que los valores intermedios se extraen de los registros. a la memoria principal y el número total de instrucciones en el código compilado resultante.
Parámetros relacionados
Relación de bifurcación
Asociados con los números de Strahler de un árbol están las proporciones de bifurcación , números que describen qué tan cerca del equilibrio está un árbol. Para cada orden i en una jerarquía, la i- ésima relación de bifurcación es
donde n i denota el número de nodos con orden i .
La relación de bifurcación de una jerarquía general puede tomarse promediando las relaciones de bifurcación en diferentes órdenes. En un árbol binario completo, la proporción de bifurcación será 2, mientras que otros árboles tendrán proporciones de bifurcación mayores. Es un número adimensional.
Ancho de ruta
El ancho de ruta de un grafo arbitrario no dirigido G puede definirse como el número más pequeño w, de modo que exista un grafo de intervalo H que contenga G como un subgrafo, con la camarilla más grande en H teniendo w + 1 vértices. Para los árboles (vistos como gráficos no dirigidos al olvidar su orientación y raíz), el ancho de ruta difiere del número de Strahler, pero está estrechamente relacionado con él: en un árbol con ancho de ruta w y números de Strahler s , estos dos números están relacionados por las desigualdades [13 ]
- w ≤ s ≤ 2 w + 2.
La capacidad de manejar gráficos con ciclos y no solo árboles le da al ancho de ruta una versatilidad adicional en comparación con el número de Strahler. Sin embargo, a diferencia del número de Strahler, el ancho de ruta se define solo para todo el gráfico y no por separado para cada nodo del gráfico.
Ver también
- Tallo principal de un río, que normalmente se encuentra siguiendo la rama con el número más alto de Strahler.
- Sistema de codificación Pfafstetter
Notas
- ^ Shreve, RL, 1966. Ley estadística de los números de flujo. Journal of Geology 74, 17–37.
- ^ Shreve, RL, 1967. Infinitas redes de canales topológicamente aleatorios. Journal of Geology 75, 178-186.
- ^ a b Hodgkinson, JH, McLoughlin, S. & Cox, ME 2006. La influencia del grano estructural en el drenaje en una subcuenca metamórfica: Laceys Creek, sureste de Queensland, Australia. Geomorfología, 81: 394–407.
- ^ Smart, JS 1968, Propiedades estadísticas de las longitudes de los arroyos, Investigación de recursos hídricos, 4, No 5. 1001-1014
- ^ Devroye y Kruszewski (1996) .
- ^ Devroye y Kruszewski ( 1995 , 1996 ).
- ^ 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.
- ^ "Orden de arroyos - la clasificación de arroyos y ríos" . Consultado el 11 de diciembre de 2011 .
- ^ Waugh (2002) .
- ^ Borchert y Slade (1981)
- ^ Horsfield (1976) .
- ↑ Ershov (1958) ; Flajolet, Raoult y Vuillemin (1979) .
- ^ Luttenberger & 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 .; Danon, 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), "Razones de bifurcación y la geometría adaptativa de los árboles", Botanical Gazette , 142 (3): 394–401, doi : 10.1086 / 337238 , hdl : 1808/9253 , JSTOR 2474363.
- 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.
- 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), "On ETOL systems with finite tree-rank", 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", Comunicaciones del 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", Informática teórica , 9 (1): 99-125, doi : 10.1016 / 0304-3975 (79) 90009-4.
- Gleyzer, A .; Denisyuk, M .; Rimmer, A .; Salingar, Y. (2004), "Un algoritmo GIS recursivo rápido para calcular el orden de flujo de Strahler en redes trenzadas y no trenzadas", Revista de la Asociación Estadounidense de Recursos Hídricos , 40 (4): 937–946, Código Bibliográfico : 2004JAWRA..40. .937G , doi : 10.1111 / j.1752-1688.2004.tb01057.x.
- 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 erosional de arroyos y sus cuencas de drenaje: enfoque hidrofísico de 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.
- Lanfear, KJ (1990), "Un algoritmo rápido para calcular automáticamente el orden de las 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.
- Luttenberger, 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 erosional", 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 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.a ed.), Nelson Thornes.