🔀 Дискретка

Код Прюфера

англ. Prüfer code

Биекция между помеченными деревьями на n вершинах и последовательностями длины n−2; из неё мгновенно следует формула Кэли n^(n−2) о числе деревьев.

Код Прюфера — способ записать помеченное дерево на $n$ вершинах последовательностью из $n - 2$ чисел. Кодирование: пока вершин больше двух, берём лист с наименьшим номером, выписываем номер его соседа и лист удаляем. Полученный кортеж восстанавливает дерево однозначно — это биекция между деревьями и последовательностями длины $n - 2$ . Отсюда мгновенно вытекает формула Кэли: помеченных деревьев на $n$ вершинах ровно $n^{n - 2}$ . Подробности теоремы — в термине теорема Кэли, свойства деревьев — в уроке деревья и алгоритмы.

Код не просто упражнение, а рабочая техника перебора: выбирать $n^{n - 2}$ деревьев через кортежи удобнее, чем генерировать графы напрямую. Из записи читаются степени: вершина появляется в коде столько раз, какова её степень минус единица, а листья — числа, вообще не встретившиеся в кортеже. Восстановление идёт тем же жадным процессом в обратную сторону и занимает линейное время с правильной структурой данных. Базовые определения — в термине дерево, а смежные подсчёты (деревья с заданными степенями) решаются мультиномиальными коэффициентами из урока перестановки, размещения, сочетания.

{деревья на n вершинах} \leftrightarrow {1, \dots, n}^{n - 2}, N = n^{n - 2}

биекция Прюфера: n−2 независимых выборов из n вариантов — и формула Кэли для числа помеченных деревьев готова

Частые вопросы

Как по коду Прюфера найти листья и степени вершин?

Листья — вершины, чьи номера не встречаются в коде: каждое вхождение вершины в запись «съедает» одно ребро к удалённому листу, поэтому степень равна числу вхождений плюс единица, а у отсутствующих в коде степень ровно один. Контрольная сумма: степени в сумме дают $2 (n - 1)$ — как у всякого дерева. Эта же карта «номер — степень» позволяет строить деревья с заранее заданным распределением степеней.

Зачем код Прюфера нужен на практике?

Три ответа. Подсчёт: биекция даёт формулу Кэли и её обобщения без единого перебора. Алгоритмика: случайное дерево строится выбором $n - 2$ случайных чисел — дешёвая выборка для тестирования и Монте-Карло. Олимпиадная техника: условия вида «перечислите деревья со свойством P» переводятся на язык кода, где свойство превращается в ограничение на вхождения чисел — и задача сводится к подсчёту последовательностей.