Вопрос 40 из 42
Практика: доказательства и комбинаторные модели
Код Прюфера: восстановление дерева и подсчёт по степеням
От чтения к действию
А теперь — вы
Разберёмся в теме
Деревьям с различными метками 1,…,n при n≥2 взаимно однозначно соответствуют последовательности длины n−2 из этих меток. Для построения кода удаляют наименьший текущий лист и записывают его соседа. Метка i встречается ровно deg(i)−1 раз. Поэтому деревьев n^(n−2), а заданные степени дают отдельный мультиномиальный подсчёт.
Частые вопросы
Где найти подробное решение?
Перейдите по ссылке «Объяснение и примеры» над этим блоком. Там разобрана тема текущего вопроса.
Можно ли попробовать снова?
Да. После проверки можно изменить ответ. Переход к следующему вопросу не блокируется результатом, а личный счёт не сохраняется.