Введение

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

Алгоритм преобразования дерева в последовательность Пруфера

Можно сгенерировать последовательность Пруфера помеченного дерева путем итеративного удаления вершин из дерева, пока не останутся только две вершины. В частности, рассмотрим помеченное дерево T с вершинами {1, 2, ..., n}. На шаге i удалите лист с наименьшей меткой и установите i-й элемент последовательности Пруфера равным метке соседа этого листа. Последовательность Пруфера помеченного дерева уникальна и имеет длину n − 2. Как кодирование, так и декодирование могут быть сведены к сортировке по основанию для целых чисел и распараллелены.

Пример

Рассмотрим вышеуказанный алгоритм, примененный к дереву, показанному справа. Изначально вершина 1 является листом с наименьшей меткой, поэтому она удаляется первой, и 4 добавляется в последовательность Пруфера. Затем удаляются вершины 2 и 3, поэтому 4 добавляется еще дважды. Вершина 4 теперь является листом и имеет наименьшую метку, поэтому она удаляется, и мы добавляем 5 в последовательность. У нас остались только две вершины, поэтому мы останавливаемся. Последовательность для этого дерева — {4, 4, 4, 5}.

Формула Кейли

Последовательность Пруфера помеченного дерева на n вершинах — это уникальная последовательность длины n − 2, составленная из меток от 1 до n. Для заданной последовательности S длины n − 2, составленной из меток от 1 до n, существует единственное помеченное дерево, чья последовательность Пруфера равна S. Непосредственным следствием является то, что последовательности Пруфера устанавливают взаимно однозначное соответствие между множеством помеченных деревьев на n вершинах и множеством последовательностей длины n − 2, составленных из меток от 1 до n. Размер последнего множества равен n^(n−2), поэтому существование этого соответствия доказывает формулу Кейли, то есть, что существует n^(n−2) помеченных деревьев на n вершинах.