Код Прюфера

Дерево с кодом Прюфера (4,4,4,5).

Код Прюфера сопоставляет произвольному конечному дереву с $n$ вершинами последовательность из $n-2$ чисел (от $1$ до $n$) с возможными повторениями. Отношение между деревом с помеченными вершинами и кодом Прюфера является взаимно однозначным: каждому дереву соответствует уникальный код Прюфера, при этом номерам вершин сопоставляются элементы последовательности кода. Обратно, по заданному коду из $n-2$ чисел можно однозначно восстановить дерево с $n$ вершинами. Код был построен Хайнцем Прюфером при доказательстве формулы Кэли в 1918 году.

Построение

Пусть $T$ есть дерево с вершинами, занумерованными числами $\{1,2,\dots ,n\}$. Построение кода Прюфера дерева T ведётся путем последовательного удаления вершин из дерева, пока не останутся только две вершины. При этом каждый раз выбирается концевая вершина с наименьшим номером, и в код записывается номер единственной вершины, с которой она соединена. В результате образуется последовательность $(p_1,\dots ,p_{n-2})$, составленная из чисел $\{1,2,\dots ,n\}$, возможно с повторениями.

Пример

Для дерева на диаграмме вершина 1 является концевой вершиной с наименьшим номером, поэтому она удаляется первой, и 4 записывается в код Прюфера.

Вершины 2 и 3 удаляются следующими, так что 4 добавляется в код два раза.

Вершина 4 теперь стала концевой и имеет наименьший номер, поэтому она удаляется, а 5 добавляется в код.

Остались только две вершины, поэтому код записан полностью, и процесс останавливается.

В результате получается код Прюфера (4,4,4,5).

Восстановление дерева

Для восстановления дерева по коду $p=(p_1,\dots ,p_{n-2})$ заготовим список номеров вершин $s=(1,\dots ,n)$. Выберем первый номер $i_1$, который не встречается в коде. Добавим ребро $(i_1,p_1)$, после этого удалим $i_1$ из $s$ и $p_1$ из $p$.

Повторяем процесс до момента, когда код $p$ становится пустым. В этот момент список $s$ содержит ровно два числа $i_{n-1}$ и $n$. Остаётся добавить ребро $(i_{n-1},n)$, и дерево построено.

Свойства

• Если $d_i$ — это степень вершины с номером $i$, то $i$ встречается в коде Прюфера ровно ($d_i-1$) раз.

Приложения

• Из кода Прюфера следует Формула Кэли, то есть число остовных деревьев полного графа ${\mathrm{\Pi }}_n$ с $n$ вершинами равно $n^{n-2}$. Доказательство следует из того, что код Прюфера даёт биекцию между остовными деревьями и последовательностями длины $n-2$ из $n$ чисел.
• Код Прюфера также позволяет обобщить формулу Кэли на случай, если даны степени вершин, если $(d_1,\dots ,d_n)$ — это последовательность степеней дерева, то число деревьев с такими степенями равно мультиноминальному коэффициенту

$(\genfrac{}{}{0ex}{}{n-2}{d_1-1,d_2-1,\dots ,d_n-1})=\frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots (d_n-1)!}.$

• Код Прюфера используется для построений случайных деревьев.