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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Коды Прюфера.)
(Коды Прюфера.)
Строка 1: Строка 1:
 
== Коды Прюфера. ==
 
== Коды Прюфера. ==
Кодирование Прюфера переводит помеченные деревья порядка n в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:
+
Кодирование Прюфера переводит помеченные деревья порядка <tex>n</tex> в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:
 
   Пока количество вершин <tex>>1</tex> {
 
   Пока количество вершин <tex>>1</tex> {
 
     1. Выбирается лист с минимальным номером.
 
     1. Выбирается лист с минимальным номером.
Строка 7: Строка 7:
 
   }
 
   }
 
Полученная последовательность и есть '''код Прюфера'''.
 
Полученная последовательность и есть '''код Прюфера'''.
 +
 +
{{Лемма
 +
|statement=
 +
Номера всех вершин, которые не являются листьями или с номером <tex>n</tex>, встречаются в коде Прюфера. А те, которые не входят - являются листьями.
 +
|proof=
 +
  1. Вершина <tex>n</tex> не удаляется, так как у неё максимальный номер (в графе с <tex>>1</tex> вершиной - <tex>\leq 2<tex> листа), а, значит, на последнем шаге у неё была смежная вершина. <tex>Rightarrow</tex> n - как минимум один раз встретилось в коде.
 +
  2. Если вершина, не лист, то у неё на каком-то шаге была смежная вершина - лист. А, значит, номер этой вершины был <tex>>1</tex> выписан в код.
 +
  3. Так как вершина - лист(с номером не равным <tex>n</tex>), она была только удалена.
 +
 +
  А, значит, все вершины, не являющиеся листьями "входят" в код Прюфера.
 +
}}
  
 
{{Лемма
 
{{Лемма
Строка 18: Строка 29:
 
<br>
 
<br>
 
Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex>
 
Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex>
Выберем минимальное число <tex>v</tex> не лежащее в A. Это означает, что <tex>v</tex> - вершина, которую мы удалили первой, а, значит, это лист. Соединяем <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> - <tex>a_1</tex>. Далее будем перенумеровывать вершины, то есть - <tex>\forall i : a_i > v</tex> выполняем <tex>a_i = a_i - 1</tex>. А теперь мы можем применить предположение индукции.
+
Выберем минимальное число <tex>v</tex> не лежащее в A. Это означает, что <tex>v</tex> - вершина, которую мы удалили первой(). А, значит, это лист. Соединяем <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> - <tex>a_1</tex>. Далее будем перенумеровывать вершины, то есть - <tex>\forall i : a_i > v</tex> выполняем <tex>a_i = a_i - 1</tex>. А теперь мы можем применить предположение индукции.
 
}}
 
}}
  

Версия 02:26, 9 октября 2010

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

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

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

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

Лемма:
Номера всех вершин, которые не являются листьями или с номером [math]n[/math], встречаются в коде Прюфера. А те, которые не входят - являются листьями.
Доказательство:
[math]\triangleright[/math]

1. Вершина [math]n[/math] не удаляется, так как у неё максимальный номер (в графе с [math]\gt 1[/math] вершиной - [math]\leq 2\lt tex\gt листа), а, значит, на последнем шаге у неё была смежная вершина. \lt tex\gt Rightarrow[/math] n - как минимум один раз встретилось в коде.

 2. Если вершина, не лист, то у неё на каком-то шаге была смежная вершина - лист. А, значит, номер этой вершины был [math]\gt 1[/math] выписан в код.
 3. Так как вершина - лист(с номером не равным [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 \rightarrow n + 1[/math].
Пусть у нас есть последовательность: [math]A = [a_1, a_2, ..., a_{n - 2}].[/math]

Выберем минимальное число [math]v[/math] не лежащее в A. Это означает, что [math]v[/math] - вершина, которую мы удалили первой(). А, значит, это лист. Соединяем [math]v[/math] и [math]a_1[/math] ребром. Выкинем из последовательности [math]A[/math] - [math]a_1[/math]. Далее будем перенумеровывать вершины, то есть - [math]\forall i : a_i \gt v[/math] выполняем [math]a_i = 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]

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