Математика. Графы. Деревья. Код Хайнца Прюфера.

Код Прюфера однозначно сопоставляет произвольному конечному дереву последовательность; дереву с nn вершинами сопоставляется последовательность из n−2n−2 чисел от 11 до nn с возможными повторениями. Код может быть получен применением простого итерационного алгоритма; также есть алгоритм, восстанавливающий дерево по его коду Прюфера. Код Прюфера был использован Хайнцем Прюфером при доказательстве формулы Кэли в 1918 году.

Дерево – частный случай графа. Деревья широко применяются в программировании. Дерево – это связный граф без циклов. Дерево называется помеченным, если каждой вершине соответствует уникальная метка. Обычно это число.

Код Прюфера – это способ взаимно однозначного кодирования помеченных деревьев с n вершинами с помощью последовательности n-2 целых чисел в отрезке [1,n]. То есть, можно сказать, что код Прюфера – это биекция между всеми остовными деревьями полного графа и числовыми последовательностями.

Определение. Кодом Прюфера длины 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 из дерева;

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

Кодирование Прюфера переводит помеченные деревья порядка nn  в последовательность чисел от 11 до nn по алгоритму: Пока количество вершин больше двух:

1. Выбирается лист vv с минимальным номером.
2. В код Прюфера добавляется номер вершины, смежной с vv.
3. Вершина vv и инцидентное ей ребро удаляются из дерева.

Полученная последовательность называется кодом Прюфера (англ. Codes Priifer) для заданного дерева.