Номер прожектора

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

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

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

Определение

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

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

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

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

Любой узел с номером Стралера i должен иметь как минимум двух потомков с номером Стралера i - 1, как минимум четырех потомков с номером Стралера i - 2 и т. д., и как минимум 2. ^{я - 1} потомки листьев. Следовательно, в дереве с n узлами максимально возможное число Стралера равно log ₂   n + 1. Однако, если дерево не образует полное двоичное дерево, его число Стралера будет меньше этой границы. В с n узлами двоичном дереве , случайно выбранном среди всех возможных двоичных деревьев , ожидаемый индекс корня с высокой вероятностью очень близок к log ₄   n .

Приложения

Речные сети

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

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

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

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

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

Альтернативные системы упорядочивания потоков были разработаны Шривом. и Ходжкинсон и др. Статистическое сравнение систем Стралера и Шрива, а также анализ длин потоков/каналов предоставлено Смартом.

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

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

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

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

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

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

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

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

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

${\frac {n_{i}}{n_{i+1}}}$

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

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

Ширина пути

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

ш ≤ с ≤ 2 ш + 2.

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

См. также

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

Ссылки

• Аренас, А.; Данон, Л.; Диас-Гилера, А.; Глейзер, премьер-министр; Гимера, Р. (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 .
• Борхерт, Рольф; Слэйд, Норман А. (1981), «Коэффициенты бифуркации и адаптивная геометрия деревьев», Botanical Gazette , 142 (3): 394–401, doi : 10.1086/337238 , hdl : 1808/9253 , JSTOR   2474363 , S2CID   84145477 .
• Деврой, Люк ; Крушевски, Пол (1995), «Заметки о числе Хортона – Стралера для случайных деревьев», Information Processing Letters , 56 (2): 95–99, doi : 10.1016/0020-0190(95)00114-R .
• Деврой, Л. ; Крушевски П. (1996), «О числе Хортона-Стралера для случайных попыток» , RAIRO Informatique Théorique et Applications , 30 (5): 443–456, doi : 10.1051/ita/1996300504431 , MR   1435732
• Эренфойхт, А .; Розенберг, Г .; Вермейр, Д. (1981), «О системах ETOL с конечным древовидным рангом», SIAM Journal on Computing , 10 (1): 40–58, doi : 10.1137/0210004 , MR   0605602 .
• Ершов, А. П. (1958), «О программировании арифметических операций», Сообщения АКМ , 1 (8): 3–6, doi : 10.1145/368892.368907 , S2CID   15986378 .
• Флажоле, П. ; Рауль, Дж.К.; Вуйемен, Дж. (1979), «Количество регистров, необходимых для оценки арифметических выражений», Theoretical Computer Science , 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 , S2CID   128399321 .
• Хорсфилд, Кейт (1976), «Некоторые математические свойства ветвящихся деревьев применительно к дыхательной системе», Бюллетень математической биологии , 38 (3): 305–315, doi : 10.1007/BF02459562 , PMID   1268383 , S2CID   189888885 .
• Хортон, Р.Э. (1945), «Эрозионное развитие ручьев и их водосборных бассейнов: гидрофизический подход к количественной морфологии» , Бюллетень Геологического общества Америки , 56 (3): 275–370, doi : 10.1130/0016-7606 (1945). )56[275:EDOSAT]2.0.CO;2 , S2CID   129509551 .
• Ланфир, К.Дж. (1990), «Быстрый алгоритм автоматического расчета порядка потока Стралера», Журнал Американской ассоциации водных ресурсов , 26 (6): 977–981, Bibcode : 1990JAWRA..26..977L , doi : 10.1111/ j.1752-1688.1990.tb01432.x .
• Люттенбергер, Майкл; Шлунд, Максмилиан (2011), Расширение теоремы Париха за пределы идемпотентности , arXiv : 1112.2864 , Bibcode : 2011arXiv1112.2864L
• Стралер, А.Н. (1952), «Гипсометрический (площадь-высотный) анализ эрозионной топологии», Бюллетень Геологического общества Америки , 63 (11): 1117–1142, doi : 10.1130/0016-7606(1952)63[1117:HAAOET ]2.0.CO;2 .
• Стралер, А.Н. (1957), «Количественный анализ геоморфологии водоразделов», Труды Американского геофизического союза , 38 (6): 913–920, Бибкод : 1957TrAGU..38..913S , doi : 10.1029/tr038i006p00913 .
• Во, Дэвид (2002), География, комплексный подход (3-е изд.), Нельсон Торнс .