Número de Strahler-Filosofov

El número de Strahler , el número de Horton-Strahler o el número de Strahler-Philosophic [1] de un árbol matemático  es una medida numérica de la complejidad de ramificación.

Estos números fueron introducidos por primera vez en hidrología por Robert Horton [2] en 1945. Strahler [3] [4] e, independientemente, Filosofov propusieron usar una división dicotómica de los ríos en órdenes (como sugirió Horton), pero no adoptaron un procedimiento de recodificación de canales para identificar los principales ríos del sistema [1] . En esta aplicación, los números se denominan orden de corrientes de Strahler y se utilizan para determinar el tamaño de una corriente en función de una jerarquía de afluentes . Los números también aparecen en el análisis de sistemas L y en estructuras biológicas jerárquicas como árboles (biológicos) y los sistemas respiratorio y circulatorio, en la distribución de registros en la compilación de lenguajes de programación de alto nivel y en el análisis de redes sociales . . Shreve [5] [6] y el grupo de Hodgkinson [7] desarrollaron un sistema de orden de flujo alternativo ] . Smart [8] proporcionó una comparación estadística de los sistemas Strahler y Shreve, junto con un análisis de las longitudes de flujo .

Definición

Todos los árboles en el contexto del artículo son gráficos dirigidos desde la raíz hasta las hojas. En otras palabras, son árboles dirigidos . El grado de un nodo en un árbol es simplemente el número de descendientes del nodo. Puede asignar números de Strahler a todos los nodos del árbol de abajo hacia arriba de la siguiente manera:

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

Algorítmicamente , estos números se pueden asignar realizando una búsqueda en profundidad y asignando a cada nodo un número de Strahler en orden inverso . Los mismos números se pueden generar mediante la poda, en la que el árbol se simplifica a través de una serie de pasos. En cada paso, se eliminan todos los nodos colgantes y todos los caminos de grado uno que llevan a las hojas: el número de Strahler del nodo es igual al número de paso en el que se elimina el nodo, y el número de Strahler del árbol es igual al número de pasos necesarios para eliminar todos los nodos. Otra definición equivalente de Strahler de un árbol es la altura del árbol binario completo más grande que se puede anidar homeomórficamente en un árbol dado. El número de Strahler de un nodo en un árbol es análogo a la altura del árbol completo más grande que se puede anidar debajo de ese nodo.

Cualquier nodo con número de Strahler i debe tener al menos dos hijos con número de Strahler i  − 1, al menos cuatro hijos con número de Strahler i  − 2, etc., y al menos 2 hijos i  − 1 hoja. Así, en un árbol con n nodos, el mayor valor del número de Strahler es log 2  n  + 1 [9] . Sin embargo, si el árbol no forma un árbol binario completo, su número de Strahler será menor que este valor. En un árbol binario con n nodos, elegidos aleatoriamente de todos los árboles binarios posibles con probabilidad uniforme , el índice raíz esperado está muy cerca de log 4  n [10] [9] con alta probabilidad .

Aplicaciones

Red fluvial

En la aplicación de Strahler de los órdenes de flujo en hidrología, cada segmento de un arroyo o río se trata como un nodo en un árbol. Cuando dos corrientes de primer orden se fusionan, forman una corriente de segundo orden . Cuando los flujos de segundo orden se fusionan, forman un flujo de tercer orden . Cuando las corrientes de orden inferior se fusionan en una corriente de orden superior, el orden de las corrientes no cambia. Por lo tanto, si un flujo de primer orden se fusiona con un flujo de segundo orden, el segundo flujo sigue siendo un flujo de segundo orden. Pero si un flujo de segundo orden se funde con un flujo del mismo orden, el segundo se convierte en un flujo de tercer orden. Por lo tanto, para árboles matemáticos, el segmento con índice i debe tener al menos 2 i  - 1 fuentes distintas de orden 1. Shreve señaló que las leyes de Horton y Strahler son de esperar en cualquier distribución topológicamente aleatoria. Estudios posteriores de las conexiones confirmaron estos argumentos, estableciendo que la estructura o fuentes de los flujos no podían ser explicadas [7] [11] .

El flujo de agua debe ser (como fenómeno hidrológico) o efímero o no efímero . Los arroyos intermitentes (o "intermitentes") tienen agua en su canal solo una parte del año. El índice de caudal puede variar de 1 (caudal sin afluentes) a 12 (ríos más caudalosos como el Amazonas en su desembocadura). Ohio tiene un orden de 8 y Mississippi tiene un orden de 10. Se estima que alrededor del 80% de los flujos del planeta tienen un orden de uno a tres [12]

