Определение. Кодом Прюфера длины n – 2 называется последовательность из чисел от 1 до n с повторениями.

Лемма. Количество кодов Прюфера длины n – 2 равно n^n-2.

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

Следствие. Количество пронумерованых деревьев из n вершин равно n^n-2.

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

Вход: дерево с n вершинами.

Выход: код Прюфера длины n – 2.

Повторить n – 2 раза

Выбрать вершину v – лист дерева с наименьшим номером;

Добавить номер единственного соседа v в последовательность кода Прюфера;

Удалить вершину v из дерева;

 

Пример 1. Построение всех кодов Прюфера длины 2. Для этого следует рассмотреть все возможные деревья из 4 вершин. Под каждым деревом приведен соответствующий код.

... Смотреть решение »

Алгоритм составления дерева по коду:

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. Построить дерево по к ... Смотреть решение »

Задана матрица инцидентности неориентированного графа G:

	e1	e2	e3	e4	e5
v1	1	1	0	1	0
v2	1	0	0	0	1
v3	0	1	1	0	0
v4	0	0	1	1	1

Постройте граф, соответствующий данной матрице.

... Смотреть решение »