Лекция
Привет, Вы узнаете о том , что такое код прюфера, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое код прюфера , настоятельно рекомендую прочитать все из категории Структуры данных.
код прюфера – это способ взаимно однозначного кодирования помеченных деревьев с n вершинами с помощью последовательности n-2 целых чисел в отрезке [1,n]. То есть, можно сказать, что код Прюфера – это биекция между всеми остовными деревьями полного графа и числовыми последовательностями. Данный способ кодирования деревьев был предложен немецким математиком Хайнцом Прюфером в 1918 году. Код Прюфера сопоставляет произвольному конечному дереву с 
вершинами последовательность из 
чисел (от 
до ) с возможными повторениями. Отношение между деревом с помеченными вершинами и кодом Прюфера является взаимно однозначным: каждому дереву соответствует уникальный код Прюфера, при этом номерам вершин сопоставляются элементы последовательности кода. Обратно, по заданному коду из чисел можно однозначно восстановить дерево с вершинами. Код был построен Хайнцем Прюфером при доказательстве формулы Кэли в 1918 году.
Пусть 
есть дерево с вершинами, занумерованными числами 
. Построение кода Прюфера дерева T ведется путем последовательного удаления вершин из дерева, пока не останутся только две вершины. При этом каждый раз выбирается концевая вершина с наименьшим номером, и в код записывается номер единственной вершины, с которой она соединена. В результате образуется последовательность 
, составленная из чисел , возможно с повторениями.
Для дерева на диаграмме вершина 1 является концевой вершиной с наименьшим номером, поэтому она удаляется первой, и 4 записывается в код Прюфера.
Вершины 2 и 3 удаляются следующими, так что 4 добавляется в код два раза.
Вершина 4 сейчас теперь стала концевой и имеет наименьший номер, поэтому она удаляется, а 5 добавляется в код.
Остались только две вершины, поэтому код записан полностью, и процесс останавливается.
В результате получается код Прюфера (4,4,4,5).
Для восстановления дерева по коду 
заготовим список номеров вершин 
. Об этом говорит сайт https://intellect.icu . Выберем первый номер 
, который не встречается в коде. Добавим ребро 
, после этого удалим из 
и 
из 
.
Повторяем процесс до момента, когда код становится пустым. В этот момент список содержит ровно два числа 
и . Остается добавить ребро 
, и дерево построено.
— это степень вершины с номером 
, то встречается в коде Прюфера ровно (
) раз. 
Позвольте {a , a , ..., a[n]}быть последовательность Прюфера:
В дереве будут n+2узлы, пронумерованные от 1до n+2. Для каждого узла установите его степень равной количеству раз, которое он появляется в последовательности плюс 1. Например, в псевдокоде:
Преобразование Прюфера в дерево ( а ) 1 n ← длина [ a ] 2 T ← граф с n + 2 изолированными узлами, пронумерованными от 1 до n + 2 3 степень ← массив целых чисел 4 для каждого узла i в T - 5 градусов [ i ] ← 1 6 для каждого значения I в сделать 7 степень [ я ] ← степень [ я ] + 1
Затем для каждого числа в последовательности a[i]найдите первый (с наименьшим номером) узел jсо степенью, равной 1, добавьте ребро (j, a[i])к дереву и уменьшите степени jи a[i]. В псевдокоде:
8 для каждого значения i в a do 9 для каждого узла j в T do 10, если степень [ j ] = 1, то 11 Вставить ребро [ i , j ] в T 12 степень [ i ] ← степень [ i ] - 1 13 степень [ j ] ← степень [ j ] - 1 14 перерыв
В конце этого цикла останутся два узла со степенью 1 (назовем их u, v). Наконец, добавьте край (u,v)к дереву.
15 u ← v ← 0 16 для каждого узла i в T 17, если степень [ i ] = 1, то 18, если u = 0, то 19 u ← i 20 else 21 v ← i 22 break 23 Вставить ребро [ u , v ] в T 24 степень [ u ] ← степень [ u ] - 1 25 градус [ v ] ← градус [ v ] - 1 26 возврат T
0 #include
1 using namespace std;
2 void printTreeEdges(int prufer[], int m)
3 {
4 int vertices = m + 2;
5 int vertex_set[vertices];
6 for (int i=0; i
0 int main()
1 {
2 int prufer[] = {4, 1, 3, 4};
3 int n = sizeof(prufer)/sizeof(prufer );
4 printTreeEdges(prufer, n);
5 return 0;
6 }
с вершинами равно 
. Доказательство следует из того, что код Прюфера дает биекцию между остовными деревьями и последовательностями длины из чисел.
— это последовательность степеней дерева, то число деревьев с такими степенями равно мультиноминальному коэффициенту
Исследование, описанное в статье про код прюфера, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое код прюфера и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных
Из статьи мы узнали кратко, но содержательно про код прюфера
Комментарии