Пятница, 09.12.2016, 04:54
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 7
Гостей: 7
Пользователей: 0
» »
22:04
Постройте дерево, которому соответствует код

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

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. Построить дерево по коду Прюфера (3, 3, 4, 5, 4, 6).

Скачать решение, формат Word

 

Категория: Теория графов | Просмотров: 746 | Добавил: Admin | Теги: построить граф, построить дерево, найти код дерева | Рейтинг: 0.0/0


Похожие материалы:

Всего комментариев: 0
avatar
  .