Вопрос 40 из 42

Практика: доказательства и комбинаторные модели

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

От чтения к действию

А теперь — вы

Код дерева на n≥3 вершинах не содержит повторяющихся меток. Какое структурное следствие доказано?

Разберёмся в теме

Деревьям с различными метками 1,…,n при n≥2 взаимно однозначно соответствуют последовательности длины n−2 из этих меток. Для построения кода удаляют наименьший текущий лист и записывают его соседа. Метка i встречается ровно deg(i)−1 раз. Поэтому деревьев n^(n−2), а заданные степени дают отдельный мультиномиальный подсчёт.

Объяснение и примеры

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

Где найти подробное решение?

Перейдите по ссылке «Объяснение и примеры» над этим блоком. Там разобрана тема текущего вопроса.

Можно ли попробовать снова?

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