Коды Прюфера

Коды Прюфера.

Кодирование Прюфера переводит помеченные деревья порядка [math]n[/math] в последовательность чисел от [math]1[/math] до [math]n[/math] по алгоритму:

 Пока количество вершин [math]\gt 1[/math] {
   1. Выбирается лист с минимальным номером.
   2. В последовательность Прюфера добавляется номер смежной вершины.
   3. Лист и инцидентное ребро удаляются из дерева.
 }

Полученная последовательность и есть код Прюфера.

Лемма:

Номера всех вершин, которые не являются листьями или имеют номер [math]n[/math], встречаются в коде Прюфера. А номера вершин - листьев, не имеющих номер [math]n[/math], не встречаются в коде Прюфера.

Доказательство:

[math]\triangleright[/math]

1. Вершина [math]n[/math] не удаляется, так как у неё максимальный номер (в графе с [math]\gt 1[/math] вершиной - [math]\geq 2[/math] листа), а, значит, на последнем шаге у неё была смежная вершина. [math]\Rightarrow[/math] [math]n[/math] - как минимум один раз встретилось в коде. 2. Если вершина - не лист, то у неё на каком-то шаге была смежная вершина - лист. А, значит, номер этой вершины был [math]\gt 1[/math] раза выписан в код. 3. Так как вершина - лист(с номером не равным [math]n[/math]), она была только удалена. А, значит, все вершины, не являющиеся листьями или имеющие номер [math]n[/math], "входят" в код Прюфера, а остальные - нет.

[math]\triangleleft[/math]

Лемма:

По любой последовательности длиной [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] - вершина, которую мы удалили первой (По предыдущей лемме v - лист, а по построению кода мы удаляем лист с минимальным номером). Соединяем [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]

Следствием из этой теоремы является формула Кэли.