1632
правки
Изменения
м
Номера всех вершин, которые не являются листьями или имеют номер Номер вершины <tex>nv</tex>, встречаются встречается в коде Прюфера. А номера вершин - листьевтогда и только тогда, не имеющих номер когда <tex>nv</tex>не является листом, не встречаются причём встречается этот номер к коде дерева в коде Прюфераточности <math>\deg v - 1</math> раз.
1. # Вершина с номером <tex>n</tex> не удаляется, так как у неё максимальный номер (в графе с <tex>>1</tex> вершиной - <tex>\geq 2</tex> листа), а, значитможет быть удалена, следовательно на последнем шаге у неё была смежная вершина. <tex>\Rightarrow</tex> , и число <tex>n</tex> - как минимум один раз встретилось в коде.2. # Если вершина - не листявляется листом, то у неё на каком-то некотором шаге была смежная вершина - лист. А, значит, номер этой вершины был <tex>>1-</tex> выписан лист, следовательно номер этой вершины встречается в кодкоде.3. Так как # Если вершина - лист(является листом с номером не равным меньше <tex>n</tex>), то она была только удаленадо того, как был удален её сосед, следовательно её номер не встречается в коде.
АТаким образом, значит, все вершиныномера всех вершин, не являющиеся являющихся листьями или имеющие имеющих номер <tex>n</tex>, "входят" встречаются в код коде Прюфера, а остальные <tex>- </tex> нет.
1. # Каждому помеченному дереву соотвествует приведенный алгоритм сопоставляет последовательность и только одна. Это верно по построению кода.2. # Каждой последовательности , как следует из предыдущей леммы, соотвествует помеченное дерево и только одно. Это верно по предыдущей лемме, т.к. восстанавливали мы однозначно.<br>Значит, это биекция - по определению.
rollbackEdits.php mass rollback
== Коды Алгоритм построения кодов Прюфера. ==Кодирование Прюфера переводит [[Количество помеченных деревьев#Помеченное дерево|помеченные деревья порядка <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)'' для заданного дерева.
{{Лемма
|statement=
|proof=
}}
{{Лемма
|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>A = [a_1, a_2, ..., a_{n - 2}].</tex>
Выберем минимальное число <tex>v</tex> не лежащее в <tex>A</tex>. Это означает, что По предыдущей лемме <tex>v</tex> <tex> - </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>. А теперь мы можем применить предположение индукции.
}}
{{Теорема
|statement=
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex>
|proof=
}}
Следствием из этой теоремы является [[Количество помеченных деревьев|формула Кэли]].
== Пример построения кода Прюфера ==
[[Файл: 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</tex>''' V: P.count(x) == 0)
G.push({u, v})
P.erase(0)
V.erase(indexOf(v))
G.push({v[0], v[1]})
'''return''' G
== Пример декодирования кода Прюфера ==
[[Файл: backprufer.png|700px]]
==См. также==
*[[Связь матрицы Кирхгофа и матрицы инцидентности]]
*[[Матрица Кирхгофа]]
*[[Количество помеченных деревьев]]
*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
== Источники информации ==
* [http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
[[Категория: Свойства остовных деревьев ]]
