Код Прюфера

Дерево с кодом Прюфера (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$) раз.

Приложения

• Из кода Прюфера следует Формула Кэли, то есть число остовных деревьев полного графа $\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)!}}.$

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