Strahler number

Введение

Измерение сложности разветвления В математике число Страхлера или число Хортона Страхлера математического дерева является численной мерой сложности его разветвления. Эти числа были впервые разработаны в гидрологии, как способ измерения сложности рек и ручьев, и в этом приложении они называются порядком потока Страхлера и используются для определения размера потока на основе иерархии притоков. Такие же числа также появляются в анализе L-систем и иерархических биологических структур, таких как (биологические) деревья и дыхательные и кровообрабатывающие системы животных, в распределении регистров для составления языков программирования высокого уровня и в анализе социальных сетей.

Определение

Все деревья в этом контексте - направленные графики, ориентированные от корня к листьям; другими словами, они являются древообразованиями. Степень узла в дереве - это просто количество его детей. Можно назначить число Страхлера всем узлам дерева в порядке от низа вверх, следующим образом: если узел является листьем (не имеет детей), его число Страхлера равно единице. Если у узла есть один ребенок с числом Страхлера i, а у всех других детей число Страхлера меньше i, то число Страхлера узла снова i. Если у узла есть два или более детей со строхлеровским числом i, и нет детей с большим числом, то строхлеровское число узла равно i + 1. Число Стралера дерева - это число его корневого узла. Алгоритмически эти числа могут быть назначены путем выполнения глубокого первого поиска и назначения номера каждого узла в последующем порядке. Те же числа также могут быть получены с помощью процесса обрезки, в котором дерево упрощается в последовательности этапов, где на каждом этапе удаляются все узлы листьев и все пути узлов первой степени, ведущие к листьям: число Страхлера узла - это этап, на котором оно будет удалено этим процессом, а число Страхлера дерева - это количество этапов, необходимых для удаления всех его узлов. Другое эквивалентное определение числа Страхлера дерева заключается в том, что это высота самого большого полного двоичного дерева, которое может быть гомеоморфно встроено в данное дерево; число Страхлера узла в дереве аналогично высоте самого большого полного двоичного дерева, которое может быть встроено ниже этого узла. Любой узел с числом Страхлера i должен иметь по крайней мере два потомка с числом Страхлера i − 1, по крайней мере четыре потомка с числом Страхлера i − 2 и т. д. и по крайней мере 2i − 1 потомка листа. Поэтому, в дереве с n узлами, наибольшее возможное число Страхлера - log2 n + 1. Однако, если дерево не образует полное двоичное дерево, его число Стралера будет меньше этой границы. В двоичном дереве с n узлами, выбранном равномерно случайным образом из всех возможных двоичных деревьев, ожидаемый индекс корня с высокой вероятностью очень близок к log4n.

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.

Речные сети

При применении порядка потоков Страхлера в гидрологии каждый сегмент потока или реки в речной сети рассматривается как узел в дереве, а следующий сегмент вниз по течению - как его родитель. Когда два потока первого порядка соединяются, они образуют поток второго порядка. Когда два потока второго порядка соединяются, они образуют поток третьего порядка. Потоки низшего порядка, присоединяющиеся к потоку более высокого порядка, не меняют порядок потока более высокого порядка. Таким образом, если поток первого порядка присоединяется к потоку второго порядка, он остается потоком второго порядка. Только когда поток второго порядка соединяется с другим потоком второго порядка, он становится потоком третьего порядка. Как и в случае с математическими деревьями, сегмент с индексом i должен питаться по крайней мере 2i - 1 различными притоками индекса 1. Шрев отметил, что законы Хортона и Стралера следует ожидать от любого топологически случайного распределения. Позднее обзор взаимосвязей подтвердил этот аргумент, установив, что из свойств, описанных в законах, нельзя сделать вывод, объясняющий структуру или происхождение сети потоков. Чтобы считаться ручью, гидрологическая особенность должна быть либо повторяющейся, либо многолетней. Вода в канале поступает из периодических (или "перерывных") потоков, по крайней мере, в течение части года. Индекс ручья или реки может варьироваться от 1 (река без притоков) до 12 (самой мощной рекой в мире, Амазонка, в ее устье). Река Огайо - восьмой, а Миссисипи - десятой. По оценкам, 80% рек на планете являются ручьями первого и третьего порядка. Если соотношение бифуркации речной сети высокое, то вероятность наводнения выше. Также будет меньше времени на концентрацию. Коэффициент бифуркации также может показать, какие части бассейна с большей вероятностью затопляются, сравнивая отдельные коэффициенты. Опишите, как рассчитать значения порядка потока Стрейлера в ГИС-приложении. Этот алгоритм реализован RivEX, инструментом ESRI ArcGIS Pro 3.2. x. Вход в их алгоритм - это сеть центральных линий водоемов, представленных в виде дуг (или краев), соединенных в узлах. Границы озер и берега рек не должны использоваться в качестве дуг, поскольку они обычно образуют нелетуческую сеть с неправильной топологией. Альтернативные системы заказа потоков были разработаны Шривом и Ходжкинсоном и др. Статистическое сравнение систем Strahler и Shreve, а также анализ длины потоков/ссылок, приведены в Smart.

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 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 by RivEX, an ESRI ArcGIS Pro 3.2. x 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 and Hodgkinson et al. A statistical comparison of Strahler and Shreve systems, together with an analysis of stream/link lengths, is given by Smart.

Другие иерархические системы

Номерация Стралера может применяться в статистическом анализе любой иерархической системы, а не только рек. описать применение индекса Хортона-Страллера в анализе социальных сетей. применили вариант нумерации Страхлера (начинающийся с нуля на листьях вместо одного), который они назвали рангом дерева, для анализа L-систем. Номерация Страхлера также применяется к биологическим иерархиям, таким как ветвистые структуры деревьев и дыхательных и кровообрабатывающих систем животных.

Распределение в регистре

При переводе языка программирования высокого уровня на язык сборки минимальное количество регистров, необходимое для оценки дерева выражений, является точно его числом Страхлера. В этом контексте номер Страхлера также можно назвать регистрационным номером. Для деревьев выражений, требующих большего количества регистров, чем имеется, алгоритм SethiUllman может быть использован для перевода дерева выражений в последовательность машинных инструкций, которая использует регистры максимально эффективно, минимизируя количество раз, когда промежуточные значения проливаются из регистров в основную память и общее количество инструкций в полученном компилированном коде.

Коэффициент бифуркации

С числами Страхлера дерева связаны соотношения бифуркации, числа, описывающие, насколько близко к балансу дерево. Для каждого порядка i в иерархии, ith коэффициент бифуркации, где ni обозначает количество узлов с порядком i. Коэффициент бифуркации общей иерархии может быть получен путем усреднения коэффициентов бифуркации в разных порядках. В полном двоичном дереве соотношение бифуркации будет 2, в то время как другие деревья будут иметь более высокие соотношения бифуркации. Это безразмерное число.

Ширина пути

Ширина пути произвольного ненаправленного графа G может быть определена как наименьшее число w, такое, что существует интервальный граф H, содержащий G в качестве подграфа, с самой большой кликой в H, имеющей вершины w + 1. Для деревьев (сматриваемых как ненаправленные графики, забывая их ориентацию и корень) ширина пути отличается от числа Страхлера, но тесно связана с ним: в дереве с шириной пути w и числом Страхлера s эти два числа связаны неравенствами w ≤ s ≤ 2w + 2. Возможность обрабатывать графики с циклами, а не только деревьями, дает дополнительную универсальность ширины пути по сравнению с числом Стралера. Однако, в отличие от числа Стралера, ширина пути определяется только для всего графа, а не отдельно для каждого узла в графе.