Аноним

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

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 4: Строка 4:
     1.    Пусть n - число вершин в ''T'',  
     1.    Пусть n - число вершин в ''T'',  
           а A - целочисленный вектор длины ''n''-2;
           а A - целочисленный вектор длины ''n''-2;
     2.    B:= [1 : n];
     2.    B := [1 : n];
     3.    '''для''' ''i'' '''от''' ''1'' '''до''' ''n-2'' '''цикл'''
     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
           '''всё''';
           '''всё''';
Строка 24: Строка 24:


     '''функ''' РАСПАКОВКА (A: '''код''')=
     '''функ''' РАСПАКОВКА (A: '''код''')=
     1.    Пусть ''T'' состоит из вершин <math>\{\nu_1, \nu_2, ... , \nu_n\}</math> таких,
     1.    Пусть ''T'' состоит из вершин ''{ν₁, ν₂, ... , νₙ}'' таких,
           что номер вершины <math>\nu_i</math> равен <math>i</math>,где n - длина кода A плюс 2;
           что номер вершины ''νᵢ'' равен ''i'',где ''n'' - длина кода ''A'' плюс 2;
     2.    B: = [1 : n];
     2.    '' B := [1 : n];''
     3.    '''для''' i '''от''' 1 '''до''' n-2 '''цикл'''
     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 A[j]'' для любого ''j i''};
     5.        В <math>T</math> добавить ребро, соединяющее вершины  
     5.        В ''T'' добавить ребро, соединяющее вершины  
               с номерами <math>b</math> и <math>A[i]</math>;
               с номерами ''b'' и ''A[i]'';
     6.        B:=B-{b}
     6.        ''B'' := ''B-{b}''
           '''всё;'''
           '''всё;'''
     7.    В <math>T</math> добавить ребро, соединяющее вершины  
     7.    В ''T'' добавить ребро, соединяющее вершины  
           с номерами, оставшимися в В;
           с номерами, оставшимися в ''В'';
     8.    '''возврат''' ''T''
     8.    '''возврат''' ''T''
     '''всё'''
     '''всё'''
Строка 48: Строка 48:
Рассмотрим следующие операции над деревьями:
Рассмотрим следующие операции над деревьями:


<math>\overset{a}{\underset{b}{\downarrow}}</math> - операция замены номера a вершины T на номер b;
<math>\overset{a}{\underset{b}{\downarrow}}</math> - операция замены номера a вершины ''T'' на номер b;


<math>a \overset{0}{\rightarrow} b</math> - операция склеивания двух деревьев по вершинам a и b, т.е. дерево <math>T_1 a  \overset{0}{\rightarrow}  b T_2</math> получается из <math>T_2</math> и <math>T_1</math> отождествлением вершин a из <math>T_1</math> b из <math>T_2</math> и присвоением склеенной вершине номера b (при склеивании ордеревьев добавляется требование, чтобы вершина b была корневой).
<math>a \overset{0}{\rightarrow} b</math> - операция склеивания двух деревьев по вершинам a и b, т.е. дерево <math>T_1 a  \overset{0}{\rightarrow}  b T_2</math> получается из <math>T_2</math> и <math>T_1</math> отождествлением вершин a из <math>T_1</math> b из <math>T_2</math> и присвоением склеенной вершине номера b (при склеивании ордеревьев добавляется требование, чтобы вершина b была корневой).
Строка 55: Строка 55:


Рассмотрим некоторые вставки кода Прюфера:
Рассмотрим некоторые вставки кода Прюфера:
[] - операция формального отбрасывания квадратных скобок; определена на всех выражениях вида <math>[a_1, a_2, ..., a_n],b,[b_1, b_2, ..., b_m]</math> и состоит в отбрасывании всех внутренних квадратных скобок и добавлении двух внешних;
[ ] - операция формального отбрасывания квадратных скобок; определена на всех выражениях вида <math>[a_1, a_2, ..., a_n],b,[b_1, b_2, ..., b_m]</math> и состоит в отбрасывании всех внутренних квадратных скобок и добавлении двух внешних;


<math>\stackrel{*}{c}</math> -операция вставки кода Прюфера; если  
<math>\stackrel{*}{c}</math> -операция вставки кода Прюфера; если  
47

правок