Архив форума

Всем привет, я здесь первый раз и обращаюсь за помощью. К сожалению в интернете очень мало материала по восстановлению деревьев по коду Прюфера, поэтому спрашиваю у вас. Заранее спасибо.

Код Прюфера.
Пусть G –дерево на n вершинах.
1. Находим висячую вершину с наименьшим номером, пишем номер, смежной ей вершины и удаляем соответствующее ребро из графа.
2. Проделываем шаг 1 n-1 раз.
В результате получается набор из n-1 числа, каждое из которых не превосходит n, а последним является число n.
Справедлива теорема:
Каждый набор из n-1 числа, каждое из которых не превосходит n, а последним является n, однозначно определяет дерево на n вершинах.
Отсюда получается алгоритм восстановления дерева по коду Прюфера.
Вход: набор из n-1 числа с условием (см. выше).
1. Пусть первым записано число x. Выбираем минимальное натуральное число y, не превосходящее n, и отсутствующее в коде. В граф добавляем ребро xy. Число x удаляем из кода.
2. Повторяем шаг 1 n-1 раз.

нужно ещё добавить, что выбираемое число y нужно запоминать
и на следующем шаге выбирать его из тех чисел, что еще не выбирались в качестве y

Либо я совсем ничего не понимаю в этом алгоритме, либо он не работает с кодом, составленным по этому списку ребер:
1 2
1 3
3 5
5 6
5 4
5 8
2 7
2 9

он вершину 2 соединяет с 5 :?:

Гость
Вашему дереву соответствует код Прюфера [55253129].
Из него отлично восстанавливается Ваше дерево.

Попробовал воспроизвести Вашу ошибку: вероятно при восстановлении Вы слишком буквально выполняете пункт "Число x удаляем из кода."

Нужно удалить только одну цифру - x, с которой мы работали на текущем шаге. Т.е. на первом шаге от кода останется [5253129] - нет первой пятерки.

Надеюсь, мое объяснение чем-то поможет :wink: