Уровневые коды корневых деревьев: различия между версиями

'''Уровневые коды корневых деревьев''' (''[[Level representation of rooted trees]]'') —

Пусть <math>\,(T,z)</math> обозначает [[корневое дерево]] с лежащим в его основе [[свободное дерево|свободным деревом]] <math>\,T</math> и [[корень|корнем]] <math>\,z</math>. [[Уровень вершины]] <math>v</math> в <math>\,(T,z)</math> — это расстояние <math>\,v</math> от <math>\,z</math> плюс единица. ''Уровневый код'' (обозначение <math>L(T,z)=[l_1,l_2,\ldots,l_n]</math>) — это последовательность целых чисел, полученная выписыванием уровней [[вершина|вершин]] [[дерево|дерева]] <math>\,(T,z)</math> в постфиксном порядке. Уровневый код называется ''каноническим'' (обозначение <math>\,L^*(T,z))</math>, если он является наибольшим в лексикографическом упорядочении среди всех уровневых кодов, описывающих дерево.

Вершина <math>\,z</math> называется ''[[основной корень|основным корнем]]'' [[свободное дерево|свободного дерева]] <math>\,T</math> (обозначение <math>\bar{z}(T)</math> или просто <math>\bar{z}</math>), если либо <math>\,z</math> — единственный [[центр]] <math>\,T</math>, либо <math>\,z</math> — один из центров <math>\,z_1</math> и <math>\,z_2</math> [[бицентральное дерево|бицентрального дерева]] <math>\,T</math>, определяемый по следующим правилам. Пусть <math>\,T_1</math> и <math>\,T_2</math> — [[поддерево|поддеревья]], получаемые из <math>\,T</math> удалением [[ребро|ребра]], соединяющего <math>\,z_1</math> и <math>\,z_2</math>. В качестве

<math>\,z</math> берется <math>\,z_1</math>, если либо <math>\,T_1</math> имеет меньше вершин, чем <math>\,T_2</math>, либо <math>\,T_1</math> и <math>\,T_2</math> состоят из равного числа вершин, но <math>\,L^*(T_1,z_1)</math> лексикографически предшествует последовательности <math>\,L^*(T_2,z_2);\, z_2</math> берется в противном случае. Уровневый код <math>L(T,\bar{z})</math>называется ''[[главный уровневый код|главным уровневым кодом]]'' дерева <math>\,T</math>, а

<math>L^*(T,\bar{z})</math> — ''[[главный канонический уровневый код|главным каноническим уровневым кодом]]'' дерева <math>\,T</math>.

* ''[[Код Гапта для 2-3-деревьев]],''

* ''[[Коды Ли]],''

* ''[[Коды, свободные от повторений]],''

* ''[[Коды с дублированием номеров вершин]],''

* ''[[Коды с использованием ограничителей]],''

* ''[[Линейный код]].''

* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.