Изменения

== Коды Алгоритм построения кодов Прюфера. ==Кодирование Прюфера переводит [[Количество помеченных деревьев#Помеченное дерево|помеченные деревья порядка <tex>n </tex>]] в последовательность чисел от <tex>1 </tex> до <tex>n </tex> по алгоритму:<br> Пока количество вершин больше двух:# Выбирается лист <tex>>1v</tex> { 1. Выбирается лист с минимальным номером. 2. # В последовательность код Прюфера добавляется номер вершины, смежной вершиныс <tex>v</tex>. 3. Лист # Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева. }<br>Полученная последовательность и есть называется '''код кодом Прюфера'''''(англ. Prüfer code)'' для заданного дерева.

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

# Вершина с номером <tex>n</tex> не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число <tex>n</tex> встретилось в коде.# Если вершина не является листом, то у неё на некотором шаге была смежная вершина <tex>-</tex> лист, следовательно номер этой вершины встречается в коде.# Если вершина является листом с номером меньше <tex>n</tex>, то она была удалена до того, как был удален её сосед, следовательно её номер не встречается в коде. Таким образом, номера всех вершин, не являющихся листьями или имеющих номер <tex>n</tex>, встречаются в коде Прюфера, а остальные <tex>-</tex> нет.}} {{Лемма|statement=По любой последовательности длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> можно построить помеченное дерево,для которого эта последовательность является кодом Прюфера.|proof=Доказательство проведем по индукции.по числу <tex>n</tex><br><u>''База. индукции:''</u> <tex>n = 1</tex> <tex> - </tex> верно. <u>''Индукционный переход:''<br/u>Переход Пусть для числа <tex>n \rightarrow </tex> верно, построим доказательство для <tex>n + 1</tex>.:<br>

Выберем минимальное число <tex>v</tex> не лежащее в <tex>A</tex>. Это означает, что По предыдущей лемме <tex>v</tex> <tex> - </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 = </tex> на <tex>a_i - 1</tex>. А теперь мы можем применить предположение индукции.

Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex>

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

 Следствием из этой теоремы является [[Количество помеченных деревьевaдеревьев|формула Кэли]]. == Пример построения кода Прюфера ==[[Файл: Prufer.png|500px]] == Пример декодирования кода Прюфера ==[[Файл: backprufer.png|700px]] ==См. также==*[[Связь матрицы Кирхгофа и матрицы инцидентности]]*[[Матрица Кирхгофа]]*[[Количество помеченных деревьев]]*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]  == Источники информации ==* [http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Университет INTUIT | Представление с помощью списка ребер и кода Прюфера] [[Категория: Алгоритмы и структуры данных]][[Категория: Остовные деревья ]][[Категория: Свойства остовных деревьев ]]