Уровневые коды корневых деревьев: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Уровневые коды корневых деревьев''' (''Level representation of rooted trees'') - Пусть <math>(T,z)</...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>(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_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>L^*(T,\bar{z})</math> - ''[[главный канонический уровневый код|главным каноническим уровневым кодом]]'' дерева <math>T</math>. | ||
См. также ''Код Гапта для 2-3-деревьев, Коды Ли, Коды, свободные от повторений, Коды с дублированием номеров вершин, Коды с использованием ограничителей, Линейный код.'' | ==См. также == | ||
''[[Код Гапта для 2-3-деревьев]], [[Коды Ли]], [[Коды, свободные от повторений]], [[Коды с дублированием номеров вершин]], [[Коды с использованием ограничителей]], [[Линейный код]].'' | |||
==Литература== | ==Литература== | ||
[Евстигнеев-Касьянов/94] | [Евстигнеев-Касьянов/94] | ||
Версия от 12:02, 18 февраля 2010
Уровневые коды корневых деревьев (Level representation of rooted trees) - Пусть [math]\displaystyle{ (T,z) }[/math] обозначает корневое дерево с лежащим в его основе свободным деревом [math]\displaystyle{ T }[/math] и корнем [math]\displaystyle{ z }[/math]. Уровень вершины [math]\displaystyle{ v }[/math] в [math]\displaystyle{ (T,z) }[/math] - это расстояние [math]\displaystyle{ v }[/math] от [math]\displaystyle{ z }[/math] плюс единица. Уровневый код (обозначение [math]\displaystyle{ L(T,z)=[l_1,l_2,\ldots,l_n]) }[/math] - это последовательность целых чисел, полученная выписыванием уровней вершин дерева [math]\displaystyle{ (T,z) }[/math] в постфиксном порядке. Уровневый код называется каноническим (обозначение [math]\displaystyle{ L^*(T,z)) }[/math], если он является наибольшим в лексикографическом упорядочении среди всех уровневых кодов, описывающих дерево.
Вершина [math]\displaystyle{ z }[/math] называется основным корнем свободного дерева [math]\displaystyle{ T }[/math] (обозначение [math]\displaystyle{ \bar{z}(T) }[/math] или просто [math]\displaystyle{ \bar{z} }[/math], если либо [math]\displaystyle{ z }[/math] - единственный центр [math]\displaystyle{ T }[/math], либо [math]\displaystyle{ z }[/math] - один из центров [math]\displaystyle{ z_1 }[/math] и [math]\displaystyle{ z_2 }[/math] бицентрального дерева [math]\displaystyle{ T }[/math], определяемый по следующим правилам. Пусть [math]\displaystyle{ T_1 }[/math] и [math]\displaystyle{ T_2 }[/math] - поддеревья, получаемые из [math]\displaystyle{ T }[/math] удалением ребра, соединяющего [math]\displaystyle{ z_1 }[/math] и [math]\displaystyle{ z_2 }[/math]. В качестве [math]\displaystyle{ z }[/math] берется [math]\displaystyle{ z_1 }[/math], если либо [math]\displaystyle{ T_1 }[/math] имеет меньше вершин, чем [math]\displaystyle{ T_2 }[/math], либо [math]\displaystyle{ T_1 }[/math] и [math]\displaystyle{ T_2 }[/math] состоят из равного числа вершин, но [math]\displaystyle{ L^*(T_1,z_1) }[/math] лексикографически предшествует последовательности [math]\displaystyle{ L^*(T_2,z_2); z_2 }[/math] берется в противном случае. Уровневый код [math]\displaystyle{ L(T,\bar{z}) }[/math]называется главным уровневым кодом дерева [math]\displaystyle{ T }[/math], а [math]\displaystyle{ L^*(T,\bar{z}) }[/math] - главным каноническим уровневым кодом дерева [math]\displaystyle{ T }[/math].
См. также
Код Гапта для 2-3-деревьев, Коды Ли, Коды, свободные от повторений, Коды с дублированием номеров вершин, Коды с использованием ограничителей, Линейный код.
Литература
[Евстигнеев-Касьянов/94]