Номер Strahler - Strahler number

Диаграмма, показывающая порядок потоков Strahler

В математика, то Номер Strahler или же Число Хортона – Стрелера математического дерево - числовая мера сложности ветвления.

Эти числа были впервые разработаны в гидрология к Роберт Э. Хортон  (1945 ) и Артур Ньюэлл Стралер  (1952, 1957 ); в этом приложении они называются Порядок потока Strahler и используются для определения размера потока на основе иерархии притоки. Они также возникают при анализе L-системы и иерархических биологических структур, таких как (биологические) деревья и дыхательные и кровеносные системы животных, в распределение регистров за сборник из языки программирования высокого уровня и при анализе социальные сети. Альтернатива системы заказа потоков были разработаны Shreve[1][2] и Hodgkinson et al.[3] Смарт дает статистическое сравнение систем Strahler и Shreve, а также анализ длин потоков / каналов.[4]

Определение

Все деревья в этом контексте ориентированные графы, ориентированная от корня к листьям; другими словами, они древесные растения. В степень узла в дереве - это просто количество его дочерних элементов. Можно присвоить номер Стрелера всем узлам дерева в восходящем порядке следующим образом:

  • Если узел является листом (не имеет дочерних), его номер Стрелера равен единице.
  • Если у узла есть один дочерний элемент с номером Strahler я, а все остальные дети имеют числа Стрелера меньше, чем я, то число Стрелера узла равно я опять таки.
  • Если у узла два или более дочерних узла с номером Strahler я, а потомков с большим числом нет, то число Стрелера узла равно я + 1.

Число Стрелера дерева - это номер его корневого узла.

Алгоритмически, эти номера могут быть присвоены путем выполнения поиск в глубину и присвоение каждому узлу номера в почтовый заказ Те же числа могут быть сгенерированы посредством процесса отсечения, в котором дерево упрощается в последовательности этапов, где на каждом этапе удаляются все конечные узлы и все пути узлов первой степени, ведущие к листьям: число Стрелера. узла - это этап, на котором он будет удален этим процессом, а число Стрелера дерева - это количество этапов, необходимых для удаления всех его узлов. Другое эквивалентное определение числа Стрелера дерева состоит в том, что это высота наибольшего полное двоичное дерево это может быть гомеоморфно вложенный в данное дерево; Число Стрелера узла в дереве аналогично высоте самого большого полного двоичного дерева, которое может быть встроено под этот узел.

Любой узел с номером Strahler я должен иметь как минимум двух потомков с номером Штралера я - 1, минимум четыре потомка с числом Штралера я - 2 и т. Д. И не менее 2я − 1 листовые потомки. Следовательно, в дереве с п узлов, максимально возможное число Strahler - log2 п + 1.[5] Однако, если дерево не образует полное двоичное дерево, его число Стрелера будет меньше этой границы. В п-узел двоичное дерево, выбрал равномерно случайным образом среди всех возможных двоичных деревьев, ожидаемый индекс корня с большой вероятностью очень близок к log4 п.[6]

Приложения

Речные сети

В приложении Strahler порядок потоков с точки зрения гидрологии каждый сегмент ручья или реки в речной сети рассматривается как узел в дереве, а следующий сегмент ниже по течению является его родительским. Когда два первый заказ потоки сходятся, они образуют второго порядка транслировать. Когда два потока второго порядка объединяются, они образуют третьего порядка транслировать. Потоки более низкого порядка, присоединяющиеся к потоку более высокого порядка, не изменяют порядок потока более высокого порядка. Таким образом, если поток первого порядка присоединяется к потоку второго порядка, он остается потоком второго порядка. Только когда поток второго порядка объединяется с другим потоком второго порядка, он становится потоком третьего порядка. Как и в случае с математическими деревьями, сегмент с индексом я должны питаться как минимум 2я − 1 различные притоки индекса 1. Шрив заметил, что законы Хортона и Стрелера следует ожидать от любого топологически случайного распределения. Более поздний обзор взаимосвязей подтвердил этот аргумент, установив, что из свойств, описываемых законами, нельзя сделать никаких выводов для объяснения структуры или происхождения потоковой сети.[3][7]

