Условие:
Построить код прюфера дерева с ребрами (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. Удаляем выбранную вершину-лист...