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