Число Стралера — Философова

Число Стралера, число Хортона — Стралера или число Стралера — Философова^[1] математического дерева — это численная мера сложности ветвления.

Эти числа впервые были введены в гидрологии Робертом Хортоном (англ.)^[2] в 1945. Стралер^[3][4] и, независимо, Философов предложили использовать дихотомическое деление рек на порядки (как предложил Хортон), но ими не принята процедура перекодировки русел для выявления системы главных рек^[1]. В этом приложении числа называются порядком потоков Стралера и используются для определения размера потока, основываясь на иерархии притоков. Числа появляются также при анализе L-систем и в иерархических биологических структурах, таких как (биологические) деревья и дыхательные и кровеносные системы, в распределении регистров при компиляции высокоуровневых языков программирования и в анализе социальных сетей. Альтернативную систему порядка потоков^[англ.] разработали Шрив^[5][6] и группа Ходжкинсона^[7]. Статистическое сравнение систем Стралера и Шрива вместе с анализом длин потоков дал Смарт^[8].

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

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

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

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

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

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

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

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

Глейзер, Денисюк, Риммер и Салингар^[14] описали, каким образом вычислить значение порядка потока Стралера в GIS. Этот алгоритм имплементирован в системе RivEX, инструментальной системе ArcGIS 10.2.1 компании ESRI. Входом в их алгоритм служит сеть центральных линий водных потоков, представленная дугами (или рёбрами), связывающими узлы. Границы озёр и берега рек не следует использовать в качестве дуг, поскольку, в общем случае, они образуют сеть с неправильной топологией.

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

• Аренас, Данон, Диаз-Гилера и Глейзер^[15] описывают применение индекса Хортона — Стралера для анализа социальных сетей.
• Эренфойхт, Розенберг и Вермьер^[16] применили вариант нумерации Стралера (начиная нумерацию для листьев с нуля, а не с единицы), который они назвали рангом дерева, для анализа L-систем.
• Нумерация Стралера применяется также в биологических иерархиях, таких как структура ветвления деревьев^[17], дыхательных и кровеносных систем животных^[18].

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

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

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

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

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

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

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

w ≤ s ≤ 2w + 2.

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