Усеченное дерево

Для занумерованных деревьев можно ввести нумерацию вершин. Сначала перенумеруем классы эквивалентности числами 0, 1, ¼ так, чтобы класс, в которых попадает исходное дерево, имел номер 0. Таким образом, нумерация содержит большой произвол. Пусть c – номер класса, в который попадает дерево с корнем . Тогда вершине присваивается номер c. Получили дерево, у которого занумерованы также и вершины, причем корень имеет номер 0.

Рассмотрим теперь дерево с занумерованными ребрами и вершинами. Пусть ветвь проходит через вершины и этим вершинам приписаны соответственно номера Допустим, что , и для всех пар , для которых , индекс является наименьшим. Произведем усечение данной ветви, сохранив ее начальный отрезок до вершины . Произведя операцию усечения каждой ветви, получим усеченное дерево.