HOME

TheInfoList



OR:

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 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 drainage ...
. They also arise in the analysis of L-systems and 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 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 an ...
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 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.
Algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
ically, these numbers may be assigned by performing a depth-first search and assigning each node's number in
postorder In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. ...
. 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 log2 ''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 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 ...
, chosen uniformly at random among all possible binary trees, the expected index of the root is with high probability very close to log4 ''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 wide ...
. 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 co ...
, 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 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 manipulat ...
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 an ...
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-systems. *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 to
assembly language In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence b ...
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 :\frac 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 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 ''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 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 popula ...
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 of a river, typically found by following the branch with the highest Strahler number * Pfafstetter Coding System


Notes


References

*. *. *. * *. *. *. *. *. *. *. * *. *. *. {{River morphology Hydrology Geomorphology Physical geography Trees (graph theory) Graph invariants