Определение. Кодом Прюфера длины n – 2 называется последовательность из чисел от 1 до n с повторениями.

Лемма. Количество кодов Прюфера длины n – 2 равно n^n-2.

Теорема. Существует взаимно однозначное соответствие между остовными деревьями для графа из n вершин и кодами Прюфера длины n – 2. По каждому дереву с n вершинами можно построить код Прюфера длины n – 2 и наоборот.

Следствие. Количество пронумерованых деревьев из n вершин равно n^n-2.

Алгоритм построения кода Прюфера по дереву

Вход: дерево с n вершинами.

Выход: код Прюфера длины n – 2.

Повторить n – 2 раза

Выбрать вершину v – лист дерева с наименьшим номером;

Добавить номер единственного соседа v в последовательность кода Прюфера;

Удалить вершину v из дерева;

Пример 1. Построение всех кодов Прюфера длины 2. Для этого следует рассмотреть все возможные деревья из 4 вершин. Под каждым деревом приведен соответствующий код.

Пример 2. Построить код Прюфера по дереву:

Скачать  подробное решение