.svg/1280px-Flussordnung_(Strahler).svg.png)
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 su complejidad de ramificación.
Estos números fueron desarrollados por primera vez 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 orden de arroyos de Strahler y se utilizan para definir el tamaño de los arroyos en función de una jerarquía de afluentes . Las mismas cifras surgen también 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 de redes sociales .
Todos los árboles en este contexto son grafos dirigidos , orientados desde la raíz hacia las hojas; es decir, son arborescencias . El grado de un nodo en un árbol es simplemente su número de hijos. Se puede asignar un número de Strahler a todos los nodos de un árbol, en orden de abajo hacia arriba, de la siguiente manera:
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 orden posterior . Los mismos números también pueden generarse 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 de las 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 este proceso lo eliminaría, 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 puede incrustarse homeomórficamente en el árbol dado; De manera similar, el número de Strahler de un nodo en un árbol es 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 de 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]
En la aplicación del orden de corrientes de Strahler a la hidrología, cada segmento de una corriente 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 juntan, forman una corriente de segundo orden . Cuando dos corrientes de segundo orden se juntan, 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 corriente de primer orden se une a una corriente de segundo orden, sigue siendo una corriente de segundo orden. No es hasta que una corriente de segundo orden se combina con otra corriente de segundo orden que se convierte en una corriente 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 del índice 1. Shreve señaló que se deben esperar las leyes de Horton y Strahler 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 para explicar la estructura u origen de la red de arroyos. [3] [4]
Para calificar como corriente, 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 oscilar entre 1 (un arroyo sin afluentes) y 12 (a nivel mundial el río más caudaloso, 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 . [5]
Si la tasa de bifurcación de una red fluvial es alta, existe una mayor probabilidad de inundaciones. 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 de drenaje tienen más probabilidades de inundarse, comparativamente, al observar las relaciones por separado. La mayoría de los ríos británicos tienen una proporción de bifurcación de entre 3 y 5. [7]
Gleyzer et al. (2004) describen cómo calcular los valores del orden de las corrientes de Strahler en una aplicación SIG . Este algoritmo lo implementa RivEX, una herramienta de ESRI ArcGIS Pro 3.2.x. La entrada a su algoritmo es una red de líneas centrales de cuerpos de agua, representadas como arcos (o bordes) unidos en nodos. Los límites de los lagos y las orillas de los ríos no deben usarse como arcos, ya que generalmente formarán una red sin árboles con una topología incorrecta.
Shreve [8] [9] y Hodgkinson et al. han desarrollado sistemas alternativos de ordenamiento 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 flujo/enlace. [10]
La numeración de Strahler puede aplicarse en el análisis estadístico de cualquier sistema jerárquico, no sólo de los ríos.
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 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 . [13]
Para árboles de expresión que requieren más registros de los disponibles, se puede utilizar el algoritmo de Sethi-Ullman para traducir un árbol de expresión en una secuencia de instrucciones de máquina que utilice los registros de la manera más eficiente posible, minimizando el número de veces que los valores intermedios se derraman de los registros. a la memoria principal y el número total de instrucciones en el código compilado resultante.
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 se puede tomar 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.
El ancho de ruta de un gráfico arbitrario no dirigido G puede definirse como el número más pequeño w tal que exista un gráfico de intervalo H que contenga G como 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úmero de Strahler s , estos dos números están relacionados por las desigualdades [14 ]
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.
