Условие:
Составить код прюфера по дереву с ребрами (5,7),(5,2),(2,1),(1,4),(1,3),(3,10),(2,6),(6,9),(6,8).
Решение:
Мы должны получить код Прюфера для заданного дерева с 10 вершинами. Напомним, что код Прюфера получается следующим алгоритмом: пока в дереве более двух вершин, находим вершину-листь (то есть вершину со степенью 1) с минимальным номером, записываем в код её соседа, а затем удаляем эту вершину из дерева, уменьшая степень соответствующего соседа. В итоге для дерева из n вершин получаем последовательность длины n–2.
Дано дерево с ребрами:
(5,7), (5,2), (2,1), (1,4), (1,3), (3,10), (2,6), (6,9), (6,8).
Первым делом определим, какие вершины и с кем соединены:
- Вершина 1: соседями 2, 4, 3
2....