Русская Википедия:Код Прюфера
Код Прюфера сопоставляет произвольному конечному дереву с <math>n</math> вершинами последовательность из <math>n-2</math> чисел (от <math>1</math> до <math>n</math>) с возможными повторениями. Отношение между деревом с помеченными вершинами и кодом Прюфера является взаимно однозначным: каждому дереву соответствует уникальный код Прюфера, при этом номерам вершин сопоставляются элементы последовательности кода. Обратно, по заданному коду из <math>n-2</math> чисел можно однозначно восстановить дерево с <math>n</math> вершинами. Код был построен Хайнцем Прюфером при доказательстве формулы Кэли в 1918 году.[1]
Построение
Пусть <math>T</math> есть дерево с вершинами, занумерованными числами <math>\{1,2,\dots,n\}</math>. Построение кода Прюфера дерева T ведётся путем последовательного удаления вершин из дерева, пока не останутся только две вершины. При этом каждый раз выбирается концевая вершина с наименьшим номером, и в код записывается номер единственной вершины, с которой она соединена. В результате образуется последовательность <math>(p_1,\dots,p_{n-2})</math>, составленная из чисел <math>\{1,2,\dots,n\}</math>, возможно с повторениями.
Пример
Файл:Tree graph Prufer code step 1.svg Файл:Tree graph Prufer code step 2.svg Файл:Tree graph Prufer code step 3.svg Файл:Tree graph Prufer code step 4.svg Файл:Tree graph Prufer code step 5.svg
Для дерева на диаграмме вершина 1 является концевой вершиной с наименьшим номером, поэтому она удаляется первой, и 4 записывается в код Прюфера.
Вершины 2 и 3 удаляются следующими, так что 4 добавляется в код два раза.
Вершина 4 теперь стала концевой и имеет наименьший номер, поэтому она удаляется, а 5 добавляется в код.
Остались только две вершины, поэтому код записан полностью, и процесс останавливается.
В результате получается код Прюфера (4,4,4,5).
Восстановление дерева
Для восстановления дерева по коду <math>p=(p_1,\dots,p_{n-2})</math> заготовим список номеров вершин <math>s=(1,\dots,n)</math>. Выберем первый номер <math>i_1</math>, который не встречается в коде. Добавим ребро <math>(i_1, p_1)</math>, после этого удалим <math>i_1</math> из <math>s</math> и <math>p_1</math> из <math>p</math>.
Повторяем процесс до момента, когда код <math>p</math> становится пустым. В этот момент список <math>s</math> содержит ровно два числа <math>i_{n-1}</math> и <math>n</math>. Остаётся добавить ребро <math>(i_{n-1},n)</math>, и дерево построено.
Файл:Prufer graph construction step 1.svg
Файл:Prufer graph construction step 2.svg
Файл:Prufer graph construction step 3.svg
Файл:Prufer graph construction step 4.svg
Файл:Prufer graph construction.svg
Свойства
- Если <math>d_i</math> — это степень вершины с номером <math>i</math>, то <math>i</math> встречается в коде Прюфера ровно (<math>d_i-1</math>) раз.
Приложения
- Из кода Прюфера следует Формула Кэли, то есть число остовных деревьев полного графа <math>\Pi_n</math> с <math>n</math> вершинами равно <math>n^{n-2}</math>. Доказательство следует из того, что код Прюфера даёт биекцию между остовными деревьями и последовательностями длины <math>n-2</math> из <math>n</math> чисел.
- Код Прюфера также позволяет обобщить формулу Кэли на случай, если даны степени вершин, если <math>(d_1,\dots,d_n)</math> — это последовательность степеней дерева, то число деревьев с такими степенями равно мультиноминальному коэффициенту
- <math>\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)!}.</math>
- Код Прюфера используется для построений случайных деревьев.
Ссылки
