Математика · объяснение и практика

Код Прюфера: восстановление дерева и подсчёт по степеням

Кодируем помеченное дерево удалением наименьшего листа, доказываем обратимость и получаем 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≥3 вершинах не содержит повторяющихся меток. Какое структурное следствие доказано?

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

Можно ли переставить числа кода и получить то же дерево?

В общем случае нет. Порядок определяет последовательность удалений и соседей; одинаковые частоты сохраняют степени, но не обязательно сами рёбра.

Формула считает деревья с назначенным корнем?

Нет. Метки заданы, но отдельный корень не выбирается. Если дополнительно свободно выбрать корень, число вариантов умножается на n.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться