Код Прюфера и деревья кратко

Привет, Вы узнаете о том , что такое код прюфера, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое код прюфера , настоятельно рекомендую прочитать все из категории Структуры данных.

код прюфера – это способ взаимно однозначного кодирования помеченных деревьев с 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

C++ реализация

Код функции

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 }

Применения

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

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

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