fbpx
Wikipedia

In mathematics, the Strahler number or Horton–Strahler number of a mathematical tree is a numerical measure of its branching complexity.

Diagram showing the Strahler stream order

These numbers were first developed in hydrology by Robert E. Horton (1945) and Arthur Newell Strahler (1952, 1957); 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 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 networks. Alternative stream ordering systems have been developed by Shreve and Hodgkinson et al. A statistical comparison of Strahler and Shreve systems, together with an analysis of stream/link lengths, is given by Smart.

Contents

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.

Algorithmically, 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 + 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 log4 n.

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. 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. 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.

If the bifurcation ratio of a river network is low, then 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 are more likely to flood, comparatively, by looking at the separate ratios. Most British rivers have a bifurcation ratio of between 3 and 5.

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.6.1 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.

  • 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 and of animal respiratory and circulatory systems.

Register allocation

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.

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.

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 is

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

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 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

ws ≤ 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.

  1. Shreve, R.L., 1966. Statistical law of stream numbers. Journal of Geology 74, 17–37.
  2. Shreve, R.L., 1967. Infinite topologically random channel networks. Journal of Geology 75, 178–186.
  3. 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.
  4. Smart, J.S. 1968, Statistical properties of stream lengths, Water Resources Research, 4, No 5. 1001–1014
  5. Devroye & Kruszewski (1996).
  6. Devroye and Kruszewski (1995, 1996).
  7. Kirchner, J.W., 1993. Statistical inevitability of Horton Laws and the apparent randomness of stream channel networks. Geology 21, 591–594.
  8. "Stream Order – The Classification of Streams and Rivers". Retrieved2011-12-11.
  9. Waugh (2002).
  10. Borchert & Slade (1981)
  11. Horsfield (1976).
  12. Ershov (1958); Flajolet, Raoult & Vuillemin (1979).
  13. Luttenberger & Schlund (2011), using a definition of the "dimension" of a tree that is one less than the Strahler number.

Strahler number Article Talk Language Watch Edit 160 160 Redirected from Strahler Stream Order In mathematics the Strahler number or Horton Strahler number of a mathematical tree is a numerical measure of its branching complexity Diagram showing the Strahler stream order These numbers were first developed in hydrology by Robert E Horton 1945 and Arthur Newell Strahler 1952 1957 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 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 networks Alternative stream ordering systems have been developed by Shreve 1 2 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 4 Contents 1 Definition 2 Applications 2 1 River networks 2 2 Other hierarchical systems 2 3 Register allocation 3 Related parameters 3 1 Bifurcation ratio 3 2 Pathwidth 4 See also 5 Notes 6 ReferencesDefinition EditAll 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 Algorithmically 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 1 5 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 6 Applications EditRiver networks Edit 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 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 7 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 8 If the bifurcation ratio of a river network is low then 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 are more likely to flood comparatively by looking at the separate ratios Most British rivers have a bifurcation ratio of between 3 and 5 9 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 6 1 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 Edit 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 amp 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 10 and of animal respiratory and circulatory systems 11 Register allocation Edit 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 12 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 Related parameters EditBifurcation ratio Edit 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 n i n i 1 displaystyle frac n i n i 1 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 Edit 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 13 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 See also EditMain stem of a river typically found by following the branch with the highest Strahler number Pfafstetter Coding SystemNotes Edit Shreve R L 1966 Statistical law of stream numbers Journal of Geology 74 17 37 Shreve R L 1967 Infinite topologically random channel networks Journal of Geology 75 178 186 a b Hodgkinson J H McLoughlin S amp 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 Smart J S 1968 Statistical properties of stream lengths Water Resources Research 4 No 5 1001 1014 Devroye amp Kruszewski 1996 Devroye and Kruszewski 1995 1996 Kirchner J W 1993 Statistical inevitability of Horton Laws and the apparent randomness of stream channel networks Geology 21 591 594 Stream Order The Classification of Streams and Rivers Retrieved 2011 12 11 Waugh 2002 Borchert amp Slade 1981 Horsfield 1976 Ershov 1958 Flajolet Raoult amp Vuillemin 1979 Luttenberger amp Schlund 2011 using a definition of the dimension of a tree that is one less than the Strahler number References EditArenas A Danon L Diaz Guilera A Gleiser P M Guimera 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 Theorique 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 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 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 Retrieved from https en wikipedia org w index php title Strahler number amp oldid 1071756169, wikipedia, wiki, book,

books

, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.