Коды Прюфера

Материал из Викиконспекты
Перейти к: навигация, поиск

Содержание

[править] Алгоритм построения кодов Прюфера

Кодирование Прюфера переводит помеченные деревья порядка n в последовательность чисел от 1 до n по алгоритму:
Пока количество вершин больше двух:

  1. Выбирается лист v с минимальным номером.
  2. В код Прюфера добавляется номер вершины, смежной с v.
  3. Вершина v и инцидентное ей ребро удаляются из дерева.


Полученная последовательность называется кодом Прюфера (англ. Codes Priifer) для заданного дерева.

Лемма:
Номер вершины v встречается в коде Прюфера тогда и только тогда, когда v не является листом, причём встречается этот номер к коде дерева в точности \deg v - 1 раз.
Доказательство:
\triangleright
  1. Вершина с номером n не может быть удалена, следовательно на последнем шаге у неё была смежная вершина, и число n встретилось в коде.
  2. Если вершина не является листом, то у неё на некотором шаге была смежная вершина - лист, следовательно номер этой вершины встречается в коде.
  3. Если вершина является листом с номером меньше n, то она была удалена до того, как был удален её сосед, следовательно её номер не встречается в коде.
Таким образом, номера всех вершин, не являющихся листьями или имеющих номер n, встречаются в коде Прюфера, а остальные - нет.
\triangleleft
Лемма:
По любой последовательности длины n - 2 из чисел от 1 до n можно построить помеченное дерево, для которого эта последовательность является кодом Прюфера.
Доказательство:
\triangleright

Доказательство проведем по индукции по числу n
База индукции:

n = 1 - верно.

Индукционный переход:

Пусть для числа n верно, построим доказательство для n+1:

Пусть у нас есть последовательность: A = [a_1, a_2, ..., a_{n - 2}].

Выберем минимальное число v не лежащее в A. По предыдущей лемме v - вершина, которую мы удалили первой. Соединим v и a_1 ребром. Выкинем из последовательности A число a_1. Перенумеруем вершины, для всех a_i > v заменим a_i на a_i - 1. А теперь мы можем применить предположение индукции.
\triangleleft
Теорема:
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка n и последовательностями длиной n - 2 из чисел от 1 до n
Доказательство:
\triangleright
  1. Каждому помеченному дереву приведенный алгоритм сопоставляет последовательность.
  2. Каждой последовательности, как следует из предыдущей леммы, соотвествует помеченное дерево.
\triangleleft

Следствием из этой теоремы является формула Кэли.

[править] Пример построения кода Прюфера

Prufer.png

[править] Пример декодирования кода Прюфера

Backprufer.png

[править] См. также


[править] Источники информации

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты