Кодирование деревьев методом прюфера реферат

Обновлено: 04.07.2024

В математике , прюферово кодирование представляет собой способ компактно , описывающее дерево с пронумерованными вершинами. Эта кодировка представляет собой дерево из n пронумерованных вершин с последовательностью из n-2 членов. Данная последовательность P соответствует одному и только одному дереву, пронумерованному от 1 до n . п знак равно ( Икс 1 , Икс 2 , Икс 3 , . . . , Икс нет - 2 ) , x_ , x_ , . x_ )>

Последовательности Прюфера были впервые использованы Хайнцем Прюфером для демонстрации формулы Кэли в 1918 году. Их также можно использовать в компьютерном программировании для более компактной записи структуры дерева, чем с помощью указателей [см. необходимо] .

Резюме

Кодирование

Алгоритм

Последовательность Прюфера строится по следующему алгоритму :

Пример

Рассмотрим дерево на рисунке выше.

Вначале 1 - это лист с минимальным номером , таким образом, это тот лист , который снимают первым, а один кладет 4 (номер ветви, к которой он был подключен) в продолжение Прюфера.

Следующими удаляются вершины 2 и 3, и мы добавляем еще два раза по 4 к последовательности Прюфера.

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

Остались только две вершины, поэтому останавливаемся. Последовательность Прюфера, кодирующая дерево, имеет вид . п знак равно ( 4 , 4 , 4 , 5 )

Расшифровка - первый метод

Этот алгоритм основан на последовательности степеней каждой вершины дерева . D Т

Алгоритм

Дерево можно восстановить, используя следующий обратный алгоритм:

Пример

Обратите внимание на следующее . Это должно позволить нам реконструировать дерево на рисунке выше. п знак равно ( 4 , 4 , 4 , 5 )

На первом этапе мы создаем граф с шестью изолированными вершинами, пронумерованными от 1 до 6. Мы приписываем всем им степень по умолчанию, равную 1. Затем мы проходим P, увеличивая степень вершин, которые там появляются: мы увеличиваем три умноженное на степень вершины 4 и однажды на степень вершины 5. Наконец, мы имеем степени D = (1, 1, 1, 4, 2, 1).

На следующем этапе мы снова проходим P:

При x₁ = 4 ищем вершину с наименьшим номером степени, равным 1. Это вершина с номером 1, и мы соединяем вершины 1 и 4, уменьшая их степени. Теперь у нас есть степени D = (0, 1, 1, 3, 2, 1).
Для x₂ = 4 ищем вершину с наименьшим номером степени, равным 1. Это вершина с номером 2, и мы соединяем вершины 2 и 4, уменьшая их степени. Теперь у нас есть степени D = (0, 0, 1, 2, 2, 1).
Для x₃ = 4 ищем вершину с наименьшим номером степени, равным 1. Это вершина номер 3, и мы соединяем вершины 3 и 4, уменьшая их степени. Теперь у нас есть степени D = (0, 0, 0, 1, 2, 1).
При x₄ = 5 ищем вершину с наименьшим номером степени, равным 1. Это вершина с номером 4, и мы соединяем вершины 4 и 5, уменьшая их степени. Теперь у нас есть степени D = (0, 0, 0, 0, 1, 1).

Наконец, мы соединяем две оставшиеся вершины степени 1, а именно вершины чисел 5 и 6. Мы действительно восстановили исходное дерево T.

Расшифровка - второй метод

Вместо последовательности степеней от каждой вершины мы можем использовать последовательность вершин, которые мы еще не обработали. D я

Алгоритм

Дерево можно восстановить, используя следующий обратный алгоритм:

Пример

Обратите внимание на следующее . Это снова должно позволить нам реконструировать дерево на рисунке выше. п знак равно ( 4 , 4 , 4 , 5 )

Первоначально I = (1, 2, 3, 4, 5, 6). Потом:

