Код Прюфера
Время на прочтение
3 мин
Количество просмотров 69K
Деревья. Кратко напомним
Дерево – частный случай графа. Деревья широко применяются в программировании. Дерево – это связный граф без циклов. Дерево называется помеченным, если каждой вершине соответствует уникальная метка. Обычно это число.
Определение. Построение кода Прюфера для заданного дерева
Код Прюфера – это способ взаимно однозначного кодирования помеченных деревьев с 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
Заключение
Код Прюфера был предложен как наглядное и простое доказательство формулы Кэли о числе помеченных деревьев. На практике же его используют чаще для решения комбинаторных задач.
Источники
- Уилсон Р. Введение в теорию графов. Перевод с англ. М.: Мир, 1977. -208 с.
- Комбинаторика. Булевы функции. Графы: учеб. пособие / А. А. Балагура, О. В. Кузьмин. – Иркутск: Изд-во ИГУ, 2012. – 115 с.
- MAXimal [Электронный ресурс] — Режим доступа: ссылка, свободный. (дата обращения: 22.04.2017)
Содержание
- 1 Алгоритм построения кодов Прюфера
- 2 Пример построения кода Прюфера
- 3 Алгоритм декодирования кодa Прюфера
- 3.1 Реализация
- 4 Пример декодирования кода Прюфера
- 5 См. также
- 6 Источники информации
Алгоритм построения кодов Прюфера
Кодирование Прюфера переводит помеченные деревья порядка в последовательность чисел от до по алгоритму:
Пока количество вершин больше двух:
- Выбирается лист с минимальным номером.
- В код Прюфера добавляется номер вершины, смежной с .
- Вершина и инцидентное ей ребро удаляются из дерева.
Полученная последовательность называется кодом Прюфера (англ. Prüfer code) для заданного дерева.
| Лемма: |
|
Номер вершины встречается в коде Прюфера тогда и только тогда, когда не является листом, причём встречается этот номер к коде дерева в точности раз. |
| Доказательство: |
Таким образом, номера всех вершин, не являющихся листьями или имеющих номер , встречаются в коде Прюфера, а остальные нет. |
| Лемма: |
|
По любой последовательности длины из чисел от до можно построить помеченное дерево, |
| Доказательство: |
|
Доказательство проведем по индукции по числу верно. Индукционный переход: Пусть для числа верно, построим доказательство для : Пусть у нас есть последовательность: Выберем минимальное число не лежащее в . По предыдущей лемме вершина, которую мы удалили первой. Соединим и ребром. Выкинем из последовательности число . Перенумеруем вершины, для всех заменим на . А теперь мы можем применить предположение индукции. |
| Теорема: |
|
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка и последовательностями длиной из чисел от до |
| Доказательство: |
|
Следствием из этой теоремы является формула Кэли.
Пример построения кода Прюфера
Алгоритм декодирования кодa Прюфера
В массиве вершин исходного дерева найдём вершину с минимальным номером, не содержащуюся в массиве с кодом Прюфера , т.е. такую, что она является листом или концом уже добавленного в граф ребра, т.е. она стала листом в процессе построения кода Прюфера (по первому пункту построения). Вершина была добавлена в код Прюфера как инцидентная листу с минимальным номером (по второму пункту построения), поэтому в исходном дереве существует ребро {, }, добавим его в список ребер. Удалим первый элемент из массива , а вершину — из массива т.к. она больше не может являться листом (по третьему пункту построения). Будем выполнять вышеуказанные действия, пока массив не станет пустым. В конце работы алгоритма в массиве останутся две вершины, составляющие последнее ребро дерева (это следует из построения).
Реализация
# P - код Прюфера
# V - вершины
function buildTree(P, V):
while not P.empty():
u = P[0]
v = min(x V: P.count(x) == 0)
G.push({u, v})
P.erase(0)
V.erase(indexOf(v))
G.push({v[0], v[1]})
return G
Пример декодирования кода Прюфера
См. также
- Связь матрицы Кирхгофа и матрицы инцидентности
- Матрица Кирхгофа
- Количество помеченных деревьев
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
Источники информации
- Университет INTUIT | Представление с помощью списка ребер и кода Прюфера
Немецкий математик
К.Прюфер изобрёл способ представления
любых деревьев и ордеревьев. Изложим
алгоритм построения кода Прюфера.
Пусть имеется
дерево с n
пронумерованными вершинами. В списке
всех вершин слева направо ищем первую
висячую вершину. Пусть это a1.
Ищем
единственную вершину b1
с которой смежна a1.
Величину b1
заносим в новый список – будущий код
Прюфера, а вершину a1
вычеркиваем и из списка, и из дерева.
Этот процесс повторяем n-2
раза. В результате получим новый список.
{b1,
b2,…,
bn-2}
– это и есть код Прюфера. Заметим, что
в процессе построения дерево все время
уменьшается, и возникают новые висячие
вершины
Пример.
Построить код
Прюфера для дерева.
Список всех вершн
1
2
3
4
5
6 7.
N=7;
отсюда n-2=5.
В этом списке слева
направо ищем первую висячую.
{1; 1; 6; 2; 6;} – код
Прюфера.
Доказано, что код
Прюфера определяет дерево однозначно.
Более того, любой список { b1,
b2,..,bn-2}
чисел от 1 до n
является кодом Прюфера некоторого
дерева.
Пример 2.
Восстановить
дерево по коду Прюфера.
{1;
3; 6; 5; 3; 2; 7;}
n-2=7;
n=9.
1
2
3
4
5
6
7 8
9
Введем
понятие неприкосновенной вершины: если
вершина встречается в коде Прюфера
дальше, то она неприкосновенна
Д
обавляем
оставшиеся вершины.
Перестроим
дерево.
Теорема
Кэш.
Общее
число деревьев с n
пронумерованными вершинами равно nn-2/
Доказательство.
Таких
деревьев ровно столько, сколько кодов
Прюфера. b
– число от 1 до n.
По
правилу произведения nn-2
Например,
для n=5,
получим 55-2=152
раз.
3.6. Обход деревьев.
Часто
необходимо обойти все вершины дерева
или ордерева не хаотично, а по определённому
алгоритму.
Самые
простые алгоритмы обхода для бинарного
ордерева. Из 3 на выбор.
1)Прямой
метод – обойти корень, затем левое
поддерево, затем правое (КЛП)
Этот
принцип соблюдается в любой момент
времени.
2)Обратный
метод: обойти левое поддерево, корень,
правое поддерево (ЛКП)
3)Концевой
метод: обойти левое поддерево, правое,
корень (ЛПК)
Обойти
3 способам данное бинарное дерево (не
менее 10 вершин)
1
)
Прямой
(КЛП)
a b d e f c g h I k
2)
Обратный
(ЛКП)
d b f e a g c I h k
3)
Концевой
(ЛПК)
d f e b g I k h c a
Для
не бинарных деревьев и ордеревьев
алгоритм гораздо сложнее.
3.7. Деревья и списки.
Бытовое
понятие списков всем известно, но в
информатике имеется формальное понятие
списка.
Опр.
Назовем атомом любой неделимый объект
(букву, цифру и т.д.). Списками называется
последовательность атомов и списков,
разделенных запятыми и заключенными в
общие скобки.
Это
так называемая рекурсивное определение
(использующие само себя). В математике
это запрещается, а информатике широко
применяется.
Примеры
списков.
Атомы
– буквы.
-
(а)
-
(a,b)
-
(a,b,c)
-
(a,
(b,c)) -
((a,b),c)
-
(a,((b,c),d),((e,f),g))
Каждому списку
можно сопоставить ордерево, действуя
по правилу
Атомом или списком,
заключенным в общие скобки, соответствует
общая безымянная вершина, потомками
которой они являются.
П
ример.
Видим, что атомам
соответствуют только висячие вершины
дерева. Поэтому обратная связь такова:
каждому дереву соответствует список
его висячих вершин.
Вводится понятие
глубины списка: наибольшее число
вложенных друг в друга скобок.
При этом глубина
списка совпадает с глубиной соответствующего
дерева (число уровней).
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
- #
Алгоритм составления дерева по коду:
1.Выписываем висячие вершины, всего вершин на 2 больше чем значений в коде дерева.
2. находим наименьшее натуральное число, которое не встречается в последовательности.
3. это число – номер вершины, которую необходимо соединить с вершиной, которая встречается первой в коде.
4. находим следующее число.
и т.д.
Рассмотрим применение данного алгоритма на примере.
Пример 1. Постройте дерево, которому соответствует код {1, 2, 2, 1, 1}
Решение.
1. Выписываем висячие вершины. Всего вершин на 2 больше чем значений в коде дерева, в данном случае такими будут 3,4,5,6,7.
2. Вершину с минимальным номером (3) соединяем с первым значением кода (1).
3. Поскольку вершина (1) еще встречается в коде , то соединяем следующую висячую вершину (4) с вершиной из кода (2).
Повторяем для 5-2.
Дальше вершины (2) больше нет в коде, потому она становится висячей с наименьшим номером, потому следующим шагом я соединяю ее (2) со следующим значением кода (1).
Далее 6 – 7. Код закончился, осталась 6. Соединяем ее с 1.
Дерево построено.
Пример 2. Построить дерево по к … Смотреть решение »
Improve Article
Save Article
Like Article
Improve Article
Save Article
Like Article
Given an integer N, the task is to generate a random labelled tree of N node with (N – 1) edges without forming cycle.
Note: The output generated below is random which may not match with the output generated by the code.
Examples:
Input: N = 3
Output:
1 3
1 2
Input: N = 5
Output:
3 2
4 3
1 4
1 5
This approach uses the Prüfer Sequence to generate random trees.
What is a Prüfer Sequence?
In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labelled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n – 2 and can be generated by a simple iterative algorithm.
If the number of nodes is N then the Prüfer Sequence is of length (N – 2) and each position can have N possible values. So the number of the possible labeled trees with N Nodes is N(N – 2).
How Random Trees are generated using Prüfer Sequence?
Generally, Random Tree Generation with N nodes is done in the following steps:
- Generate a Random Sequence
S = {s1, s2, s3.....sn-2}
where each element of the sequence si ∈ {1, 2, 3, … N} where repetition of elements is allowed
- Generate Tree from the generated Prüfer Sequence S:
- Create N nodes with values {1, 2, 3, … N}
- Find smallest element X such that X ∈ {1, 2, 3, … N} and X ∉ S
- Join Node with value X to the node with value s1
- Delete s1 from S
- Repeat the same process from step 2 with until the Prüfer Sequence is empty.
For Example:
- Number of Nodes = 3
- Then the Prüfer Sequence will be of length (N – 2), as in this case it will be of 1 and the possible values it can have {1, 2, 3}.
- Possible Random Sequences will be {{1}, {2}, {3}}.
Below is the implementation of the above approach.
C++
#include<bits/stdc++.h>
using namespace std;
void printTreeEdges(vector<int> prufer, int m)
{
int vertices = m + 2;
vector<int> vertex_set(vertices);
for (int i = 0; i < vertices; i++)
vertex_set[i] = 0;
for (int i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
cout<<("nThe edge set E(G) is:n");
int j = 0;
for (int i = 0; i < vertices - 2; i++)
{
for (j = 0; j < vertices; j++)
{
if (vertex_set[j] == 0)
{
vertex_set[j] = -1;
cout<<"(" << (j + 1) << ", "
<< prufer[i] << ") ";
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
for (int i = 0; i < vertices; i++)
{
if (vertex_set[i] == 0 && j == 0)
{
cout << "(" << (i + 1) << ", ";
j++;
}
else if (vertex_set[i] == 0 && j == 1)
cout << (i + 1) << ")n";
}
}
int ran(int l, int r)
{
return l + (rand() % (r - l + 1));
}
void generateRandomTree(int n)
{
int length = n - 2;
vector<int> arr(length);
for (int i = 0; i < length; i++)
{
arr[i] = ran(0, length + 1) + 1;
}
printTreeEdges(arr, length);
}
int main()
{
srand(time(0));
int n = 5;
generateRandomTree(n);
return 0;
}
Java
import java.util.Arrays;
import java.util.Random;
class GFG {
static void printTreeEdges(int prufer[], int m)
{
int vertices = m + 2;
int vertex_set[] = new int[vertices];
for (int i = 0; i < vertices; i++)
vertex_set[i] = 0;
for (int i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
System.out.print("nThe edge set E(G) is:n");
int j = 0;
for (int i = 0; i < vertices - 2; i++) {
for (j = 0; j < vertices; j++) {
if (vertex_set[j] == 0) {
vertex_set[j] = -1;
System.out.print("(" + (j + 1) + ", "
+ prufer[i] + ") ");
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
for (int i = 0; i < vertices; i++) {
if (vertex_set[i] == 0 && j == 0) {
System.out.print("(" + (i + 1) + ", ");
j++;
}
else if (vertex_set[i] == 0 && j == 1)
System.out.print((i + 1) + ")n");
}
}
static void generateRandomTree(int n)
{
Random rand = new Random();
int length = n - 2;
int[] arr = new int[length];
for (int i = 0; i < length; i++) {
arr[i] = rand.nextInt(length + 1) + 1;
}
printTreeEdges(arr, length);
}
public static void main(String[] args)
{
int n = 5;
generateRandomTree(n);
}
}
Python3
import random
def print_tree_edges(prufer, m):
vertices = m + 2
vertex_set = [0] * vertices
for i in range(vertices):
vertex_set[i] = 0
for i in range(vertices - 2):
vertex_set[prufer[i] - 1] += 1
print("nThe edge set E(G) is:")
j = 0
for i in range(vertices - 2):
for j in range(vertices):
if vertex_set[j] == 0:
vertex_set[j] = -1
print("({}, {})".format(j + 1, prufer[i]), end=" ")
vertex_set[prufer[i] - 1] -= 1
break
j = 0
for i in range(vertices):
if vertex_set[i] == 0 and j == 0:
print("({}, ".format(i + 1), end="")
j += 1
elif vertex_set[i] == 0 and j == 1:
print("{})".format(i + 1))
def generate_random_tree(n):
length = n - 2
arr = [0] * length
for i in range(length):
arr[i] = random.randint(1, length + 1)
print_tree_edges(arr, length)
n = 5
generate_random_tree(n)
C#
using System;
class GFG
{
static void printTreeEdges(int []prufer, int m)
{
int vertices = m + 2;
int []vertex_set = new int[vertices];
for (int i = 0; i < vertices; i++)
vertex_set[i] = 0;
for (int i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
Console.Write("nThe edge set E(G) is:n");
int j = 0;
for (int i = 0; i < vertices - 2; i++)
{
for (j = 0; j < vertices; j++)
{
if (vertex_set[j] == 0)
{
vertex_set[j] = -1;
Console.Write("(" + (j + 1) + ", "
+ prufer[i] + ") ");
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
for (int i = 0; i < vertices; i++)
{
if (vertex_set[i] == 0 && j == 0)
{
Console.Write("(" + (i + 1) + ", ");
j++;
}
else if (vertex_set[i] == 0 && j == 1)
Console.Write((i + 1) + ")n");
}
}
static void generateRandomTree(int n)
{
Random rand = new Random();
int length = n - 2;
int[] arr = new int[length];
for (int i = 0; i < length; i++)
{
arr[i] = rand.Next(length + 1) + 1;
}
printTreeEdges(arr, length);
}
public static void Main(String[] args)
{
int n = 5;
generateRandomTree(n);
}
}
Javascript
<script>
function printTreeEdges(prufer,m)
{
let vertices = m + 2;
let vertex_set = new Array(vertices);
for (let i = 0; i < vertices; i++)
vertex_set[i] = 0;
for (let i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
document.write("<br>The edge set E(G) is:<br>");
let j = 0;
for (let i = 0; i < vertices - 2; i++) {
for (j = 0; j < vertices; j++) {
if (vertex_set[j] == 0) {
vertex_set[j] = -1;
document.write("(" + (j + 1) + ", "
+ prufer[i] + ") ");
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
for (let i = 0; i < vertices; i++) {
if (vertex_set[i] == 0 && j == 0) {
document.write("(" + (i + 1) + ", ");
j++;
}
else if (vertex_set[i] == 0 && j == 1)
document.write((i + 1) + ")<br>");
}
}
function generateRandomTree(n)
{
let length = n - 2;
let arr = new Array(length);
for (let i = 0; i < length; i++) {
arr[i] = Math.floor(Math.random()*(length + 1)) + 1;
}
printTreeEdges(arr, length);
}
let n = 5;
generateRandomTree(n);
</script>
Output:
The edge set E(G) is: (2, 4) (4, 3) (3, 1) (1, 5)
Time Complexity: O(N*N)
Auxiliary Space: O(N)
Last Updated :
10 Jan, 2023
Like Article
Save Article
Vote for difficulty
Current difficulty :
Basic