Аноним

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

Материал из WikiGrapp
нет описания правки
(Создана новая страница размером '''Уровневые коды корневых деревьев''' (''Level representation of rooted trees'') - Пусть <math>(T,z)</...)
 
Нет описания правки
Строка 1: Строка 1:
'''Уровневые коды корневых деревьев''' (''Level representation of rooted trees'') -  
'''Уровневые коды корневых деревьев''' (''[[Level representation of rooted trees]]'') -  
Пусть <math>(T,z)</math> обозначает
Пусть <math>(T,z)</math> обозначает
корневое дерево с лежащим в его основе свободным деревом
[[корневое дерево]] с лежащим в его основе [[свободное дерево|свободным деревом]]
<math>T</math> и корнем <math>z</math>. Уровень вершины <math>v</math> в
<math>T</math> и [[корень|корнем]] <math>z</math>. [[Уровень вершины]] <math>v</math> в
<math>(T,z)</math> --- это расстояние <math>v</math> от <math>z</math>
<math>(T,z)</math> - это расстояние <math>v</math> от <math>z</math>
плюс единица. ''Уровневый код'' (обозначение
плюс единица. ''Уровневый код'' (обозначение
<math>L(T,z)=[l_1,l_2,\ldots,l_n])</math> --- это последовательность целых
<math>L(T,z)=[l_1,l_2,\ldots,l_n])</math> - это последовательность целых
чисел, полученная выписыванием уровней вершин дерева
чисел, полученная выписыванием уровней [[вершина|вершин]] [[дерево|дерева]]
<math>(T,z)</math> в постфиксном порядке.
<math>(T,z)</math> в постфиксном порядке.
Уровневый код называется ''каноническим'' (обозначение
Уровневый код называется ''каноническим'' (обозначение
Строка 13: Строка 13:
уровневых кодов, описывающих дерево.
уровневых кодов, описывающих дерево.


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


См. также ''Код Гапта для 2-3-деревьев, Коды Ли, Коды, свободные от повторений, Коды с дублированием номеров вершин, Коды с использованием ограничителей, Линейный код.''
==См. также ==
''[[Код Гапта для 2-3-деревьев]], [[Коды Ли]], [[Коды, свободные от повторений]], [[Коды с дублированием номеров вершин]], [[Коды с использованием ограничителей]], [[Линейный код]].''
==Литература==               
==Литература==               
[Евстигнеев-Касьянов/94]
[Евстигнеев-Касьянов/94]