stringtranslate.com

Число Стралера

Диаграмма, показывающая порядок потоков Стрэлера

В математике число Стралера или число Хортона–Штралера математического дерева является числовой мерой его ветвящейся сложности.

Эти числа были впервые разработаны в гидрологии как способ измерения сложности рек и ручьев Робертом Э. Хортоном  (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 (самая мощная река в мире, Амазонка , в ее устье). Река Огайо имеет восьмой порядок, а река Миссисипи — десятый. По оценкам, 80% потоков на планете являются верховьями первого-третьего порядка . [ 5]

Если коэффициент бифуркации речной сети высок, то вероятность затопления выше. Также будет меньше время концентрации. [6] Коэффициент бифуркации также может показать, какие части водосборного бассейна с большей вероятностью затопят, сравнительно, рассматривая отдельные коэффициенты. Большинство британских рек имеют коэффициент бифуркации от 3 до 5. [7]

Сравнение неправильного и правильного преобразования водоемов в древесную сеть

Gleyzer et al. (2004) описывают, как вычислять значения порядка потока Strahler в приложении ГИС . Этот алгоритм реализован 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]

ж ≤ с ≤ 2 ж + 2.

Возможность обработки графов с циклами, а не только деревьев, дает pathwidth дополнительную универсальность по сравнению с числом Страхлера. Однако, в отличие от числа Страхлера, pathwidth определяется только для всего графа, а не отдельно для каждого узла в графе.

Смотрите также

Примечания

  1. ^ Девройе и Крушевски (1996).
  2. ^ Девройе и Крушевски (1995, 1996).
  3. ^ ab Hodgkinson, JH, McLoughlin, S. & Cox, ME 2006. Влияние структурного зерна на дренаж в метаморфическом суб-водосборе: ручей Лейси, юго-восточный Квинсленд, Австралия. Геоморфология, 81: 394–407.
  4. ^ Киршнер, Дж. В., 1993. Статистическая неизбежность законов Хортона и кажущаяся случайность сетей русел рек. Геология 21, 591–594.
  5. ^ "Порядок рек – Классификация рек и потоков". Архивировано из оригинала 2011-11-27 . Получено 2011-12-11 .
  6. ^ Bogale, Alemsha (2021). "Морфометрический анализ водосборного бассейна с использованием географической информационной системы в водоразделе Гилгель-Абай, бассейн озера Тана, верхний бассейн Голубого Нила, Эфиопия". Applied Water Science . 11 (7): 122. Bibcode :2021ApWS...11..122B. doi : 10.1007/s13201-021-01447-9 . S2CID  235630850.
  7. ^ Во (2002).
  8. ^ Шрив, Р. Л., 1966. Статистический закон численности потоков. Журнал геологии 74, 17–37.
  9. ^ Шрив, Р. Л., 1967. Бесконечные топологически случайные сети каналов. Журнал геологии 75, 178–186.
  10. ^ Смарт, Дж. С. 1968, Статистические свойства длин потоков, Исследования водных ресурсов, 4, № 5. 1001–1014
  11. ^ Борхерт и Слэйд (1981)
  12. ^ Хорсфилд (1976).
  13. ^ Ершов (1958); Флажоле, Рауль и Вюйемен (1979).
  14. ^ Люттенбергер и Шлунд (2011) используют определение «размерности» дерева, которое на единицу меньше числа Штралера.

Ссылки