Первый элемент Р равен 4 , и наименьший элемент I не появляются в P равно 1. соединяет вершины 1 и 4 в Т и удалены соответственно я и Р . В этот момент I = (2, 3, 4, 5, 6) и P = (4, 4, 5).
Первый элемент Р равен 4 , и наименьший элемент I не появляются в Р равно 2. соединяет вершины 2 и 4 в Т и удалены соответственно я и Р . В этот момент I = (3, 4, 5, 6) и P = (4, 5).
Первый элемент Р равен 4 , и наименьший элемент I не появляются в P равно 3. Она соединяет вершин 3 и 4 в Т и удалены соответственно I и P . На данный момент I = (4, 5, 6) и P = (5).
Единственный элемент P 5 и наименьший элемент I не появляются в P равно 4. Она соединяет пики 4 и 5 в Т и удалены , соответственно , из I и Р . В этот момент I = (5, 6) и P пусто.

Наконец, мы соединяем оставшиеся вершины 5 и 6. Мы воссоздали исходное дерево T.

Демонстрация формулы Кэли

Принцип демонстрации

Сначала покажем, что:

для дерева T существует только одна последовательность Прюфера P, описывающая T ;
для данной последовательности P длины n - 2 существует единственный граф T, пронумерованный от 1 до n, чья последовательность Прюфера равна P , и это дерево.

Таким образом, кодирование Прюфера обеспечивает взаимно однозначное соответствие между набором деревьев, пронумерованных n вершинами, и набором последовательностей длины n - 2, составленных из значений в интервале [1, n ]. Поскольку последний имеет элементы, и поскольку кодирование Прюфера биективно, это демонстрирует формулу Кэли. нет нет - 2 >

Расширение

Доказательство основано на том факте, что в продолжении Прюфера число встречается ровно раз. я d я - 1 -1>

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

Определение. Построение кода Прюфера для заданного дерева

Код Прюфера – это способ взаимно однозначного кодирования помеченных деревьев с n вершинами с помощью последовательности n-2 целых чисел в отрезке [1,n]. То есть, можно сказать, что код Прюфера – это биекция между всеми остовными деревьями полного графа и числовыми последовательностями.

Данный способ кодирования деревьев был предложен немецким математиком Хайнцом Прюфером в 1918 году.

Рассмотрим алгоритм построения кода Прюфера для заданного дерева с n вершинами.

На вход подается список ребер. Выбирается лист дерева с наименьшим номером, затем он удаляется из дерева, и к коду Прюфера добавляется номер вершины, которая была связана с этим листом. Эта процедура повторяется n-2 раза. В конце концов, в дереве останется только 2 вершины, и алгоритм на этом завершается. Номера оставшихся двух вершин в код не записываются.

Таким образом, код Прюфера для заданного дерева – это последовательность из n-2 чисел, где каждое число – номер вершины, связанной с наименьшим на тот момент листом – то есть это число в отрезке [1,n].

Пример

Исходное дерево

Код Прюфера: 1

Код Прюфера: 1 5

Код Прюфера: 1 5 2

Код Прюфера: 1 5 2 6

Код Прюфера: 1 5 2 6 6

Код Прюфера: 1 5 2 6 6 2

Код Прюфера: 1 5 2 6 6 2 1

Код Прюфера: 1 5 2 6 6 2 1 3

Восстановление дерева по его коду Прюфера

Рядом с задачей построения кода Прюфера стоит задача восстановления закодированного дерева. Будем рассматривать алгоритм восстановления дерева со следующими условиями: на вход подается последовательность цифр (вершин), которая представляет код Прюфера, результатом будет список ребер дерева. Таким образом, задача будет решена.

Рассмотрим алгоритм декодирования подробно. Помимо кода нам нужен список всех вершин графа. Мы знаем, что код Прюфера состоит из n-2 вершин, где n – это число вершин в графе. То есть, мы можем по размеру кода определить число вершин в закодированном дереве.

В результате, в начале работы алгоритма мы имеем массив из кода Прюфера размера n-2 и массив всех вершин графа: [1… n]. Далее n-2 раза повторяется такая процедура: берется первый элемент массива, содержащего код Прюфера, и в массиве с вершинами дерева производится поиск наименьшей вершины, не содержащейся в массиве с кодом. Найденная вершина и текущий элемент массива с кодом Прюфера составляют ребро дерева. Данные вершины удаляются из соответствующих массивов, и описанная выше процедура повторяется, пока в массиве с кодом не закончатся элементы. В конце работы алгоритма в массиве с вершинами графа останется две вершины, они составляют последнее ребро дерева. В результате получаем список всех ребер графа, который был закодирован.

Пример
Восстановим дерево по коду Прюфера, который был получен в примере кодирования.

