Изменения
→Коды Прюфера.
Кодирование Прюфера переводит помеченные деревья порядка <tex>n</tex> в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:
Пока количество вершин больше одной {
1. Выбирается лист <tex>v </tex> с минимальным номером. 2. В код Прюфера добавляется номер вершины, смежной с <tex>v</tex>. 3. Вершина <tex>v </tex> и инцидентное ей ребро удаляются из дерева.
}
Полученная последовательность называется '''кодом Прюфера''' для заданного дерева.
{{Лемма
|statement=
Номер вершины <tex>v </tex> встречается в коде Прюфера тогда и только тогда, когда <tex>v </tex> не является листом или <tex>v </tex> имеет номер <tex>n</tex>.
|proof=
# Вершина с номером <tex>n</tex> не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число <tex>n</tex> встретилось в коде.
{{Теорема
|statement=
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex>
|proof=
# Каждому помеченному дереву приведенный алгоритм сопоставляет последовательность.
