Interested Article - Код Прюфера

Дерево с кодом Прюфера (4,4,4,5).

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

Построение

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

Пример


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

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

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

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

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

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

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

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


Свойства

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

Приложения

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

Ссылки

  1. Prüfer, H. Neuer Beweis eines Satzes über Permutationen (нем.) // Arch. Math. Phys.. — 1918. — Bd. 27 . — S. 742—744 .
Источник —

Same as Код Прюфера