End for

 

Обоснование

Код Прюфера действительно является представлением свободного дерева. Чтобы убедиться в этом, покажем, что если Т' — дерево, построенное алгоритмом 9.2 по коду А, который построен алгоритмом 9.1 по дереву Т, то Т' изоморфно Т, Т' ~ Т.

Для этого установим отображение f: 1..р → 1..р между номерами вершин в деревьях Т, и Т' по порядку выбора вершин в алгоритмах: если вершина v выбрана на i-ом шаге алгоритма 9.1, то вершина f(v) выбрана на i-ом шаге алгоритма 9.2. Заметим, что Dom f = 1..р, поскольку висячие вершины есть в любом дереве и удаление висячей вершины оставляет дерево деревом. Далее, Iт f = 1..р, поскольку на i-ом шаге алгоритма 9.2 использовано i - 1 число из р чисел и остаётся р – i + 1 чисел, а в хвосте кода Прюфера занято не более р – i чисел. Более того, v f(v) = v. Действительно, номера вершин, которые являются висячими в исходном дереве, не появляются в коде Прюфера (кроме, может быть, одной висячей вершины с наибольшим номером), а номера вершин, которые не являются висячими, обязательно появляются. Поскольку при выборе первой вершины v в алгоритме 9.1 все вершины с меньшими номерами не являются висячими, их номера будет присутствовать в коде и, значит, не могут быть использованы на первом шаге алгоритма 9.2. Таким образом, на первом шаге алгоритм 9.2 выберет ту же вершину v. Но после удаления вершины v на втором шаге снова имеется дерево, к которому применимы те же рассуждения.

Итак, f - тождественное и, значит, взаимно-однозначное отображение. Заметим теперь, что для определения i-ого элемента кода на i-ом шаге алгоритма 9.1 используется, а затем удалется ребро (v, А[i]) и в точности то же ребро добавляется в дерево Т' на i-ом шаге алгоритма 9.2. Следовательно, f - взаимно-однозначное отображение, сохраняющее смежность и Т ~ Т'.