Математика · объяснение и практика
Код Прюфера: восстановление дерева и подсчёт по степеням
Кодируем помеченное дерево удалением наименьшего листа, доказываем обратимость и получаем n^(n−2) и число деревьев с заданными степенями.

В теме Доказательства и комбинаторные модели · Учебная карта
Главная мысль
Деревьям с различными метками 1,…,n при n≥2 взаимно однозначно соответствуют последовательности длины n−2 из этих меток. Для построения кода удаляют наименьший текущий лист и записывают его соседа. Метка i встречается ровно deg(i)−1 раз. Поэтому деревьев n^(n−2), а заданные степени дают отдельный мультиномиальный подсчёт.
Записывается сосед удалённого листа
Дерево связно и не содержит циклов. При числе вершин хотя бы два у него есть листья, а удаление листа вместе с ребром оставляет дерево на остальных вершинах. Каждый раз выбираем лист с наименьшей меткой. Фиксированное правило необходимо: произвольный выбор листа давал бы одному дереву несколько возможных кодов.
После удаления листа записываем не его метку, а метку единственного соседа. Когда остаются две вершины, прекращаем запись. Выполнено ровно n−2 удалений, поэтому код имеет заданную длину. Повторение меток разрешено: одна центральная вершина может многократно оставаться соседом разных удаляемых листьев.
При n=2 код пуст, и единственное ребро восстанавливается по двум оставшимся меткам. Дерево на одной вершине рассматривается отдельно: формулу длины n−2 и обычный процесс для него не применяют.
Почему по коду восстанавливается ровно одно дерево
Каждая вершина i записывается за каждое удалённое соседнее ребро, пока сама не станет листом. Последнее её ребро исчезает при удалении самой вершины или остаётся последним ребром двух финальных вершин; за него i уже не записывается. Поэтому число появлений равно её исходной степени минус один.
Значит, метки, отсутствующие в текущем остатке кода, — листья текущего остатка дерева. Берём наименьшую такую метку среди ещё не удалённых, соединяем её с первым числом кода, удаляем выбранную метку и только первое число последовательности. Заново проверяем отсутствие в укороченном коде: сосед может теперь превратиться в лист.
Когда код пуст, соединяем две оставшиеся метки. На каждом шаге выбор однозначен, а вершина добавляется к ещё существующей части одним ребром, поэтому обратное построение даёт связное дерево без цикла. Кодирование вновь удалит именно восстановленный наименьший лист. Таким образом, процессы взаимно обратны, а не только дают одинаковое число шагов.
Пример
Восстановите дерево на шести метках по коду (4;4;2;4) и найдите степени 2 и 4.
Сначала отсутствуют 1,3,5,6, выбираем 1 и проводим 1−4. Затем минимальный отсутствующий 3 даёт 3−4. В остатке (2;4) выбираем 5 и соединяем 5−2. В остатке (4) выбираем 2 и соединяем 2−4. Последними остаются 4 и 6, добавляем 4−6. Метка 2 встретилась один раз, её степень 2; метка 4 три раза, её степень 4. Полученные пять рёбер непосредственно подтверждают эти значения.
Метки и степени определяют, что именно считается
На каждой из n−2 позиций кода допустима любая из n меток. Поэтому число помеченных деревьев равно n^(n−2). Это не число разных геометрических рисунков и не число непомеченных форм. Перестановка меток может давать другое дерево даже при той же форме ветвления.
Если заранее заданы степени d₁,…,dₙ≥1 с суммой 2n−2, метка i должна появиться dᵢ−1 раз. Число подходящих кодов равно (n−2)!/∏(dᵢ−1)!. При неправильной сумме или неположительной степени для n≥2 деревьев с таким профилем нет. Это условный подсчёт по подписанным вершинам, а не просто по неупорядоченному набору степеней.
Число различных меток, встречающихся в коде, показывает количество нелистовых вершин. Поэтому постоянный код описывает звезду с указанным центром, а код без повторений — дерево с максимальной степенью два, то есть путь. Эти выводы следуют из инварианта степеней без полного восстановления всех рёбер.
От чтения к действию
А теперь — вы
Частые вопросы
Можно ли переставить числа кода и получить то же дерево?
В общем случае нет. Порядок определяет последовательность удалений и соседей; одинаковые частоты сохраняют степени, но не обязательно сами рёбра.
Формула считает деревья с назначенным корнем?
Нет. Метки заданы, но отдельный корень не выбирается. Если дополнительно свободно выбрать корень, число вариантов умножается на n.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Чем минимальное остовное дерево отличается от кратчайших путей
Сравните сумму веса сети с длиной маршрута от одной вершины: постройте минимальный остов на собственном примере и проверьте, почему цели различаются.
Открыть темуПочему одинаковые элементы уменьшают число перестановок
Считаем разные строки из набора с одинаковыми символами, объясняем повторный счёт через временные метки и проверяем, какие перестановки действительно видимы.
Открыть тему