Inmathematics, theStrahler number orHorton–Strahler number of a mathematicaltree is a numerical measure of its branching complexity.

These numbers were first developed inhydrology, as a way of measuring the complexity of rivers and streams, byRobert E. Horton (1945) andArthur Newell Strahler (1952,1957). In this application, they are referred to as theStrahler stream order and are used to define stream size based on a hierarchy oftributaries.The same numbers also arise in the analysis ofL-systems and of hierarchical biological structures such as (biological) trees and animal respiratory and circulatory systems, inregister allocation forcompilation ofhigh-level programming languages and in the analysis ofsocial networks.

All trees in this context aredirected graphs, oriented from the root towards the leaves; in other words, they arearborescences. Thedegree 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 numberi, and all other children have Strahler numbers less thani, then the Strahler number of the node isi again.
• If the node has two or more children with Strahler numberi, and no children with greater number, then the Strahler number of the node isi + 1.

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

Algorithmically, these numbers may be assigned by performing adepth-first search and assigning each node's number inpostorder.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 largestcomplete binary tree that can behomeomorphically 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 numberi must have at least two descendants with Strahler numberi − 1, at least four descendants with Strahler numberi − 2, etc., and at least 2^i − 1 leaf descendants. Therefore, in a tree withn nodes, the largest possible Strahler number is log₂ n + 1.^[1] However, unless the tree forms a complete binary tree its Strahler number will be less than this bound. In ann-nodebinary tree, chosenuniformly at random among all possible binary trees, the expected index of the root is with high probability very close to log₄ n.^[2]

In the application of the Strahlerstream 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 twofirst-order streams come together, they form asecond-order stream. When two second-order streams come together, they form athird-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 indexi must be fed by at least 2^i − 1 different tributaries of index 1. Shreve noted that Horton's and Strahler's Laws should be expected from any topologically random distribution. A later review of the relationships confirmed this argument, establishing that, from the properties the laws describe, no conclusion can be drawn to explain the structure or origin of the stream network.^[3][4]

To qualify as a stream a hydrological feature must be either recurring orperennial. Recurring (or "intermittent") 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 (globally the most powerful river, theAmazon, at its mouth). TheOhio River is of order eight and theMississippi River is of order 10. Estimates are that 80% of the streams on the planet are first to third orderheadwater streams.^[5]

If the bifurcation ratio of a river network is high, then there is a higher chance of flooding. There would also be a lower time of concentration.^[6] The bifurcation ratio can also show which parts of adrainage basin are more likely to flood, comparatively, by looking at the separate ratios. Most British rivers have a bifurcation ratio of between 3 and 5.^[7]

Gleyzer et al. (2004) describe how to compute Strahler stream order values in aGIS application. This algorithm is implemented by RivEX, an ESRIArcGIS Pro 3.4.x tool. The input to their algorithm is a network of the centre lines of the bodies of water, represented as arcs (or edges) joined at nodes. Lake boundaries and river banks should not be used as arcs, as these will generally form a non-tree network with an incorrect topology.

Alternativestream ordering systems have been developed by Shreve^[8][9] and Hodgkinson et al.^[3] A statistical comparison of Strahler and Shreve systems, together with an analysis of stream/link lengths, is given by Smart.^[10]

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 ofsocial networks.
• Ehrenfeucht, Rozenberg & Vermeir (1981) applied a variant of Strahler numbering (starting with zero at the leaves instead of one), which they calledtree-rank, to the analysis ofL-systems.
• Strahler numbering has also been applied to biological hierarchies such as the branching structures of trees^[11] and of animal respiratory and circulatory systems.^[12]

When translating ahigh-level programming language toassembly language the minimum number ofregisters required to evaluate an expression tree is exactly its Strahler number. In this context, the Strahler number may also be called theregister number.^[13]

For expression trees that require more registers than are available, theSethi–Ullman algorithm may be used to translate an expression tree into a sequence of machine instructions that uses the registers as efficiently as possible, minimizing the number of times intermediate values are spilled from registers to main memory and the total number of instructions in the resulting compiled code.

The Strahler number can be used informal language theory as a parameter on thederivation trees ofcontext-free grammars, especially those inChomsky normal form. This notion has been studied under the name ofindex of a derivation tree and some properties of the language of a context-free grammar can already be understood by looking at the derivation trees of bounded index.^[14]

Associated with the Strahler numbers of a tree arebifurcation ratios, numbers describing how close to balanced a tree is. For each orderi in a hierarchy, theith bifurcation ratio is

${\displaystyle \frac{n_i}{n_{i+1}}}$

wheren_i denotes the number of nodes with orderi.

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 larger bifurcation ratios. It is a dimensionless number.

Thepathwidth of an arbitraryundirected graphG may be defined as the smallest numberw such that there exists aninterval graphH containingG as a subgraph, with the largestclique inH havingw + 1 vertices. For trees (viewed as undirected graphs by forgetting their orientation and root) the pathwidth differs from the Strahler number, but is closely related to it: in a tree with pathwidthw and Strahler numbers, these two numbers are related by the inequalities^[15]

w ≤s ≤ 2w + 2.

The ability to handle graphs with cycles and not just trees gives pathwidth extra versatility compared to the Strahler number.However, unlike the Strahler number, the pathwidth is defined only for the whole graph, and not separately for each node in the graph.

• Main stem of a river, typically found by following the branch with the highest Strahler number
• Pfafstetter Coding System

• Arenas, A.; Danon, L.; Díaz-Guilera, A.; Gleiser, P. M.; Guimerá, R. (2004), "Community analysis in social networks",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), "Bifurcation ratios and the adaptive geometry of trees",Botanical Gazette,142 (3):394–401,doi:10.1086/337238,hdl:1808/9253,JSTOR 2474363,S2CID 84145477.
• 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),"On the Horton–Strahler number for random tries",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, A. P. (1958), "On programming of arithmetic operations",Communications of the ACM,1 (8):3–6,doi:10.1145/368892.368907,S2CID 15986378.
• 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,Bibcode:2004JAWRA..40..937G,doi:10.1111/j.1752-1688.2004.tb01057.x,S2CID 128399321.
• 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,S2CID 189888885.
• 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,S2CID 129509551.
• Lanfear, K. J. (1990), "A fast algorithm for automatically computing Strahler stream order",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),An extension of Parikh's theorem beyond idempotence,arXiv:1112.2864,Bibcode:2011arXiv1112.2864L
• 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,38 (6):913–920,Bibcode:1957TrAGU..38..913S,doi:10.1029/tr038i006p00913.
• Waugh, David (2002),Geography, An Integrated Approach (3rd ed.), Nelson Thornes.

• Hydrology
• Geomorphology
• Physical geography
• Trees (graph theory)
• Graph invariants

• CS1 maint: work parameter with ISBN
• Articles with short description
• Short description is different from Wikidata