Si la relación de bifurcación de los flujos de agua es baja, entonces existe una alta probabilidad de inundación, ya que el agua se recolectará en un canal y no se dispersará, como en el caso de una relación de bifurcación alta. La relación de bifurcación también puede mostrar qué partes de la cuenca del río son más peligrosas (en términos de posibilidad de inundación). La mayoría de los ríos de Gran Bretaña tienen proporciones de bifurcación entre 3 y 5 [13] .

Glazer, Denisyuk, Rimmer y Salingar [14] describieron cómo calcular el valor de orden de flujo de Strahler en GIS . Este algoritmo está implementado en el sistema RivEX , un sistema de herramientas ArcGIS 10.2.1 de ESRI. La entrada a su algoritmo es una red de líneas centrales de flujos de agua, representada por arcos (o bordes) que conectan nodos. Los límites de los lagos y las riberas de los ríos no deben usarse como arcos, ya que generalmente forman una red con una topología irregular.

Otros sistemas jerárquicos

La numeración de Strahler se puede aplicar al análisis estadístico de cualquier sistema jerárquico, no solo de ríos.

Asignación de registros

Al traducir lenguajes de programación de alto nivel a lenguaje ensamblador, el número mínimo de registros necesarios para ejecutar un árbol de expresión es exactamente igual a su número de Strahler. En este contexto, el número de Strahler puede llamarse el número de registros [19] [20] .

Para los árboles de expresión que requieren más registros de los que están disponibles, se puede usar el algoritmo de Seth-Ullman para convertir el árbol de expresión en una secuencia de instrucciones de máquina que usa registros de la manera más eficiente posible, minimizando el número de escrituras de registros intermedios en la memoria principal y el total número de instrucciones en código compilado.

Parámetros relacionados

Relación de bifurcación

Relacionadas con los números de Strahler para árboles, están las relaciones de bifurcación que describen qué tan cerca está un árbol de un árbol equilibrado. Para cada orden i en la jerarquía, la i -ésima relación de bifurcación es

,

donde n i significa el número de nodos de orden i .

Como el índice de bifurcación de toda la jerarquía, podemos tomar el promedio de los índices de bifurcación. En un árbol binario completo, la relación de bifurcación será 2, pero otros árboles tendrán una relación de bifurcación menor. La relación de bifurcación es una cantidad adimensional.

Ancho de vía

El ancho de ruta de un gráfico no dirigido arbitrario G se puede definir como el número más pequeño w tal que hay un gráfico de intervalo H que contiene G como un subgráfico tal que la camarilla más grande de H tiene w  + 1 vértices. Para árboles (tratados como gráficos no dirigidos al ignorar la orientación y la raíz), el ancho de ruta puede diferir del número de Strahler, pero está estrechamente relacionado con él; en un árbol con un ancho de ruta w y un número de Strahler s , estas dos cantidades están relacionadas por el desigualdad [21]

w ≤ s ≤ 2 w + 2.

La capacidad de trabajar con gráficos que tienen un ciclo, y no solo con árboles, le da al ancho de ruta una flexibilidad adicional en comparación con el número de Strahler. Sin embargo, a diferencia del número de Strahler, el ancho de ruta solo se define para todo el gráfico, no para cada nodo del gráfico.

Notas

  1. ↑ 1 2 Ananiev, Simonov, Spiridonov, 1992 , p. 102.
  2. ↑ Horton, 1945 .
  3. ↑ Strahler, 1952 .
  4. ↑ Strahler, 1957 .
  5. ↑ Shreve, 1966 , pág. 17–37.
  6. ↑ Shreve, 1967 , pág. 178–186.
  7. ↑ 1 2 Hodgkinson, McLoughlin, Cox, 2006 , pág. 394–407.
  8. ↑ Smart, 1968 , pág. 1001–1014.
  9. ↑ 1 2 Devroye, Kruszewski, 1996 .
  10. ↑ Devroye, Kruszewski, 1995 .
  11. ↑ Kirchner, 1993 , pág. 591–594.
  12. ↑ Orden de los arroyos: la clasificación de arroyos y ríos . Consultado: 11 de diciembre de 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. ↑ Ershov, 1958 .
  20. ↑ Flajolet, Raoult, Vuillemin, 1979 .
  21. ↑ Luttenberger y Schlund ( Luttenberger, Schlund 2011 ) usaron una definición de la "dimensión" de un árbol, que es uno menos que el número de Strahler.

Literatura