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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Коды Прюфера.)
Строка 1: Строка 1:
 
== Коды Прюфера. ==
 
== Коды Прюфера. ==
 
Кодирование Прюфера переводит помеченные деревья порядка n в последовательность чисел от 1 до n по алгоритму:
 
Кодирование Прюфера переводит помеченные деревья порядка n в последовательность чисел от 1 до n по алгоритму:
   Пока количество вершин <math>>1</math>{
+
   Пока количество вершин <tex>>1</tex> {
 
     1. Выбирается лист с минимальным номером.
 
     1. Выбирается лист с минимальным номером.
 
     2. В последовательность Прюфера добавляется номер смежной вершины.
 
     2. В последовательность Прюфера добавляется номер смежной вершины.
Строка 10: Строка 10:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
По любой последовательности длиной <math>n - 2</math> из чисел от <math>1</math> до <math>n</math> можно построить помеченное дерево.
+
По любой последовательности длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> можно построить помеченное дерево.
 
|proof=
 
|proof=
 
Доказательство по индукции.
 
Доказательство по индукции.
База. <math>n = 1</math> - верно.
+
База. <tex>n = 1</tex> - верно.
 
<br>
 
<br>
Переход <math>n \rightarrow n + 1</math>.
+
Переход <tex>n \rightarrow n + 1</tex>.
 
<br>
 
<br>
Пусть у нас есть последовательность: <math>A = [a_1, a_2, ..., a_{n - 2}].</math>
+
Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex>
Выберем минимальное число <math>v</math> не лежащее в A. Это означает, что <math>v</math> - вершина, которую мы удалили первой, а, значит, это лист. Соединяем <math>v</math> и <math>a_1</math> ребром. Т.к. <math>v</math> - лист - он нам больше не помешает. Выкинем из последовательности <math>A</math> - <math>a_1</math> и применим предположение индукции.
+
Выберем минимальное число <tex>v</tex> не лежащее в A. Это означает, что <tex>v</tex> - вершина, которую мы удалили первой, а, значит, это лист. Соединяем <tex>v</tex> и <tex>a_1</tex> ребром. Т.к. <tex>v</tex> - лист - он нам больше не помешает. Выкинем из последовательности <tex>A</tex> - <tex>a_1</tex> и применим предположение индукции.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <math>n - 2</math> из чисел от <math>1</math> до <math>n</math>  
+
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex>  
 
|proof=
 
|proof=
 
1. Каждому помеченному дереву соотвествует последовательность и только одна - Верно по построению кода.
 
1. Каждому помеченному дереву соотвествует последовательность и только одна - Верно по построению кода.
<br>
 
 
2. Каждой последовательности соотвествует помеченное дерево и только одно - Верно по предыдущей лемме, т.к. восстанавливали мы однозначно.     
 
2. Каждой последовательности соотвествует помеченное дерево и только одно - Верно по предыдущей лемме, т.к. восстанавливали мы однозначно.     
 
}}
 
}}
 
+
Следствием из этой теоремы является [[Количество помеченных деревьев|теорема Кэли]].
 
''Следствие (Формула Кэли):''
 
''Следствие (Формула Кэли):''
Количество различных помеченных деревьев порядка <math>n = n^{n - 2}</math>.
+
Количество различных помеченных деревьев порядка <tex>n = n^{n - 2}</tex>.

Версия 21:52, 8 октября 2010

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

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

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

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

Лемма:
По любой последовательности длиной [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]v[/math] - лист - он нам больше не помешает. Выкинем из последовательности [math]A[/math] - [math]a_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]

Следствием из этой теоремы является теорема Кэли. Следствие (Формула Кэли): Количество различных помеченных деревьев порядка [math]n = n^{n - 2}[/math].