Код Прюфера

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

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

Построение

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

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

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

Ссылки

1. Prüfer, H. Neuer Beweis eines Satzes über Permutationen (нем.) // Arch. Math. Phys.. — 1918. — Bd. 27. — S. 742—744.