Изменения

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

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

Доказательство проведем по индукции.по числу <tex>n</tex><br><u>''База. индукции:''</u> <mathtex>n = 1</mathtex> <tex> - </tex> верно. <u>''Индукционный переход:''<br/u>Переход Пусть для числа <mathtex>n \rightarrow </tex> верно, построим доказательство для <tex>n + 1</mathtex>.:<br>Пусть у нас есть последовательность: <mathtex>A = [a_1, a_2, ..., a_{n - 2}].</mathtex>Выберем минимальное число <mathtex>v</mathtex> не лежащее в <tex>A</tex>. Это означает, что По предыдущей лемме <mathtex>v</mathtex> <tex> - </tex> вершина, которую мы удалили первой, а, значит, это лист. Соединяем Соединим <mathtex>v</mathtex> и <mathtex>a_1</mathtex> ребром. Т.кВыкинем из последовательности <tex>A</tex> число <tex>a_1</tex>. Перенумеруем вершины, для всех <mathtex>a_i >v</mathtex> - лист - он нам больше не помешает. Выкинем из последовательности заменим <mathtex>Aa_i</mathtex> - на <mathtex>a_1a_i - 1</mathtex> и применим . А теперь мы можем применить предположение индукции.

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

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

Следствием из этой теоремы является [[Количество помеченных деревьев|формула Кэли]]. == Пример построения кода Прюфера ==[[Файл: Prufer.png|500px]] == Алгоритм декодирования кодa Прюфера == В массиве вершин исходного дерева <tex>V</tex> найдём вершину <tex>v_{min}</tex> с минимальным номером, не содержащуюся в массиве с кодом Прюфера <tex>P</tex>, т.е. такую, что она является листом или концом уже добавленного в граф ребра, т.е. она стала листом в процессе построения кода Прюфера (по первому пункту построения). Вершина <tex>p_1</tex> была добавлена в код Прюфера как инцидентная листу с минимальным номером (по второму пункту построения), поэтому в исходном дереве существует ребро {<tex>p_1</tex>, <tex>v_{min}</tex>}, добавим его в список ребер. Удалим первый элемент из массива <tex>Р</tex>, а вершину <tex>v_{min}</tex> - из массива <tex>V</tex> т.к. она больше не может являться листом (по третьему пункту построения). Будем выполнять вышеуказанные действия, пока массив <tex>P</tex> не станет пустым. В конце работы алгоритма в массиве <tex>V</tex> останутся две вершины, составляющие последнее ребро дерева (это следует из построения). === Реализация === # P - код Прюфера # V - вершины '''function'''Следствие buildTree(Формула КэлиP, V): '''while'' '''not'' P.empty(): u = P[0]Количество различных помеченных деревьев порядка v = min(x '''<tex>\in<math/tex>n - n^''' V: P.count(x) == 0) G.push({u, v}) P.erase(0) V.erase(indexOf(v)) G.push({n - 2v[0], v[1]}<) '''return''' G  == Пример декодирования кода Прюфера ==[[Файл: backprufer.png|700px]] ==См. также==*[[Связь матрицы Кирхгофа и матрицы инцидентности]]*[[Матрица Кирхгофа]]*[[Количество помеченных деревьев]]*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]  == Источники информации ==* [http://www.intuit.ru/department/algorithms/graphsuse/11/math>2.html Университет INTUIT | Представление с помощью списка ребер и кода Прюфера] [[Категория: Алгоритмы и структуры данных]][[Категория: Остовные деревья ]][[Категория: Свойства остовных деревьев ]]