Изменения
→Коды Прюфера.
== Коды Прюфера. ==
Кодирование Прюфера переводит помеченные деревья порядка <tex>n </tex> в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:
Пока количество вершин <tex>>1</tex> {
1. Выбирается лист с минимальным номером.
}
Полученная последовательность и есть '''код Прюфера'''.
{{Лемма
|statement=
Номера всех вершин, которые не являются листьями или с номером <tex>n</tex>, встречаются в коде Прюфера. А те, которые не входят - являются листьями.
|proof=
1. Вершина <tex>n</tex> не удаляется, так как у неё максимальный номер (в графе с <tex>>1</tex> вершиной - <tex>\leq 2<tex> листа), а, значит, на последнем шаге у неё была смежная вершина. <tex>Rightarrow</tex> n - как минимум один раз встретилось в коде.
2. Если вершина, не лист, то у неё на каком-то шаге была смежная вершина - лист. А, значит, номер этой вершины был <tex>>1</tex> выписан в код.
3. Так как вершина - лист(с номером не равным <tex>n</tex>), она была только удалена.
А, значит, все вершины, не являющиеся листьями "входят" в код Прюфера.
}}
{{Лемма
<br>
Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex>
Выберем минимальное число <tex>v</tex> не лежащее в A. Это означает, что <tex>v</tex> - вершина, которую мы удалили первой, а(). А, значит, это лист. Соединяем <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> - <tex>a_1</tex>. Далее будем перенумеровывать вершины, то есть - <tex>\forall i : a_i > v</tex> выполняем <tex>a_i = a_i - 1</tex>. А теперь мы можем применить предположение индукции.
}}
