Коды Прюфера.
Кодирование Прюфера переводит помеченные деревья порядка n в последовательность чисел от 1 до n по алгоритму:
Пока количество вершин [math]\gt 1[/math] {
1. Выбирается лист с минимальным номером.
2. В последовательность Прюфера добавляется номер смежной вершины.
3. Лист и инцидентное ребро удаляются из дерева.
}
Полученная последовательность и есть код Прюфера.
| Лемма: |
По любой последовательности длиной [math]n - 2[/math] из чисел от [math]1[/math] до [math]n[/math] можно построить помеченное дерево. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Доказательство по индукции.
База. [math]n = 1[/math] - верно.
Переход [math]n \rightarrow n + 1[/math].
Пусть у нас есть последовательность: [math]A = [a_1, a_2, ..., a_{n - 2}].[/math]
Выберем минимальное число [math]v[/math] не лежащее в A. Это означает, что [math]v[/math] - вершина, которую мы удалили первой, а, значит, это лист. Соединяем [math]v[/math] и [math]a_1[/math] ребром. Выкинем из последовательности [math]A[/math] - [math]a_1[/math]. Далее будем перенумеровывать вершины, то есть - [math]\forall i : a_i \gt v[/math] выполняем [math]a_i = a_i - 1[/math]. А теперь мы можем применить предположение индукции. |
| [math]\triangleleft[/math] |
| Теорема: |
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка [math]n[/math] и последовательностями длиной [math]n - 2[/math] из чисел от [math]1[/math] до [math]n[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
1. Каждому помеченному дереву соотвествует последовательность и только одна. Это верно по построению кода.
2. Каждой последовательности соотвествует помеченное дерево и только одно. Это верно по предыдущей лемме, т.к. восстанавливали мы однозначно.
Значит, это биекция - по определению. |
| [math]\triangleleft[/math] |
Следствием из этой теоремы является теорема Кэли.
