Изменения

Пока количество вершин <tex>>1</tex> больше одной { 1. Выбирается лист v с минимальным номером. 2. В последовательность код Прюфера добавляется номер вершины, смежной вершины.с v 3. Лист Вершина v и инцидентное ей ребро удаляются из дерева.

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

Номера всех вершин, которые не являются листьями или имеют номер <tex>n</tex>, встречаются Номер вершины v встречается в коде Прюфера. А номера вершин - листьевтогда и только тогда, когда v не имеющих является листом или v имеет номер <tex>n</tex>, не встречаются в коде Прюфера.

1. # Вершина с номером <tex>n</tex> не удаляетсяможет быть удалена, так как следовательно на последнем шаге у неё максимальный номер (в графе с была смежная вершина, и число <tex>>1n</tex> вершиной - <tex>\geq 2</tex> листа), а, значитвстретилось в коде.# Если вершина не является листом, то у неё на последнем некотором шаге у неё была смежная вершина- лист, следовательно номер этой вершины встречается в коде. <tex>\Rightarrow</tex> # Если вершина является листом с номером меньше <tex>n</tex> - , то она была удалена до того, как минимум один раз встретилось был удален ее сосед, следовательно ее номер не встречается в коде.

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

По любой последовательности длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> можно построить помеченное дерево,для которого эта последовательность является кодом Прюфера.

Доказательство проведем по индукции.

Переход от <tex>n \rightarrow </tex> к <tex>n + 1</tex>.

Выберем минимальное число <tex>v</tex> не лежащее в A. Это означает, что По предыдущей лемме <tex>v</tex> - вершина, которую мы удалили первой (По предыдущей лемме v - лист, а по построению кода мы удаляем лист с минимальным номером). Соединяем Соединим <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> - число <tex>a_1</tex>. Далее будем перенумеровывать Перенумеруем вершины, то есть - для всех <tex>\forall i : a_i > v</tex> выполняем заменим <tex>a_i = </tex> на <tex>a_i - 1</tex>. А теперь мы можем применить предположение индукции.

1. # Каждому помеченному дереву соотвествует приведенный алгоритм сопоставляет последовательность и только одна. Это верно по построению кода.2. # Каждой последовательности , как следует из предыдущей леммы, соотвествует помеченное дерево и только одно. Это верно по предыдущей лемме, т.к. восстанавливали мы однозначно.<br>Значит, это биекция - по определению.