Код Прюфера

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

Код Прюфера однозначно сопоставляет произвольному конечному дереву последовательность; дереву с $n$ вершинами сопоставляется последовательность из $n-2$ чисел от $1$ до $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$ раз.

Приложения

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

${\binom {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)!}}.$

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