.svg/1280px-Flussordnung_(Strahler).svg.png)
В математике число Стралера или число Хортона-Стралера математического дерева является числовой мерой его сложности ветвления.
Эти числа были впервые разработаны в гидрологии как способ измерения сложности рек и ручьев Робертом Э. Хортоном (1945) и Артуром Ньюэллом Стралером (1952, 1957). В этом приложении они называются порядком потоков Стралера и используются для определения размера потока на основе иерархии притоков . Те же числа возникают также при анализе L-систем и иерархических биологических структур, таких как (биологические) деревья и системы дыхания и кровообращения животных, при распределении регистров для компиляции языков программирования высокого уровня и при анализе социальных сетей .
Все деревья в этом контексте представляют собой ориентированные графы , ориентированные от корня к листьям; другими словами, это древовидные образования . Степень узла в дереве — это просто количество его дочерних элементов. Можно присвоить номер Стралера всем узлам дерева в порядке снизу вверх следующим образом:
Число Стралера дерева — это номер его корневого узла.
Алгоритмически эти номера могут быть назначены путем выполнения поиска в глубину и присвоения номера каждому узлу в обратном порядке . Те же числа можно также получить с помощью процесса сокращения, в котором дерево упрощается в последовательность этапов, где на каждом этапе удаляются все листовые узлы и все пути узлов первой степени, ведущие к листьям: число Стралера узел — это этап, на котором он будет удален в ходе этого процесса, а число Стралера дерева — это количество этапов, необходимых для удаления всех его узлов. Другое эквивалентное определение числа Стралера дерева состоит в том, что это высота наибольшего полного двоичного дерева , которое может быть гомеоморфно вложено в данное дерево; Число Стралера узла в дереве аналогично высоте наибольшего полного двоичного дерева, которое может быть встроено ниже этого узла.
Любой узел с номером Стралера i должен иметь как минимум двух потомков с номером Стралера i - 1, как минимум четырех потомков с номером Стралера i - 2 и т. д. и как минимум 2 i - 1 листовых потомков. Следовательно, в дереве с n узлами максимально возможное число Стралера равно log 2 n + 1. [1] Однако, если дерево не образует полное двоичное дерево, его число Стралера будет меньше этой границы. В двоичном дереве с n узлами , случайно выбранном среди всех возможных двоичных деревьев , ожидаемый индекс корня с высокой вероятностью очень близок к log 4 n . [2]
При применении порядка ручьев Стралера к гидрологии каждый сегмент ручья или реки в речной сети рассматривается как узел в дереве, а следующий сегмент ниже по течению является его родительским. Когда два потока первого порядка соединяются, они образуют поток второго порядка . Когда два потока второго порядка соединяются, они образуют поток третьего порядка . Потоки более низкого порядка, присоединяющиеся к потоку более высокого порядка, не меняют порядок потока более высокого порядка. Таким образом, если поток первого порядка присоединяется к потоку второго порядка, он остается потоком второго порядка. Только когда поток второго порядка объединяется с другим потоком второго порядка, он становится потоком третьего порядка. Как и в случае с математическими деревьями, сегмент с индексом i должен питаться как минимум 2 i - 1 различными притоками индекса 1. Шрив отметил, что законы Хортона и Стралера следует ожидать от любого топологически случайного распределения. Более поздний обзор взаимосвязей подтвердил этот аргумент, установив, что на основе свойств, описываемых законами, нельзя сделать никаких выводов, объясняющих структуру или происхождение сети ручьев. [3] [4]
Чтобы квалифицироваться как поток, гидрологический объект должен быть повторяющимся или многолетним . Повторяющиеся (или «периодические») ручьи содержат воду в русле по крайней мере часть года. Индекс ручья или реки может варьироваться от 1 (ручей без притоков) до 12 (самая мощная река в мире — Амазонка в устье). Река Огайо имеет восьмой порядок, а река Миссисипи — 10-й. По оценкам, 80% рек на планете относятся к верховьям рек от первого до третьего порядка . [5]
Если коэффициент разветвления речной сети высок, вероятность наводнений выше. Также будет меньше времени концентрации. [6] Коэффициент раздвоения также может показать, какие части водосборного бассейна с большей вероятностью будут затоплены, если сравнивать его с отдельными коэффициентами. Большинство британских рек имеют коэффициент бифуркации от 3 до 5. [7]
Глейзер и др. (2004) описывают, как вычислить значения порядка потоков Стралера в приложении ГИС . Этот алгоритм реализован RivEX, инструментом ESRI ArcGIS Pro 3.2.x. Входными данными для их алгоритма является сеть центральных линий водоемов, представленная в виде дуг (или ребер), соединенных в узлах. Границы озер и берега рек не следует использовать в качестве дуг, поскольку они обычно образуют недревесную сеть с неправильной топологией.
Альтернативные системы упорядочения потоков были разработаны Шривом [8] [9] и Ходжкинсоном и др. [3] Статистическое сравнение систем Стралера и Шрива, а также анализ длин потоков/каналов предоставлено Смартом. [10]
Нумерацию Стралера можно применять при статистическом анализе любой иерархической системы, а не только рек.
При переводе языка программирования высокого уровня на ассемблер минимальное количество регистров, необходимое для вычисления дерева выражений, равно его числу Стралера. В этом контексте номер Стралера также можно назвать номером регистра . [13]
Для деревьев выражений, которым требуется больше регистров, чем доступно, можно использовать алгоритм Сетхи-Ульмана для преобразования дерева выражений в последовательность машинных инструкций, которая использует регистры максимально эффективно, сводя к минимуму количество раз, когда промежуточные значения выбрасываются из регистров. в основную память и общее количество инструкций в полученном скомпилированном коде.
С числами Стралера дерева связаны коэффициенты бифуркации — числа, описывающие, насколько дерево близко к сбалансированному. Для каждого порядка i в иерархии i-й коэффициент бифуркации равен
где n i обозначает количество узлов порядка i .
Коэффициент бифуркации всей иерархии может быть получен путем усреднения коэффициентов бифуркации разных порядков. В полном двоичном дереве коэффициент бифуркации будет равен 2, тогда как другие деревья будут иметь больший коэффициент бифуркации. Это безразмерное число.
Ширина пути произвольного неориентированного графа G может быть определена как наименьшее число w такое, что существует граф интервалов H, содержащий G в качестве подграфа, с наибольшей кликой в H , имеющей w + 1 вершину. Для деревьев (рассматриваемых как неориентированные графы, если забыть об их ориентации и корне) ширина пути отличается от числа Стралера, но тесно с ним связана: в дереве с шириной пути w и числом Стралера s эти два числа связаны неравенствами [14] ]
Возможность обрабатывать графы с циклами, а не только с деревьями, придает ширине пути дополнительную универсальность по сравнению с числом Стралера. Однако, в отличие от числа Стралера, ширина пути определяется только для всего графа, а не отдельно для каждого узла графа.
