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