Кодирование деревьев

Для помеченных деревьев существует эффективный способ кодирования(его можно использовать для компьютерного представления деревьев).

Найдем лист с минимальным номером, удалим его вместе с инцидентной дугой и запишем номер второй вершины этой дуги. В получившемся после удаления дереве поступаем аналогично и т.д. p- 2 раза. Таким образом, код является последовательностью длины p- 2, элементы которой – числа от 1 до p.

Разумеется, код полезен тогда, когда существует метод декодирования, т.е. восстановления дерева по коду. Опишем соответствующий алгоритм. Выпишем произвольный код, а под ним числа от 1 до p. Находим в нижней последовательности минимальное число, которого нет в коде (такие числа существуют, поскольку код короче p), соединяем вершину с этим номером с вершиной, номер которой в коде первый, вычеркиваем из последовательностей оба эти элемента. Далее продолжаем. В конце в нижней последовательности остаются два числа, соответствующие вершины соединяем дугой.

Поскольку коды деревьев это размещения с повторениями, справедлив следующий результат.

Теорема 18 (Кэли). Число помеченных деревьев с p вершинами равно p^{p -2}.

Это число гигантское, сопоставимое с p!. Обозреть все помеченные деревья даже при небольших p (порядка 10) невозможно.