Strahler number
Encyclopedia
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 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
. 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 network
s.
s, 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:
The Strahler number of a tree is the number of its root node.
Algorithm
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 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 2i − 1 leaf descendants. Therefore, in a tree with n nodes, the largest possible Strahler number is log2 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 log4 n.
where ni 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.
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.
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.
s. 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the Strahler number or Horton–Strahler number of a mathematical tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
is a numerical measure of its branching complexity.
These numbers were first developed in hydrology
Hydrology
Hydrology is the study of the movement, distribution, and quality of water on Earth and other planets, including the hydrologic cycle, water resources and environmental watershed sustainability...
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
Tributary
A tributary or affluent is a stream or river that flows into a main stem river or a lake. A tributary does not flow directly into a sea or ocean...
. They also arise in the analysis of hierarchical biological structures such as (biological) trees and animal respiratory and circulatory systems, in register allocation
Register allocation
In compiler optimization, register allocation is the process of assigning a large number of target program variables onto a small number of CPU registers...
for compilation
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
of high level programming languages and in the analysis of social network
Social network
A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
s.
Abstract trees
All trees in this context are directed graphDirected graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
s, oriented from the root towards the leaves; in other words, they are arborescences
Arborescence (graph theory)
In graph theory, an arborescence is a directed graph in which, for a vertex u called the root and any other vertex v, there is exactly one directed path from u to v....
. The degree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum 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.
Algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
ically, these numbers may be assigned by performing a depth-first search
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
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 2i − 1 leaf descendants. Therefore, in a tree with n nodes, the largest possible Strahler number is log2 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
Binary tree
In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to...
, chosen uniformly at random among all possible binary trees
Random binary tree
In computer science and probability theory, a random binary tree refers to a binary tree selected at random from some probability distribution on binary trees...
, the expected index of the root is with high probability very close to log4 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 iswhere ni 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 2i − 1 different tributaries of index 1.To qualify as a stream a hydrological feature must be either recurring or perennial
Perennial stream
A perennial stream or perennial river is a stream or river that has continuous flow in parts of its bed all year round during years of normal rainfall. "Perennial" streams are contrasted with "intermittent" streams which normally cease flowing for weeks or months each year, and with "ephemeral"...
. 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
Amazon River
The Amazon of South America is the second longest river in the world and by far the largest by waterflow with an average discharge greater than the next seven largest rivers combined...
, at its mouth). The Ohio River
Ohio River
The Ohio River is the largest tributary, by volume, of the Mississippi River. At the confluence, the Ohio is even bigger than the Mississippi and, thus, is hydrologically the main stream of the whole river system, including the Allegheny River further upstream...
is of order eight and the Mississippi River
Mississippi River
The Mississippi River is the largest river system in North America. Flowing entirely in the United States, this river rises in western Minnesota and meanders slowly southwards for to the Mississippi River Delta at the Gulf of Mexico. With its many tributaries, the Mississippi's watershed drains...
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
developed a recursive algorithm which would process vector river networks for Strahler stream order values in a GISGeographic Information System
A geographic information system, geographical information science, or geospatial information studies is a system designed to capture, store, manipulate, analyze, manage, and present all types of geographically referenced data...
application. This algorithm is implemented by RivEX, an ESRI ArcGIS
ArcGIS
ArcGIS is a suite consisting of a group of geographic information system software products produced by Esri.ArcGIS is a system for working with maps and geographic information...
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. describe an application of the Horton–Strahler index in the analysis of social networkSocial network
A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
s. 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
High-level programming language
A high-level programming language is a programming language with strong abstraction from the details of the computer. In comparison to low-level programming languages, it may use natural language elements, be easier to use, or be from the specification of the program, making the process of...
to assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
the minimum number of registers
Register allocation
In compiler optimization, register allocation is the process of assigning a large number of target program variables onto a small number of CPU registers...
required to evaluate an expression tree is exactly its Strahler number.