Просмотр исходного текста страницы Коды Прюфера

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

{{Лемма
|statement=
Номер вершины <tex>v</tex> встречается в коде Прюфера тогда и только тогда, когда <tex>v</tex> не является листом или <tex>v</tex> имеет номер <tex>n</tex>.
|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=
Доказательство проведем по индукции. <br>
База. <tex>n = 1</tex> <tex>-</tex> верно.
<br>
Переход от <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>. А теперь мы можем применить предположение индукции.
}}

{{Теорема
|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 | Представление с помощью списка ребер и кода Прюфера]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]