1. Главная
  2. Библиотека
  3. Информационные технологии
  4. Построить код Прюфера дерева с ребрами (1;2),(2;3),(3;7),(7;6),(6;4),(6;5),(7;8).

Построить код Прюфера дерева с ребрами (1;2),(2;3),(3;7),(7;6),(6;4),(6;5),(7;8).

«Построить код Прюфера дерева с ребрами (1;2),(2;3),(3;7),(7;6),(6;4),(6;5),(7;8).»
  • Информационные технологии

Условие:

Построить код прюфера дерева с ребрами (1;2),(2;3),(3;7),(7;6),(6;4),(6;5),(7;8).

Решение:

Мы имеем дерево с вершинами {1,2,3,4,5,6,7,8} и ребрами:   (1,2), (2,3), (3,7), (7,6), (6,4), (6,5), (7,8). Прежде чем начинать, определим степени вершин:  • 1: степень 1 (лист)  • 2: степень 2  • 3: степень 2  • 4: степень 1 (лист)  • 5: степень 1 (лист)  • 6: степень 3  • 7: степень 3  • 8: степень 1 (лист) Проверим, что дерево имеет 8 вершин, а длина кода Прюфера будет 8–2 = 6 чисел. Алгоритм построения кода Прюфера:  1. На каждом шаге выбираем вершину-лист с наименьшим номером.  2. Записываем её соседа (то есть вершину, с которой она соединена ребром).  3. Удаляем выбранную вершину-лист...

Похожие задачи

Не нашел нужную задачу?

Воспользуйся поиском

AI помощники

Выбери предмет

E
S
А
Б
В
Г
Д
Е
Ж
З
И
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Э
Я