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

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

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

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

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

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

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

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

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

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

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

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

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

• Теория графов
• Деревья (графы)