Русская Википедия:Число Стралера — Философова

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Flussordnung (Strahler).svg
Диаграмма порядка потоков Стралера

Число Стралера, число Хортона — Стралера или число Стралера — ФилософоваШаблон:Sfn математического дерева — это численная мера сложности ветвления.

Эти числа впервые были введены в гидрологии Робертом Хортоном (англ.)Шаблон:Sfn в 1945. СтралерШаблон:SfnШаблон:Sfn и, независимо, Философов предложили использовать дихотомическое деление рек на порядки (как предложил Хортон), но ими не принята процедура перекодировки русел для выявления системы главных рекШаблон:Sfn. В этом приложении числа называются порядком потоков Стралера и используются для определения размера потока, основываясь на иерархии притоков. Числа появляются также при анализе L-систем и в иерархических биологических структурах, таких как (биологические) деревья и дыхательные и кровеносные системы, в распределении регистров при компиляции высокоуровневых языков программирования и в анализе социальных сетей. Альтернативную Шаблон:Не переведено 5 разработали ШривШаблон:SfnШаблон:Sfn и группа ХоджкинсонаШаблон:Sfn. Статистическое сравнение систем Стралера и Шрива вместе с анализом длин потоков дал СмартШаблон:Sfn.

Определение

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

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

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

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

Любой узел с числом Стралера i должен иметь по меньшей мере два наследника с числом Стралера i − 1, по меньшей мере четыре наследника с числом Стралера i − 2, и т. д. и по меньшей мере 2i − 1 листовых наследников. Таким образом, в дереве с n узлами наибольшее значение числа Стралера равно log2 n + 1Шаблон:Sfn. Однако, если дерево не образует полное бинарное дерево, его число Стралера будет меньше этой величины. В двоичном дереве с n узлами, выбранном случайно из всех возможных бинарных деревьев с равномерной вероятностью, ожидаемый индекс корня с большой вероятностью очень близок к log4 nШаблон:SfnШаблон:Sfn.

Приложения

Речная сеть

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

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

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

Файл:NetworkType.png
Сравнение неправильного и правильного сведения водной системы в древовидную сеть

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

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

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

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

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

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

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

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

Отношение бифуркации

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

<math>\frac{n_{i}}{n_{i+1}}</math>,

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

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

Путевая ширина

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

w ≤ s ≤ 2w + 2.

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Шаблон:Стиль

Шаблон:Спам-ссылки

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
  2. ↑ Люттенбергер и Шлунд Шаблон:Harv использовали определение «размерности» дерева, которая на единицу меньше числа Стралера.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Число_Стралера_—_Философова&oldid=11339856