47
правок
Коды Прюфера: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
ALEXM (обсуждение | вклад) Нет описания правки |
ALEXM (обсуждение | вклад) Нет описания правки |
||
| Строка 6: | Строка 6: | ||
Пусть T - дерево с множеством вершин <math>\{\nu_1, \nu_2,..., \nu_n\}</math>. Будем считать, что номер вершины <math>\nu_i</math> равен <math>i</math>. Сопоставим дереву T последовательность <math>[a_1, a_2, ... , a_{n-2}]</math> называемую кодом Прюфера, по следующему правилу: | Пусть T - дерево с множеством вершин <math>\{\nu_1, \nu_2,..., \nu_n\}</math>. Будем считать, что номер вершины <math>\nu_i</math> равен <math>i</math>. Сопоставим дереву T последовательность <math>[a_1, a_2, ... , a_{n-2}]</math> называемую кодом Прюфера, по следующему правилу: | ||
'''функ''' КОД_ПРЮФЕРА(''' T дерево''') = | '''функ''' КОД_ПРЮФЕРА(''' T дерево''') = | ||
1.Пусть n - число вершин в ''T'', а ''A'' - Целочисленный вектор длины ''n''-2; | |||
1.Пусть n - число вершин в ''T'', а ''A'' - Целочисленный вектор длины ''n''-2; | 2. <math>B:= [1 \; n]</math>; | ||
3. для ''i'' от ''1'' до ''n-1'' цикл | |||
2. <math>B:= [1 \; n]</math>; | 4. <math>b:=min\{k \in B; k</math> - номер висячей вершины<math>\}</math>; | ||
5. A[i]:= номер вершины, смежной вершине с номером <math>b</math>; | |||
3. для ''i'' от ''1'' до ''n-1'' цикл | 6. B:= B-{b}; | ||
7. Удалить из ''T'' вершину с номером <math>A[i]</math> | |||
4. <math>b:=min\{k \in B; k</math> - номер висячей вершины<math>\}</math>; | всё | ||
8 возврат A | |||
5. A[i]:= номер вершины, смежной вершине с номером <math>b</math>; | всё | ||
6. B:= B-{b}; | |||
7. Удалить из ''T'' вершину с номером <math>A[i]</math> | |||
8 возврат A | |||
всё | |||
Рассмотрим седующий пример. Для дерева ''T'' (рис.) код Прюфера имеет вид: | Рассмотрим седующий пример. Для дерева ''T'' (рис.) код Прюфера имеет вид: | ||
| Строка 36: | Строка 26: | ||
Распаковка кода Прюфера осуществляется следующим образом: | Распаковка кода Прюфера осуществляется следующим образом: | ||
'''функ''' РАСПАКОВКА (A: ''код'')= | '''функ''' РАСПАКОВКА (A: ''код'')= | ||
всё | 1. Пусть ''T'' состоит из вершин <math>\{\nu_1, \nu_2, ... , \nu_n)\}</math> таких, что номер вершины <math>\nu_i</math> равен <math>i</math>, где n - длина кода A плюс 2; | ||
2. <math>B: = [1 \; n]</math>; | |||
3. для <math>i</math> от <math>n+1</math> цикл | |||
4. b:=<math>min\{k \in B \; k \neq A[j]</math> для любого <math>j \geq i\}</math>; | |||
5. В <math>T</math> добавить ребро, соединяющее вершины с номерами <math>b</math> и <math>A[i]</math>; | |||
6. <math>B:=B-\{b\}</math> | |||
всё; | |||
7. возврат T | |||
всё | |||
В случае корневого ордерева процедуры построения кода Прюфера и его распаковки аналогичны. Необходимо только на последнем месте в <math>A</math> указывать корневую вершину и при распаковке кода <math>A</math> исключать номер этой вершины из множества <math>B</math>. | В случае корневого ордерева процедуры построения кода Прюфера и его распаковки аналогичны. Необходимо только на последнем месте в <math>A</math> указывать корневую вершину и при распаковке кода <math>A</math> исключать номер этой вершины из множества <math>B</math>. | ||