Код Прюфера
сопоставляет произвольному
конечному дереву
с
вершинами
последовательность
из
чисел (от
до
) с возможными повторениями. Отношение между деревом с помеченными вершинами и кодом Прюфера является взаимно однозначным: каждому дереву соответствует уникальный код Прюфера, при этом номерам вершин сопоставляются элементы последовательности кода. Обратно, по заданному коду из
чисел можно однозначно восстановить дерево с
вершинами. Код был построен
Хайнцем Прюфером
при доказательстве
формулы Кэли
в 1918 году.
Содержание
Построение
Пусть
есть дерево с вершинами, занумерованными числами
. Построение кода Прюфера дерева
T
ведётся путем последовательного удаления вершин из дерева, пока не останутся только две вершины. При этом каждый раз выбирается концевая вершина с наименьшим номером, и в код записывается номер единственной вершины, с которой она соединена. В результате образуется последовательность
, составленная из чисел
, возможно с повторениями.
Пример
Для дерева на диаграмме вершина 1 является концевой вершиной с наименьшим номером, поэтому она удаляется первой, и 4 записывается в код Прюфера.
Вершины 2 и 3 удаляются следующими, так что 4 добавляется в код два раза.
Вершина 4 теперь стала концевой и имеет наименьший номер, поэтому она удаляется, а 5 добавляется в код.
Остались только две вершины, поэтому код записан полностью, и процесс останавливается.
В результате получается код Прюфера (4,4,4,5).
Восстановление дерева
Для восстановления дерева по коду
заготовим список номеров вершин
. Выберем первый номер
, который не встречается в коде. Добавим ребро
, после этого удалим
из
и
из
.
Повторяем процесс до момента, когда код
становится пустым. В этот момент список
содержит ровно два числа
и
. Остаётся добавить ребро
, и дерево построено.
Свойства
Если
— это степень вершины с номером
, то
встречается в коде Прюфера ровно (
) раз.
Приложения
Из кода Прюфера следует
Формула Кэли
, то есть число
остовных деревьев
полного графа
с
вершинами равно
. Доказательство следует из того, что код Прюфера даёт биекцию между остовными деревьями и последовательностями длины
из
чисел.
Код Прюфера также позволяет обобщить формулу Кэли на случай, если даны степени вершин, если
— это последовательность степеней дерева, то число деревьев с такими степенями равно
мультиноминальному коэффициенту
Код Прюфера используется для построений случайных деревьев.
Ссылки
Prüfer, H.
Neuer Beweis eines Satzes über Permutationen
(нем.)
// Arch. Math. Phys.. — 1918. —
Bd. 27
. —
S. 742—744
.