Дано: код Прюфера 4 3 3 2.
Найти: дерево, соответствующее данному коду Прюфера.
Решение:
1. Определим количество вершин в дереве. Если у нас есть код Прюфера длиной n, то количество вершин в дереве будет равно n + 2. В данном случае длина кода равна 4, следовательно:
Количество вершин = 4 + 2 = 6.
2. Запишем элементы кода Прюфера: 4, 3, 3, 2.
3. Теперь найдем все вершины, которые включены в код Прюфера и добавим две дополнительные вершины, которые не входят в код. Элементы кода: 2, 3, 4.
Полный набор вершин от 1 до 6:
Вершины: 1, 2, 3, 4, 5, 6.
Вершины из кода: 2, 3, 4.
Не входящие в код: 1, 5, 6.
4. Подсчитываем количество появлений каждой вершины в коде Прюфера:
- Вершина 2: 1 раз
- Вершина 3: 2 раза
- Вершина 4: 1 раз
- Вершины 1, 5, 6: 0 раз
5. Находим все вершины с нулевыми счетчиками (которые не встречаются в коде) и соединяем их с вершинами из кода, пока не получим n-1 рёбер:
- Первая итерация:
Нужные рёбра:
- Соединяем 1 (ноль раз) с 2 (один раз). Ребро: (1, 2).
- Удаляем 2 из кода.
- Вторая итерация:
Остаток кода: 3, 3, 4.
Нужные рёбра:
- Теперь 5 (ноль раз) соединяем с 3 (два раза). Ребро: (5, 3).
- Удаляем 3 один раз. Остаток: 3, 4.
- Третья итерация:
- Теперь соединяем 6 (ноль раз) с 3 (остался один раз). Ребро: (6, 3).
- Удаляем 3. Остаток: 4.
- Четвертая итерация:
- Остаётся 4. Соединяем 4 с 5 (уже соединена). Ребро: (4, 5).
6. В итоге мы получили следующие рёбра дерева:
- (1, 2)
- (5, 3)
- (6, 3)
- (4, 3)
Ответ:
Дерево, соответствующее коду Прюфера 4 3 3 2, имеет следующие рёбра:
- (1, 2)
- (5, 3)
- (6, 3)
- (4, 3)
Таким образом, дерево состоит из шести вершин и четырех рёбер.