Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Диаграмма, показывающая порядок потоков Strahler

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

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

Определение [ править ]

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

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

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

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

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

Приложения [ править ]

Речные сети [ править ]

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

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

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

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

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

Другие иерархические системы [ править ]

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

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

Распределение регистров [ править ]

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

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

Связанные параметры [ править ]

Коэффициент бифуркации [ править ]

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

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

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

Ширина пути [ править ]

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

весs ≤ 2 вес + 2.

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

См. Также [ править ]

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

Примечания [ править ]

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

Ссылки [ править ]

  • Arenas, A .; Данон, Л .; Díaz-Guilera, A .; Глейзер, премьер-министр; Гимера, Р. (2004), «Анализ сообщества в социальных сетях», 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.
  • Борхерт, Рольф; Slade, Норман А. (1981), "отношения бифуркации и адаптивная геометрия дерев", ботанический вестник , 142 (3): 394-401, DOI : 10,1086 / 337238 , ЛВП : 1808/9253 , JSTOR  2474363.
  • Деврой, Люк ; Крушевски, Пол (1995), «Заметка о числе Хортона – Стрелера для случайных деревьев», Письма об обработке информации , 56 (2): 95–99, DOI : 10.1016 / 0020-0190 (95) 00114-R.
  • Деврой, Л .; Крушевский, P. (1996), "О числе Хортона-Strahler для случайных попыток" , RAIRO Informatique Théorique и их приложения , 30 (5): 443-456, DOI : 10,1051 / ит / 1996300504431 , МР  1435732
  • Эренфойхт, А .; Розенберг, Г .; Vermeir, D. (1981), "О системах Etol с конечным деревом ранга", SIAM журнал по вычислениям , 10 (1): 40-58, DOI : 10,1137 / 0210004 , MR  0605602.
  • Ершов, А. П. (1958), "О программировании арифметических операций", коммуникаций АСМ , 1 (8): 3-6, DOI : 10,1145 / 368892,368907 , S2CID  15986378.
  • Flajolet, P .; Рауль, JC; Vuillemin, J. (1979), "Число регистров , необходимых для оценки арифметических выражений", Теоретическая информатика , 9 (1): 99-125, DOI : 10,1016 / 0304-3975 (79) 90009-4.
  • Глейзер, А .; Денисюк, М .; Риммер, А .; Салингар, Ю. (2004), «Быстрый рекурсивный алгоритм ГИС для вычисления порядка потока Стрелера в плетеных и несвязанных сетях», Журнал Американской ассоциации водных ресурсов , 40 (4): 937–946, Bibcode : 2004JAWRA..40. .937G , DOI : 10.1111 / j.1752-1688.2004.tb01057.x.
  • Хорсфилд, Кит (1976), "Некоторые математические свойства деревьев разветвленности с применением к дыхательной системы", Бюллетень математической биологии , 38 (3): 305-315, DOI : 10.1007 / BF02459562 , PMID  1268383 , S2CID  189888885.
  • Horton, RE (1945), "Эрозионный развитие потоков и их водосборных бассейнов: гидро-физический подход к количественной морфологии" , Геологическое общество Америки Bulletin , 56 (3): 275-370, DOI : 10,1130 / 0016-7606 (1945 ) 56 [275: EDOSAT] 2.0.CO; 2.
  • Lanfear, KJ (1990), «Быстрый алгоритм для автоматического вычисления порядка потока Strahler», Журнал Американской ассоциации водных ресурсов , 26 (6): 977–981, Bibcode : 1990JAWRA..26..977L , doi : 10.1111 / j.1752-1688.1990.tb01432.x.
  • Люттенбергер, Майкл; Шлунд, Максмилиан (2011), Расширение теоремы Париха за пределы идемпотентности , arXiv : 1112.2864 , Bibcode : 2011arXiv1112.2864L
  • Strahler, А. Н. (1952), "Гипсометрическая (площадь-высота) анализ эрозионной топологии", Геологическое общество Америки Bulletin , 63 (11): 1117-1142, DOI : 10,1130 / 0016-7606 (1952) 63 [1117: HAAOET ] 2.0.CO; 2.
  • Strahler, AN (1957), "Количественный анализ геоморфологии водораздела", Труды Американского геофизического союза , 38 (6): 913–920, Bibcode : 1957TrAGU..38..913S , doi : 10.1029 / tr038i006p00913.
  • Во, Дэвид (2002), География, Комплексный подход (3-е изд.), Нельсон Торнс.