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

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

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

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

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

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

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

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

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

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

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

 

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

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

Категория: Теория графов | Просмотров: 7513 | Добавил: Admin | Дата: 08.02.2015 | Комментарии (0)

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

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

Категория: Теория графов | Просмотров: 3722 | Добавил: Admin | Дата: 08.02.2015 | Комментарии (0)

Задана матрица инцидентности неориентированного графа 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

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

... Смотреть решение »
Категория: Теория графов | Просмотров: 4246 | Добавил: Admin | Дата: 03.02.2015 | Комментарии (0)