Открыть главное меню
Дерево с кодом Прюфера (4,4,4,5).

Код Прюфера однозначно сопоставляет произвольному конечному дереву последовательность: дереву с вершинами сопоставляется последовательность из чисел от до с возможными повторениями. Код может быть получен применением простого итерационного алгоритма; также есть алгоритм, восстанавливающий дерево по его коду Прюфера.

Код Прюфера был использован Хайнцем Прюфером при доказательстве формулы Кэли в 1918 году.[1]

Содержание

ПостроениеПравить

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

ПримерПравить

         


Для дерева на диаграмме вершина 1 является концевой вершиной с наименьшим номером, поэтому она удаляется и 4 ставится в код Прюфера.

Вершины 2 и 3 удаляются в следующем, так что 4 добавляется в два раза.

Вершина 4 сейчас теперь стала концевой и имеет наименьший номер, поэтому её удаляем и мы добавляем 5 к последовательности.

Мы остались только с двумя вершинами, поэтому мы останавливаемся.

В результате код Прюфера (4,4,4,5).

Восстановление дереваПравить

Для восстановления дерева по коду  , заготовим список номеров вершин  . Выберем первый номер  , который не встречается в коде. Добавим ребро  , после этого удалим   из   и   из  .

Повторяем процесс до момента, когда код   становится пустым. В этот момент список   содержит ровно два числа   и  . Остаётся добавить ребро  , и дерево построено.


         

СвойстваПравить

  • Если   — это степень вершины с номером  , то   встречается в коде Прюфера   раз.

ПриложенияПравить

  • Из кода Прюфера следует Формула Кэли, то есть число остовных деревьев полного графа   с   вершинами равно  . Доказательство следует из того, что код Прюфера даёт биекцию между остовными деревьями и последовательностями длины   из   чисел.
    • Код Прюфера также позволяет обобщить формулу Кэли на случай, если даны степени вершин, если   это последовательность степеней дерева, то число деревьев с такими степенями равно мультиноминальному коэффициенту
 
  • Код Прюфера используется для построений случайных деревьев.

СсылкиПравить

  1. Prüfer, H. (1918). «Neuer Beweis eines Satzes über Permutationen». Arch. Math. Phys. 27: 742–744.