WikiSort.ru - Не сортированное

Код Прюфера однозначно сопоставляет произвольному конечному дереву последовательность: дереву с ${\displaystyle n}$ вершинами сопоставляется последовательность из ${\displaystyle n-2}$ чисел от ${\displaystyle 1}$ до ${\displaystyle n}$ с возможными повторениями. Код может быть получен применением простого итерационного алгоритма; также есть алгоритм, восстанавливающий дерево по его коду Прюфера.

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

Построение

Пусть ${\displaystyle T}$ есть дерево с вершинами, занумерованными числами ${\displaystyle \{1,2,\dots ,n\}}$ . Построение кода Прюфера дерева T ведётся путем последовательного удаления вершин из дерева, пока не останутся только две вершины. При этом каждый раз выбирается концевая вершина с наименьшим номером и в код записывается номер единственной вершины, с которой она соединена. В результате получаем последовательность ${\displaystyle (p_{1},\dots ,p_{n-2})}$ , составленную из чисел ${\displaystyle \{1,2,\dots ,n\}}$ , возможно с повторениями.

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

Для восстановления дерева по коду ${\displaystyle p=(p_{1},\dots ,p_{n-2})}$ , заготовим список номеров вершин ${\displaystyle s=(1,\dots ,n)}$ . Выберем первый номер ${\displaystyle i_{1}}$ , который не встречается в коде. Добавим ребро ${\displaystyle (i_{1},p_{1})}$ , после этого удалим ${\displaystyle i_{1}}$ из ${\displaystyle s}$ и ${\displaystyle p_{1}}$ из ${\displaystyle p}$ .

Повторяем процесс до момента, когда код ${\displaystyle p}$ становится пустым. В этот момент список ${\displaystyle s}$ содержит ровно два числа ${\displaystyle i_{n-1}}$ и ${\displaystyle n}$ . Остаётся добавить ребро ${\displaystyle (i_{n-1},n)}$ , и дерево построено.

Свойства

• Если ${\displaystyle d_{i}}$ — это степень вершины с номером ${\displaystyle i}$ , то ${\displaystyle i}$ встречается в коде Прюфера ${\displaystyle d_{i}-1}$ раз.

Приложения

• Из кода Прюфера следует Формула Кэли, то есть число остовных деревьев полного графа ${\displaystyle \Pi _{n}}$ с ${\displaystyle n}$ вершинами равно ${\displaystyle n^{n-2}}$ . Доказательство следует из того, что код Прюфера даёт биекцию между остовными деревьями и последовательностями длины ${\displaystyle n-2}$ из ${\displaystyle n}$ чисел.
  • Код Прюфера также позволяет обобщить формулу Кэли на случай, если даны степени вершин, если ${\displaystyle (d_{1},\dots ,d_{n})}$ это последовательность степеней дерева, то число деревьев с такими степенями равно мультиноминальному коэффициенту

${\displaystyle {\binom {n-2}{d_{1}-1,\,d_{2}-1,\,\dots ,\,d_{n}-1}}={\frac {(n-2)!}{(d_{1}-1)!(d_{2}-1)!\cdots (d_{n}-1)!}}.}$

• Код Прюфера используется для построений случайных деревьев.

Ссылки