Изменения
Новая страница: «== Коды Прюфера == Кодирование Прюфера переводит помеченные деревья порядка n в последовате…»
== Коды Прюфера ==
Кодирование Прюфера переводит помеченные деревья порядка n в последовательность чисел от 1 до n по алгоритму:
Пока количество вершин <math>>1</math>{
1. Выбирается лист с минимальным номером.
2. В последовательность Прюфера добавляется номер смежной вершины.
3. Лист и инцидентное ребро удаляются из дерева.
}
Полученная последовательность и есть '''код Прюфера'''.
{{Лемма
|statement=
По любой последовательности длиной <math>n - 2</math> из чисел от <math>1</math> до <math>n</math> можно построить помеченное дерево.
|proof=
Доказательство по индукции.
База. <math>n = 1</math> - верно.
<br>
Переход <math>n \rightarrow n + 1</math>.
<br>
Пусть у нас есть последовательность: <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> и применим предположение индукции.
}}
{{Теорема
|statement=
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <math>n - 2</math> из чисел от <math>1</math> до <math>n</math>
|proof=
1. Каждому помеченному дереву соотвествует последовательность и только одна - Верно по построению кода.
<br>
2. Каждой последовательности соотвествует помеченное дерево и только одно - Верно по предыдущей лемме, т.к. восстанавливали мы однозначно.
}}
''Следствие:''
Количество различных помеченных деревьев порядка <math>n - n^{n - 2}</math>.
Кодирование Прюфера переводит помеченные деревья порядка n в последовательность чисел от 1 до n по алгоритму:
Пока количество вершин <math>>1</math>{
1. Выбирается лист с минимальным номером.
2. В последовательность Прюфера добавляется номер смежной вершины.
3. Лист и инцидентное ребро удаляются из дерева.
}
Полученная последовательность и есть '''код Прюфера'''.
{{Лемма
|statement=
По любой последовательности длиной <math>n - 2</math> из чисел от <math>1</math> до <math>n</math> можно построить помеченное дерево.
|proof=
Доказательство по индукции.
База. <math>n = 1</math> - верно.
<br>
Переход <math>n \rightarrow n + 1</math>.
<br>
Пусть у нас есть последовательность: <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> и применим предположение индукции.
}}
{{Теорема
|statement=
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <math>n - 2</math> из чисел от <math>1</math> до <math>n</math>
|proof=
1. Каждому помеченному дереву соотвествует последовательность и только одна - Верно по построению кода.
<br>
2. Каждой последовательности соотвествует помеченное дерево и только одно - Верно по предыдущей лемме, т.к. восстанавливали мы однозначно.
}}
''Следствие:''
Количество различных помеченных деревьев порядка <math>n - n^{n - 2}</math>.
