Strahler number

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. 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 or perennial. 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, the Amazon, at its mouth). The Ohio River is of order eight and the Mississippi River is of order 10. Estimates are that 80% of the streams on the planet are first to third order headwater 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 a drainage 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]

Comparison of incorrect and correct conversion of water bodies to a tree network

Gleyzer et al. (2004) describe how to compute Strahler stream order values in a GIS application. This algorithm is implemented by RivEX, an ESRI ArcGIS 10.7 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.

Alternative stream 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 of social networks.
• Ehrenfeucht, Rozenberg & Vermeir (1981) applied a variant of Strahler numbering (starting with zero at the leaves instead of one), which they called tree-rank, to the analysis of L-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 a high-level programming language to assembly language the minimum number of registers required to evaluate an expression tree is exactly its Strahler number. In this context, the Strahler number may also be called the register number.[13]

For expression trees that require more registers than are available, the Sethi–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.

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

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

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

The pathwidth of an arbitrary undirected graph G may be defined as the smallest number w such that there exists an interval graph H containing G as a subgraph, with the largest clique in H having w + 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 pathwidth w and Strahler number s, these two numbers are related by the inequalities[14]

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.