47
правок
Коды Прюфера: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KVN (обсуждение | вклад) Нет описания правки |
ALEXM (обсуждение | вклад) Нет описания правки |
||
| Строка 2: | Строка 2: | ||
'''функ''' КОД_ПРЮФЕРА(''T'': '''дерево''') = | '''функ''' КОД_ПРЮФЕРА(''T'': '''дерево''') = | ||
1. Пусть n - число вершин в ''T'', а A - целочисленный вектор длины ''n''-2; | 1. Пусть n - число вершин в ''T'', | ||
а A - целочисленный вектор длины ''n''-2; | |||
2. B:= [1 : n]; | 2. B:= [1 : n]; | ||
3. '''для''' ''i'' '''от''' ''1'' '''до''' ''n-2'' '''цикл''' | 3. '''для''' ''i'' '''от''' ''1'' '''до''' ''n-2'' '''цикл''' | ||
| Строка 23: | Строка 24: | ||
'''функ''' РАСПАКОВКА (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. B: = [1 : n]; | 2. B: = [1 : n]; | ||
3. '''для''' i '''от''' 1 '''до''' n+1 '''цикл''' | 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} | ||
'''всё;''' | '''всё;''' | ||