Первый шаг
Код Прюфера: 1 5 2 6 6 2 1 3
Массив вершин дерева: 1 2 3 4 5 6 7 8 9 10
Минимальная вершина, не содержащаяся в коде Прюфера – это 4
Список ребер: 1 4

Второй шаг
Код Прюфера: 1 5 2 6 6 2 1 3
Массив вершин дерева: 1 2 3 4 5 6 7 8 9 10
Минимальная вершина, не содержащаяся в коде Прюфера – это 7
Список ребер: 1 4, 5 7

Третий шаг
Код Прюфера: 1 5 2 6 6 2 1 3
Массив вершин дерева: 1 2 3 4 5 6 7 8 9 10
Минимальная вершина, не содержащаяся в коде Прюфера – это 5
Список ребер: 1 4, 5 7, 2 5

Четвертый шаг
Код Прюфера: 1 5 2 6 6 2 1 3
Массив вершин дерева: 1 2 3 4 56 7 8 9 10
Минимальная вершина, не содержащаяся в коде Прюфера – это 8
Список ребер: 1 4, 5 7, 2 5, 6 8

Пятый шаг
Код Прюфера: 1 5 2 6 6 2 1 3
Массив вершин дерева: 1 2 3 4 56 7 8 9 10
Минимальная вершина, не содержащаяся в коде Прюфера – это 9
Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9

Шестой шаг
Код Прюфера: 1 5 2 6 6 2 1 3
Массив вершин дерева: 1 2 3 4 56 7 8 9 10
Минимальная вершина, не содержащаяся в коде Прюфера – это 6
Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6

Седьмой шаг
Код Прюфера: 1 5 2 6 6 2 1 3
Массив вершин дерева: 1 2 3 4 5 6 7 8 9 10
Минимальная вершина, не содержащаяся в коде Прюфера – это 2
Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2

Восьмой шаг
Код Прюфера: 1 5 2 6 6 2 1 3
Массив вершин дерева: 1 2 3 4 5 6 7 8 9 10
Минимальная вершина, не содержащаяся в коде Прюфера – это 1
Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2, 3 1

Завершение алгоритма
Код Прюфера: 1 5 2 6 6 2 1 3
Массив вершин дерева: 1 2 3 4 5 6 7 8 9 10
Минимальная вершина, не содержащаяся в коде Прюфера – это 1
Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2, 3 1, 3 10

Заключение

Код Прюфера был предложен как наглядное и простое доказательство формулы Кэли о числе помеченных деревьев. На практике же его используют чаще для решения комбинаторных задач.

Подсчет деревьев + последовательность Пруфера и примечания к исследованию формулы Кэли

Последовательность Пруфера может использоваться для решения некоторых задач по подсчету некорневых деревьев.

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

(1) Некорневые деревья преобразуются в последовательности Пруфера.

Сначала определите узел со степенью 1 в некорневом дереве как листовой узел.

Найдите лист с наименьшим номером и удалите его, добавьте номер подключенного узла к последовательности и повторяйте, пока не останется только 2 узла.

Последовательность пруфера, соответствующая дереву на рисунке ниже, - 3, 5, 1, 3.

Конкретная реализация может быть выполнена с набором для поддержания узла со степенью 1. Сложность - O (nlogn).

(2) Последовательность Пруфера преобразуется в некорневое дерево.

Установите значение V = , каждый раз вынимайте первый элемент u в последовательности Прюфера, найдите элемент v с наименьшим номером, который не появляется в последовательности Прюфера, и дайте u, V соедините ребра, а затем удалите их по отдельности, и, наконец, в V осталось два узла, соедините их ребрами. Конечный результат - дерево без корней.

Конкретная реализация также может использовать набор для поддержания чисел, которые не появляются в последовательности prufer. Сложность - O (nlogn).

Наконец, очень важным свойством является Количество вхождений определенного числа в последовательность Прюфера равно степени этого пронумерованного узла в некорневом дереве -1.

Некорневое дерево с n узлами однозначно соответствует последовательности длиной n-2, и каждое число в последовательности находится в диапазоне от 1 до n.

Приведенное выше предложение более важно. По приведенной выше теореме

1) Мы можем напрямую вывести количество остовных деревьев неориентированного полного графа с n точками: n ^ (n-2) То есть количество помеченных и некорневых деревьев с n точками.

