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