Уровневые коды корневых деревьев

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Level representation of rooted trees.gif

Вершина \,z называется основным корнем свободного дерева \,T (обозначение \bar{z}(T) или просто \bar{z}), если либо \,z — единственный центр \,T, либо \,z — один из центров \,z_1 и \,z_2 бицентрального дерева \,T, определяемый по следующим правилам. Пусть \,T_1 и \,T_2поддеревья, получаемые из \,T удалением ребра, соединяющего \,z_1 и \,z_2. В качестве \,z берется \,z_1, если либо \,T_1 имеет меньше вершин, чем \,T_2, либо \,T_1 и \,T_2 состоят из равного числа вершин, но \,L^*(T_1,z_1) лексикографически предшествует последовательности \,L^*(T_2,z_2);\, z_2 берется в противном случае. Уровневый код L(T,\bar{z})называется главным уровневым кодом дерева \,T, а L^*(T,\bar{z})главным каноническим уровневым кодом дерева \,T.

См. также

Литература

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