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

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

Рассмотрим алгоритм декодирования подробно. Помимо кода нам нужен список всех вершин графа. Мы знаем, что код Прюфера состоит из 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

Заключение

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

Источники

1. Уилсон Р. Введение в теорию графов. Перевод с англ. М.: Мир, 1977. -208 с.
2. Комбинаторика. Булевы функции. Графы: учеб. пособие / А. А. Балагура, О. В. Кузьмин. – Иркутск: Изд-во ИГУ, 2012. – 115 с.
3. MAXimal [Электронный ресурс] — Режим доступа: ссылка, свободный. (дата обращения: 22.04.2017)