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