Чтобы считаться ручьем, гидрологический объект должен быть повторяющимся или повторяющимся. многолетнее растение. Регулярные (или «прерывистые») ручьи имеют воду в русле, по крайней мере, часть года. Индекс потока или реки может варьироваться от 1 (ручей без притоков) до 12 (в глобальном масштабе самая мощная река, Amazon, у его устья). В Река Огайо имеет порядок восемь, а Река Миссисипи имеет порядок 10. По оценкам, 80% потоков на планете имеют порядок от первого до третьего. верхние потоки.[8]

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

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

Gleyzer et al. (2004) описать, как вычислить значения порядка потока Strahler в ГИС заявление. Этот алгоритм реализован RivEX, ESRI ArcGIS 10.6.1 инструмент. Входом в их алгоритм является сеть осевых линий водоемов, представленных в виде дуг (или ребер), соединенных в узлах. Границы озер и берега рек не следует использовать в качестве дуг, так как они обычно образуют не-древовидную сеть с неправильной топологией.

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

Нумерация Strahler может применяться при статистическом анализе любой иерархической системы, а не только рек.

  • Arenas et al. (2004) описать применение индекса Хортона – Стрелера в анализе социальные сети.
  • Эренфойхт, Розенберг и Вермейр (1981) применили вариант нумерации Strahler (начиная с нуля на листьях вместо единицы), который они назвали древовидный, к анализу L-системы.
  • Нумерация Strahler также применяется к биологическим иерархиям, таким как ветвящиеся структуры деревьев.[10] дыхательной и кровеносной систем животных.[11]

Размещение регистров

При переводе язык программирования высокого уровня к язык ассемблера минимальное количество регистры Для вычисления дерева выражений требуется в точности его число Стрелера. В этом контексте число Strahler можно также назвать регистрационный номер.[12]

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

Связанные параметры

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

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

куда пя обозначает количество узлов с порядком я.

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

Ширина пути

В ширина пути произвольного неориентированный граф грамм можно определить как наименьшее число ш такой, что существует интервальный график ЧАС содержащий грамм как подграф, с наибольшим клика в ЧАС имея ш + 1 вершина. Для деревьев (рассматриваемых как неориентированные графы, забывая об их ориентации и корне) ширина пути отличается от числа Стрелера, но тесно связана с ним: в дереве с шириной пути ш и число Штралера s, эти два числа связаны неравенствами[13]

ш ≤ s ≤ 2ш + 2.

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

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

  • Главный стебель реки, обычно находящейся по рукаву с наибольшим числом Стрелера

Примечания

  1. ^ Шрив, Р.Л., 1966. Статистический закон чисел потока. Журнал геологии 74, 17–37.
  2. ^ Шрив Р.Л., 1967. Бесконечные топологически случайные сети каналов. Журнал геологии 75, 178–186.
  3. ^ а б Ходжкинсон, Дж. Х., Маклафлин, С. и Кокс, М. Е. 2006. Влияние структурного зерна на дренаж в метаморфическом водосборе: Лейсис-Крик, юго-восток Квинсленда, Австралия. Геоморфология, 81: 394–407.
  4. ^ Смарт, Дж. 1968, Статистические характеристики длин ручьев, Исследование водных ресурсов, 4, № 5. 1001–1014
  5. ^ Деврое и Крушевски (1996).
  6. ^ Деврое и Крушевский (1995, 1996 ).
  7. ^ Кирхнер, Дж. У., 1993. Статистическая неизбежность законов Хортона и очевидная случайность сетей потоковых каналов. Геология 21, 591–594.
  8. ^ «Порядок ручьев - классификация ручьев и рек». Получено 2011-12-11.
  9. ^ Во (2002).
  10. ^ Борхерт и Слэйд (1981)
  11. ^ Хорсфилд (1976).
  12. ^ Ершова (1958); Flajolet, Raoult & Vuillemin (1979).
  13. ^ Люттенбергер и Шлунд (2011), используя определение "измерения" дерева, которое на единицу меньше числа Стрелера.

Рекомендации