In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the Strahler number or Horton–Strahler number of a mathematical
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
is a numerical measure of its branching complexity.
These numbers were first developed in
hydrology
Hydrology () is the scientific study of the movement, distribution, and management of water on Earth and other planets, including the water cycle, water resources, and environmental watershed sustainability. A practitioner of hydrology is calle ...
by and ; 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
A tributary, or affluent, is a stream or river that flows into a larger stream or main stem (or parent) river or a lake. A tributary does not flow directly into a sea or ocean. Tributaries and the main stem river drain the surrounding drainag ...
. They also arise in the analysis of
L-system
An L-system or Lindenmayer system is a parallel rewriting system and a type of formal grammar. An L-system consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into som ...
s and of hierarchical biological structures such as (biological) trees and animal respiratory and circulatory systems, in
register allocation
In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers.
Register allocation can happen over a basic block (''local register allocatio ...
for
compilation
Compilation may refer to:
*In computer programming, the translation of source code into object code by a compiler
**Compilation error
**Compilation unit
*Product bundling, a marketing strategy used to sell multiple products
*Compilation thesis
M ...
of
high-level programming language
In computer science, a high-level programming language is a programming language with strong abstraction from the details of the computer. In contrast to low-level programming languages, it may use natural language ''elements'', be easier to us ...
s and in the analysis of
social network
A social network is a social structure made up of a set of social actors (such as individuals or organizations), sets of dyadic ties, and other social interactions between actors. The social network perspective provides a set of methods for ...
s. Alternative
stream ordering systems have been developed by Shreve and Hodgkinson et al.
[Hodgkinson, J.H., McLoughlin, S. & Cox, M.E. 2006. The influence of structural grain on drainage in a metamorphic sub-catchment: Laceys Creek, southeast Queensland, Australia. Geomorphology, 81: 394–407.] A statistical comparison of Strahler and Shreve systems, together with an analysis of stream/link lengths, is given by Smart.
Definition
All trees in this context are
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
s, oriented from the root towards the leaves; in other words, they are
arborescences. The
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
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.
Algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
ically, 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
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary tr ...
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
2 ''n'' + 1. 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
4 ''n''.
Applications
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. 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.
To qualify as a stream a hydrological feature must be either recurring or
perennial
A perennial plant or simply perennial is a plant that lives more than two years. The term ('' per-'' + '' -ennial'', "through the years") is often used to differentiate a plant from shorter-lived annuals and biennials. The term is also wid ...
. 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
Amazon most often refers to:
* Amazons, a tribe of female warriors in Greek mythology
* Amazon rainforest, a rainforest covering most of the Amazon basin
* Amazon River, in South America
* Amazon (company), an American multinational technology c ...
, at its mouth). The
Ohio River
The Ohio River is a long river in the United States. It is located at the boundary of the Midwestern and Southern United States, flowing southwesterly from western Pennsylvania to its mouth on the Mississippi River at the southern tip of Illino ...
is of order eight and the
Mississippi River
The Mississippi River is the second-longest river and chief river of the second-largest drainage system in North America, second only to the Hudson Bay drainage system. From its traditional source of Lake Itasca in northern Minnesota, it f ...
is of order 10. Estimates are that 80% of the streams on the planet are first to third order
headwater stream
The headwaters of a river or stream is the farthest place in that river or stream from its estuary or downstream confluence with another river, as measured along the course of the river. It is also known as a river's source.
Definition
The ...
s.
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. 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.
describe how to compute Strahler stream order values in a
GIS application. This algorithm is implemented b
RivEX an ESRI
ArcGIS
ArcGIS is a family of client, server and online geographic information system (GIS) software developed and maintained by Esri. ArcGIS was first released in 1999 and originally was released as ARC/INFO, a command line based GIS system for manipul ...
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.
Other hierarchical systems
The Strahler numbering may be applied in the statistical analysis of any hierarchical system, not just to rivers.
* describe an application of the Horton–Strahler index in the analysis of
social network
A social network is a social structure made up of a set of social actors (such as individuals or organizations), sets of dyadic ties, and other social interactions between actors. The social network perspective provides a set of methods for ...
s.
* 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-system
An L-system or Lindenmayer system is a parallel rewriting system and a type of formal grammar. An L-system consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into som ...
s.
*Strahler numbering has also been applied to biological hierarchies such as the branching structures of trees and of animal respiratory and circulatory systems.
Register allocation
When translating a
high-level programming language
In computer science, a high-level programming language is a programming language with strong abstraction from the details of the computer. In contrast to low-level programming languages, it may use natural language ''elements'', be easier to us ...
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.
For expression trees that require more registers than are available, the
Sethi–Ullman algorithm In computer science, the Sethi–Ullman algorithm is an algorithm named after Ravi Sethi and Jeffrey D. Ullman, its inventors, for translating abstract syntax trees into machine code that uses as few registers as possible.
Overview
When generati ...
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.
Related parameters
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 ''i''th bifurcation ratio is
:
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.
Pathwidth
The
pathwidth
In graph theory, a path decomposition of a graph is, informally, a representation of as a "thickened" path graph, and the pathwidth of is a number that measures how much the path was thickened to form . More formally, a path-decomposition ...
of an arbitrary
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
''G'' may be defined as the smallest number ''w'' such that there exists an
interval graph
In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line,
with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.
In ...
''H'' containing ''G'' as a subgraph, with the largest
clique
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
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
[, using a definition of the "dimension" of a tree that is one less than the Strahler number.]
:''w'' ≤ ''s'' ≤ 2''w'' + 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.
See also
*
Main stem
In hydrology, a mainstem (or trunk) is "the primary downstream segment of a river, as contrasted to its tributaries". Water enters the mainstem from the river's drainage basin, the land area through which the mainstem and its tributaries flow.. A ...
of a river, typically found by following the branch with the highest Strahler number
*
Pfafstetter Coding System The Pfafstetter Coding System is a hierarchical method of hydrologically coding river basins. It was developed by the Brazilian engineer in 1989. It is designed such that topological information is embedded in the code, which makes it easy to det ...
Notes
References
*.
*.
*.
*
*.
*.
*.
*.
*.
*.
*.
*
*.
*.
*.
{{River morphology
Hydrology
Geomorphology
Physical geography
Trees (graph theory)
Graph invariants