Коды Прюфера: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
Строка 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+1 '''цикл'''
     3.    '''для''' i '''от''' 1 '''до''' n-2 '''цикл'''
     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> добавить ребро,
     5.        В <math>T</math> добавить ребро, соединяющее вершины
               соединяющее вершины с номерами <math>b</math> и <math>A[i]</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>.

Навигация