Изменения

Перейти к: навигация, поиск

Коды Прюфера

1433 байта добавлено, 08:42, 17 октября 2019
Алгоритм построения кодов Прюфера
== Коды Алгоритм построения кодов Прюфера. ==Кодирование Прюфера переводит [[Количество помеченных деревьев#Помеченное дерево|помеченные деревья порядка <tex>n</tex> ]] в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:<br> Пока количество вершин больше одной {двух: 1. # Выбирается лист <tex>v</tex> с минимальным номером. 2. # В код Прюфера добавляется номер вершины, смежной с <tex>v</tex>. 3. # Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева. }<br>Полученная последовательность называется '''кодом Прюфера''' ''(англ. Prüfer code)'' для заданного дерева.
{{Лемма
|statement=
Номер вершины <tex>v</tex> встречается в коде Прюфера тогда и только тогда, когда <tex>v</tex> не является листом или , причём встречается этот номер к коде дерева в точности <texmath>\deg v- 1</tex> имеет номер <tex>n</texmath>раз.
|proof=
# Вершина с номером <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> верно. <bru>''Индукционный переход:''</u>Переход от Пусть для числа <tex>n</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> вершина, которую мы удалили первой. Соединим <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> число <tex>a_1</tex>. Перенумеруем вершины, для всех <tex>a_i > v</tex> заменим <tex>a_i</tex> на <tex>a_i - 1</tex>. А теперь мы можем применить предположение индукции.
}}
Следствием из этой теоремы является [[Количество помеченных деревьев|формула Кэли]].
 
== Пример построения кода Прюфера ==
[[Файл: Prufer.png|500px]]
 
== Пример декодирования кода Прюфера ==
[[Файл: backprufer.png|700px]]
 
==См. также==
*[[Связь матрицы Кирхгофа и матрицы инцидентности]]
*[[Матрица Кирхгофа]]
*[[Количество помеченных деревьев]]
*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
 
 
== Источники информации ==
* [http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
[[Категория: Свойства остовных деревьев ]]
Анонимный участник

Навигация