По теме
Определение. Кодом Прюфера длины n – 2 называется последовательность из чисел от 1 до n с повторениями.
Лемма. Количество кодов Прюфера длины n – 2 равно nn-2.
Теорема. Существует взаимно однозначное соответствие между остовными деревьями для графа из n вершин и кодами Прюфера длины n – 2. По каждому дереву с n вершинами можно построить код Прюфера длины n – 2 и наоборот.
Следствие. Количество пронумерованых деревьев из n вершин равно nn-2.
Вход: дерево с n вершинами.
Выход: код Прюфера длины n – 2.
Повторить n – 2 раза
Выбрать вершину v – лист дерева с наименьшим номером;
Добавить номер единственного соседа v в последовательность кода Прюфера;
Удалить вершину v из дерева;
Пример 1. Построение всех кодов Прюфера длины 2. Для этого следует рассмотреть все возможные деревья из 4 вершин. Под каждым деревом приведен соответствующий код.
Если вам нужно решение этой задачи или похожего варианта, напишите условие ниже — рассчитаем стоимость и срок.