Strahler number

U.S. Corps of Engineer diagram showing the Strahler stream order

In mathematics, the Strahler number or Horton–Strahler number of a mathematical tree is a numerical measure of its branching complexity.

These numbers were first developed in hydrology by Robert E. Horton (1945) and Arthur Newell Strahler (1952, 1957); in this application, they are referred to as the Strahler stream order and are used to define stream size based on a hierarchy of tributaries. They also arise in the analysis of hierarchical biological structures such as (biological) trees and animal respiratory and circulatory systems, in register allocation for compilation of high level programming languages and in the analysis of social networks.

Abstract trees

All trees in this context are directed graphs, oriented from the root towards the leaves; in other words, they are arborescences. The degree of a node in a tree is just its number of children. One may assign a Strahler number to all nodes of a tree, in bottom-up order, as follows:

• If the node is a leaf (has no children), its Strahler number is one.
• If the node has one child with Strahler number i, and all other children have Strahler numbers less than i, then the Strahler number of the node is i again.
• If the node has two or more children with Strahler number i, and no children with greater number, then the Strahler number of the node is i + 1.

The Strahler number of a tree is the number of its root node.

Algorithmically, these numbers may be assigned by performing a depth-first search and assigning each node's number in postorder. The same numbers may also be generated via a pruning process in which the tree is simplified in a sequence of stages, where in each stage one removes all leaf nodes and all of the paths of degree-one nodes leading to leaves: the Strahler number of a node is the stage at which it would be removed by this process, and the Strahler number of a tree is the number of stages required to remove all of its nodes. Another equivalent definition of the Strahler number of a tree is that it is the height of the largest complete binary tree that can be homeomorphically embedded into the given tree; the Strahler number of a node in a tree is similarly the height of the largest complete binary tree that can be embedded below that node.

Any node with Strahler number i must have at least two descendants with Strahler number i − 1, at least four descendants with Strahler number i − 2, etc., and at least 2^i − 1 leaf descendants. Therefore, in a tree with n nodes, the largest possible Strahler number is log₂ n. However, unless the tree forms a complete binary tree its Strahler number will be less than this bound. In an n-node binary tree, chosen uniformly at random among all possible binary trees, the expected index of the root is with high probability very close to log₄ n.

Bifurcation ratio

Associated with the Strahler numbers of a tree are bifurcation ratios, numbers describing how close to balanced a tree is. For each order i in a hierarchy, the ith bifurcation ratio is

${\frac {n_{i-1}}{n_{i}}}$

where n_i denotes the number of nodes with order i.

The bifurcation ratio of an overall hierarchy may be taken by averaging the bifurcation ratios at different orders. In a complete binary tree, the bifurcation ratio will be 2, while other trees will have smaller bifurcation ratios.

River networks

In the application of the Strahler stream order to hydrology, each segment of a stream or river within a river network is treated as a node in a tree, with the next segment downstream as its parent. When two first-order streams come together, they form a second-order stream. When two second-order streams come together, they form a third-order stream. Streams of lower order joining a higher order stream do not change the order of the higher stream. Thus, if a first-order stream joins a second-order stream, it remains a second-order stream. It is not until a second-order stream combines with another second-order stream that it becomes a third-order stream. As with mathematical trees, a segment with index i must be fed by at least 2^i − 1 different tributaries of index 1.

To qualify as a stream a hydrological feature must be either recurring or perennial. Recurring streams have water in the channel for at least part of the year. The index of a stream or river may range from 1 (a stream with no tributaries) to 12 (the most powerful river, the Amazon, at its mouth). The Ohio River is of order eight and the Mississippi River is of order 10. 80% of the streams and rivers on the planet are first or second order.

If the bifurcation ratio of a river network is low, there is a higher chance of flooding, as the water will be concentrated in one channel rather than spread out, as a higher bifurcation ratio would indicate. The bifurcation ratio can also show which parts of a drainage basin is more likely to flood, comparatively, by looking at the separate ratios. Most British rivers have a bifurcation ratio of between 3 and 5.

GIS algorithms

Gleyzer et al. (2004) developed a recursive algorithm which would process vector river networks for Strahler stream order values in a GIS application. This algorithm is implemented by RivEX, an ESRI ArcGIS 9.1 tool. The algorithm requires the vector network to be topologically correct to successfully process. The network must be a centre-lined network where each arc (sometimes referred to as an edge) must be joined at their node (sometime referred to as a junction). No left and right banks or lake side shores should be present. The image below demonstrates a map representation of a river network, an invalid network where lake and river bank sides have been digitally captured and a valid, topologically correct, centre-lined river network which the algorithm can process.

If the network is "broken" (arcs not connecting) then the output will be incorrect. The algorithm would treat the disconnected catchment as a separate river system, so it is important to check the connectivity of one's river network before attempting to compute Strahler order values.

Other applications

The Strahler numbering may be applied in the statistical analysis of any hierarchical system, not just to rivers. Arenas et al. (2004) describe an application of the Horton–Strahler index in the analysis of social networks. It has also been applied to biological hierarchies such as the branching structures of trees and of animal respiratory and circulatory systems.

When translating a high-level programming language to assembly language the minimum number of registers required to evaluate an expression tree is exactly its Strahler number.

See also

• Main stem
• Pathwidth

References

• Arenas, A.; Danon, L.; Díaz-Guilera, A.; Gleiser, P. M.; Guimerá, R. (2004), "Community analysis in social networks", The European Physical Journal B - Condensed Matter and Complex Systems, 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, 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.
• 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, doi:10.1007/BF02459562, PMID 1268383.
• 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.
• 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, 8 (6): 913–920.
• Waugh, David (2002), Geography, An Integrated Approach (3rd ed.), Nelson Thornes.