2) Интересное обобщение состоит в том, что существуют некорневые деревья с n узлами степени D1, D2,…, Dn. (n-2)! / [ (D1-1)!(D2-1). (Dn-1)! ] Во-первых, потому что в это время число i в коде Прюфера встречается как Di-1 раз.

То есть существует n видов элементов, всего n-2, из которых i-й элемент имеет Di-1, найдите количество перестановок.

3) Степени n узлов равны D1, D2,…, Dn, так что есть m узлов с неизвестными степенями, найдите, сколько Посадить остовное дерево? (BZOJ1005 Очевидные беды)

Пусть степень каждого узла известной степени равна di, имеется n узлов и m узлов имеют неизвестную степень, left = (n-2) - (d1-1) - (d2-1) -. - (dk -1)

Возможные комбинации узлов с известными степенями следующие.

Остальные левые позиции случайным образом заполняются узлами неизвестной степени, а количество схем m ^ left

Яма для заполнения: Немаркированное некорневое дерево 、 Маркированное корневое дерево 、 Подсчет немаркированных корневых деревьев 。

Подсчет n точек с помеченными и корневыми деревьями: n ^ (n-2) * n = n ^ (n-1)

Подсчет непомеченных корневых деревьев в n точках:

Количество непомеченных и некорневых деревьев с n точками: a_nПодсчет непомеченных корневых деревьев с n точками.

Яма, которую нужно заполнить: считать, когда степень ограничена. Например, при подсчете алканов максимальная степень каждой точки равна 4.

Кодирование Прюфера переводит помеченные деревья порядка [math]n[/math] в последовательность чисел от [math]1[/math] до [math]n[/math] по алгоритму:
Пока количество вершин больше двух:

Выбирается лист [math]v[/math] с минимальным номером.
В код Прюфера добавляется номер вершины, смежной с [math]v[/math] .
Вершина [math]v[/math] и инцидентное ей ребро удаляются из дерева.

Полученная последовательность называется кодом Прюфера (англ. Prüfer code) для заданного дерева.

Номер вершины [math]v[/math] встречается в коде Прюфера тогда и только тогда, когда [math]v[/math] не является листом, причём встречается этот номер к коде дерева в точности [math]\deg v - 1[/math] раз.

Вершина с номером [math]n[/math] не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число [math]n[/math] встретилось в коде.
Если вершина не является листом, то у неё на некотором шаге была смежная вершина [math]-[/math] лист, следовательно номер этой вершины встречается в коде.
Если вершина является листом с номером меньше [math]n[/math] , то она была удалена до того, как был удален её сосед, следовательно её номер не встречается в коде.

По любой последовательности длины [math]n - 2[/math] из чисел от [math]1[/math] до [math]n[/math] можно построить помеченное дерево, для которого эта последовательность является кодом Прюфера.

Доказательство проведем по индукции по числу [math]n[/math]
База индукции:

[math]n = 1[/math] [math]-[/math] верно.

Индукционный переход:

Пусть для числа [math]n[/math] верно, построим доказательство для [math]n+1[/math] :

Пусть у нас есть последовательность: [math]A = [a_1, a_2, . a_].[/math]

Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка [math]n[/math] и последовательностями длиной [math]n - 2[/math] из чисел от [math]1[/math] до [math]n[/math]

Следствием из этой теоремы является формула Кэли.

В массиве вершин исходного дерева [math]V[/math] найдём вершину [math]v_[/math] с минимальным номером, не содержащуюся в массиве с кодом Прюфера [math]P[/math] , т.е. такую, что она является листом или концом уже добавленного в граф ребра, т.е. она стала листом в процессе построения кода Прюфера (по первому пункту построения). Вершина [math]p_1[/math] была добавлена в код Прюфера как инцидентная листу с минимальным номером (по второму пункту построения), поэтому в исходном дереве существует ребро < [math]p_1[/math] , [math]v_[/math] >, добавим его в список ребер. Удалим первый элемент из массива [math]Р[/math] , а вершину [math]v_[/math] - из массива [math]V[/math] т.к. она больше не может являться листом (по третьему пункту построения). Будем выполнять вышеуказанные действия, пока массив [math]P[/math] не станет пустым. В конце работы алгоритма в массиве [math]V[/math] останутся две вершины, составляющие последнее ребро дерева (это следует из построения).

Читайте также: