Формулировка $Кэли$. Число помеченных деревьев на n вершинах $метки\mathrm{1..}n$ равно n^{\,n-2}.

Доказательство $биекциячерезкодПрюфера$.

Код Прюфера: каждому помеченному дереву на вершинах {1,...,n} ставим в соответствие последовательность P = $p1,...,p_{n-2}$ длины n−2, где шаги такие:
Пока в дереве больше двух вершин: выбираем лист с наименьшей меткой u $вклассическомопределении—минимальнуюпометкевершинустепени1$, записываем метку его единственного соседа v в следующий элемент последовательности P, удаляем u $иребро(u,v)$.Повторяем, пока не останется два ребра; последовательность из n−2 записанных соседей — код Прюфера.Инвертируемость $восстановлениедереваизкода$: пусть дана последовательность P длины n−2 из элементов {1..n}. Восстановим дерево:
Для кажой вершины i задаём deg$$i$$ = 1 + number_of_occurrences$iвP$.Инициализируем структуру для быстрого извлечения минимальной вершины с deg = 1 $обычноmin-heapилиочередь/массивдляметок\mathrm{1..}n$.Для k = 1..n−2: извлечь минимальную вершину u с deg$$u$$=1, взять v = P$$k$$, добавить ребро $u,v$, decrement deg$$v$$; если deg$$v$$==1 — добавить v в множество листьев.В конце останутся ровно две вершины с deg=1; соединить их ребром.Бидективность доказана: код Прюфера строится однозначно; алгоритм восстановления даёт ровно то дерево, из которого получился код; поэтому это биекция между множеством помеченных деревьев на n вершинах и множеством последовательностей длины n−2 над алфавитом {1..n}. Число таких последовательностей = n^{n-2}. Следовательно, количество помеченных деревьев = n^{n-2}.

Альтернативный $алгебраический$ подход: матрица Лапласа и теорема о числе остовных деревьев $Matrix-Treetheorem$ дают, что для полного графа K_n число остовных деревьев равно любой нетривиальной копротяненной алгебре детерминанта, что вычисляется как n^{n-2}. Но доказательство через Прюфера проще конструктивно.

Пример $маленький$: n=4. Все последовательности длины 2 над {1,2,3,4} — 4^2 = 16. Каждая соответствует своему дереву; напр., код $2,2$ даёт дерево со степенями deg$2$=1+2=3, остальные 1 — звезда с центром 2.

Вычислительная сложность алгоритмов

1) Кодирование (дерево -> код):

Наивная реализация: поддерживать для дерева степени и множество листьев $минимальныйлистизвлекаем$, при каждом удалении обновлять соседа. Если множество листьев реализовано min-heap'ом $приоритетнаяочередь$ — O$nlogn$ по времени $вдеревеn-1ребро,выполняетсяO(n)извлеченийиO(n)вставок/обновлений$.Можно сделать O$n$ по времени: так как метки — целые 1..n, поддерживают массив степеней deg$$i$$ и линейную структуру для листьев $например,массивочередейпометкамилибитовыймассивсопоискомследующейединицы$ — при аккуратной реализации извлечение следующего минимального листа можно делать амортизировано O$1$, тогда весь алгоритм O$n$. Память O$n$.

2) Декодирование (код -> дерево):

Стандартный алгоритм $см.выше$: инициализация deg$$i$$ = 1 + countOccurrences$i$ $O(n)сподсчётом$, затем n−2 итераций: извлечь минимальный лист и соединить с текущим элементом P$$k$$. С min-heap — O$nlogn$, с специализированной структурой для меток 1..n — O$n$. Память O$n$.

Следствия и полезные формулы

Степени вершин в случайном $равновероятном$ помеченном дереве: deg$i$ = 1 + X_i, где X_i — число вхождений i в код Прюфера. Поскольку P — последовательность независимых выборов из {1..n}, $X_1,...,X_n$ имеют совместное распределение мультинономного типа с суммой n−2. Это даёт явные формулы на количество деревьев с заданной последовательностью степеней d1,...,dn $приsumd<em>i=2(n-1)$:
число = $n-2$! / ∏{i=1}^n $d_i-1$!
$получаетсяизчислаперестановоккода,дающегоэтивхождения$.Это удобно при перечислении деревьев с заданной степенной структурой.

Применения в алгоритмах и моделировании сетей

1) Генерация равномерно случайных деревьев:

Чтобы получить равномерно распределённое помеченное дерево на n вершинах, сгенерируйте P$$\mathrm{1..}n-2$$ как независимые равномерные целые в {1..n} $O(n)$, затем раскодируйте $O(n)$. Это даёт быстрый способ моделирования случайных топологий.

2) Анализ степенного распределения в случайных деревьях:

Поскольку deg$i$=1+count_in_code, степени распределены мультинономно; это позволяет задавать аналитические выводы $среднее,дисперсия,предельныераспределения$. Полезно при изучении случайных сетей, разветвляющихся структур.

3) Компактное кодирование деревьев:

Код Прюфера представляет помеченное дерево за n log n бит теоретически; практические компактные представления и хеширование используют сходные идеи.

4) Комбинаторика и химия:

Перечисление изомеров $алканов$ приближённо использует подсчёт деревьев $модификациидлявершинсограниченнойстепенью$. Формулы типа $n-2$! / ∏$d_i-1$! применяются для подсчёта структур.

5) Моделирование топологий сетей $симуляции$:

Для тестирования протоколов $распространениесообщений,маршрутизация,алгоритмыприема/передачи$, для генерации случайных деревянистых топологий $например,дляP2Poverlay,топологийраспределённыхвычислений$, моделирования процессов распространения по древовидным графам $эпидемии,потоксообщений$.

6) Теоретические алгоритмы:

Различные доказательства и конструкции $подсчётостовныхдеревьев,анализпространствдеревьев,перебордеревьевсзаданнымисвойствами$ используют код Прюфера как инструмент.

Кратко о практической реализации

Для n до миллионов алгоритм O$n$ $линейныйповремениипамяти$ вполне реализуем: массив подсчёта вхождений, массив очереди листьев $например,связныйсписокилиочередь+текущееположениедляпоискаследующегоминимального$ обеспечивает эффективную работу.Для разреженных меток или общих объектов $нечисловомаркированныхот1доn$ используют хеш-таблицы и приоритетную очередь — тогда сложность обычно O$nlogn$.

Итог

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