Изменения
Нет описания правки
== Коды Прюфера. ==
Кодирование Прюфера переводит помеченные деревья порядка n в последовательность чисел от 1 до n по алгоритму:
Пока количество вершин <mathtex>>1</mathtex>{
1. Выбирается лист с минимальным номером.
2. В последовательность Прюфера добавляется номер смежной вершины.
{{Лемма
|statement=
По любой последовательности длиной <mathtex>n - 2</mathtex> из чисел от <mathtex>1</mathtex> до <mathtex>n</mathtex> можно построить помеченное дерево.
|proof=
Доказательство по индукции.
База. <mathtex>n = 1</mathtex> - верно.
<br>
Переход <mathtex>n \rightarrow n + 1</mathtex>.
<br>
Пусть у нас есть последовательность: <mathtex>A = [a_1, a_2, ..., a_{n - 2}].</mathtex>Выберем минимальное число <mathtex>v</mathtex> не лежащее в A. Это означает, что <mathtex>v</mathtex> - вершина, которую мы удалили первой, а, значит, это лист. Соединяем <mathtex>v</mathtex> и <mathtex>a_1</mathtex> ребром. Т.к. <mathtex>v</mathtex> - лист - он нам больше не помешает. Выкинем из последовательности <mathtex>A</mathtex> - <mathtex>a_1</mathtex> и применим предположение индукции.
}}
{{Теорема
|statement=
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <mathtex>n - 2</mathtex> из чисел от <mathtex>1</mathtex> до <mathtex>n</mathtex>
|proof=
1. Каждому помеченному дереву соотвествует последовательность и только одна - Верно по построению кода.
2. Каждой последовательности соотвествует помеченное дерево и только одно - Верно по предыдущей лемме, т.к. восстанавливали мы однозначно.
}}
Следствием из этой теоремы является [[Количество помеченных деревьев|теорема Кэли]].
''Следствие (Формула Кэли):''
Количество различных помеченных деревьев порядка <mathtex>n = n^{n - 2}</mathtex>.
