PROFILPELAJAR.COM

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

Построение

Пусть $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})$ — это последовательность степеней дерева, то число деревьев с такими степенями равно мультиноминальному коэффициенту