Коды Прюфера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 7: Строка 7:
 
   }
 
   }
 
Полученная последовательность называется '''кодом Прюфера''' для заданного дерева.
 
Полученная последовательность называется '''кодом Прюфера''' для заданного дерева.
 
Пример построения кода Прюфера
 
[[Файл: Prufer.png]]
 
  
 
{{Лемма
 
{{Лемма
Строка 45: Строка 42:
  
 
Следствием из этой теоремы является [[Количество помеченных деревьев|формула Кэли]].
 
Следствием из этой теоремы является [[Количество помеченных деревьев|формула Кэли]].
 +
 +
== Пример построения кода Прюфера ==
 +
[[Файл: Prufer.png|200px]]
  
 
== Источники ==
 
== Источники ==
 
[http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Интернет Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]
 
[http://www.intuit.ru/department/algorithms/graphsuse/11/2.html Интернет Университет INTUIT | Представление с помощью списка ребер и кода Прюфера]

Версия 15:15, 29 ноября 2011

Коды Прюфера.

Кодирование Прюфера переводит помеченные деревья порядка [math]n[/math] в последовательность чисел от [math]1[/math] до [math]n[/math] по алгоритму:

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

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

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

Доказательство проведем по индукции. База. [math]n = 1[/math] - верно.
Переход от [math]n[/math] к [math]n + 1[/math].
Пусть у нас есть последовательность: [math]A = [a_1, a_2, ..., a_{n - 2}].[/math]

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

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

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

Prufer.png

Источники

Интернет Университет INTUIT | Представление с помощью списка ребер и кода Прюфера