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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показано 5 промежуточных версий 2 участников)
Строка 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
           '''всё'''
           '''всё''';
     8.     '''возврат''' A
     8.   '''возврат''' A
     '''всё'''
     '''всё'''


Строка 18: Строка 18:
<math>P_2(T) = [4, 4, 4, 5, 5, 7, 7].</math>
<math>P_2(T) = [4, 4, 4, 5, 5, 7, 7].</math>


[[Файл:prufer_encode.gif|256 px]]
[[Файл:Priifer.mp4|360 px]]




Строка 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''
     '''всё'''
     '''всё'''


[[Файл:prufer_decode.gif|256 px]]
[[Файл:Priifer decode.mp4|360 px]]


В случае корневого ордерева процедуры построения кода Прюфера и его распаковки аналогичны. Необходимо только на последнем месте в <math>A</math> указывать корневую вершину и при распаковке кода <math>A</math> исключать номер этой вершины из множества <math>B</math>.
В случае корневого ордерева процедуры построения кода Прюфера и его распаковки аналогичны. Необходимо только на последнем месте в <math>A</math> указывать корневую вершину и при распаковке кода <math>A</math> исключать номер этой вершины из множества <math>B</math>.
Строка 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> -операция вставки кода Прюфера; если  

Текущая версия от 18:55, 11 мая 2023

Пусть T - дерево с множеством вершин [math]\displaystyle{ \{\nu_1, \nu_2,..., \nu_n\} }[/math]. Будем считать, что номер вершины [math]\displaystyle{ \nu_i }[/math] равен [math]\displaystyle{ i }[/math]. Сопоставим дереву T последовательность [math]\displaystyle{ [a_1, a_2, ... , a_{n-2}] }[/math] называемую кодом Прюфера, по следующему правилу:

   функ КОД_ПРЮФЕРА(T: дерево) =
   1.    Пусть n - число вершин в T, 
         а A - целочисленный вектор длины n-2;
   2.    B := [1 : n];
   3.    для i от 1 до n-2 цикл
   4.        b:=min{k ∈ B; k - номер висячей вершины};
   5.        A[i]:= номер вершины, смежной вершине с номером b;
   6.        B := B-{b};
   7.        Удалить из T вершину с номером b
         всё;
   8.    возврат A
   всё

Рассмотрим седующий пример. Для дерева T (рис.) код Прюфера имеет вид:

[math]\displaystyle{ P_2(T) = [4, 4, 4, 5, 5, 7, 7]. }[/math]


Распаковка кода Прюфера (или восстановление дерева по коду Прюфера) осуществляется следующим образом:

   функ РАСПАКОВКА (A: код)=
   1.    Пусть T состоит из вершин {ν₁, ν₂, ... , νₙ} таких,
         что номер вершины νᵢ равен i,где n - длина кода A плюс 2;
   2.     B := [1 : n];
   3.    для i от 1 до n-2 цикл
   4.        b:=min{k ∈ B : k ≠ A[j] для любого j ≥ i};
   5.        В T добавить ребро, соединяющее вершины 
             с номерами b и A[i];
   6.        B := B-{b}
         всё;
   7.    В T добавить ребро, соединяющее вершины 
         с номерами, оставшимися в В;
   8.    возврат T
   всё

В случае корневого ордерева процедуры построения кода Прюфера и его распаковки аналогичны. Необходимо только на последнем месте в [math]\displaystyle{ A }[/math] указывать корневую вершину и при распаковке кода [math]\displaystyle{ A }[/math] исключать номер этой вершины из множества [math]\displaystyle{ B }[/math].

Операции над деревьями и кодами Прюфера

Будем считать, что вершины двух разных деревьев нумеруются различными числами, причём номера одного дерева всегда больше или меньше любого номера другого. Это требование часто выполняется в практических реализациях, т.к для вершин каждого дерева обычно отводят последовательные массивы номеров ячеек памяти. Если все номера дерева [math]\displaystyle{ T_1 }[/math] (или ориентированного дерева [math]\displaystyle{ \overrightarrow{T_1} }[/math]) меньше всех номерова дерева [math]\displaystyle{ T_2 }[/math] (или [math]\displaystyle{ \overrightarrow{T_2} }[/math]) то пишут [math]\displaystyle{ T_1 }[/math]<[math]\displaystyle{ T_2 }[/math] (или [math]\displaystyle{ \overrightarrow{T_1} }[/math]<[math]\displaystyle{ \overrightarrow{T_2} }[/math]).

Рассмотрим следующие операции над деревьями:

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

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

На рис 2.22 представлен результат выполнения операции [math]\displaystyle{ \overrightarrow{T_1} 3 \overset{0}{\rightarrow} 10 T_2 }[/math], где [math]\displaystyle{ \overrightarrow{T_1} }[/math] и [math]\displaystyle{ \overrightarrow{T_2} }[/math] - деревья, изображённые на рис. 2.20 и 2.21.

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

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


[math]\displaystyle{ P_2(\overrightarrow{T_1}) = [a_1, a_2, ... , a_k, c, a_{k+2}, ..., a_{n-1}] }[/math]

и среди чисел [math]\displaystyle{ a_{k+2}, a_{k+3}, a_{n-1} }[/math] нет числа c, то

[math]\displaystyle{ P_2(\overrightarrow{T_1})\stackrel{*}{c}P_2(\overrightarrow{T_2}) = [a_1, a_2, ... , a_k, P_2(\overrightarrow{T_2}),c, a_{k+2}, ..., a_{n-1}] }[/math].

Справедливы следующие соотношения, связывающие операции над деревьями и кодами Прюфера:

если [math]\displaystyle{ T_1 \lt T_2 }[/math], то

[math]\displaystyle{ P_2({T_1}a \overset{0}{\rightarrow} bT_2) = [P_2(\overset{a}{\underset{b}{\downarrow}}T_1),b, P_2(T_2)]; }[/math]

если [math]\displaystyle{ T_1 \gt T_2 }[/math], то необходимо рассматривать дерево [math]\displaystyle{ T_1b \overset{0}{\rightarrow} aT_2 }[/math], и всё сводится к предыдущему случаю;

если [math]\displaystyle{ \overrightarrow{T_1} \lt \overrightarrow{T_2} }[/math], то

[math]\displaystyle{ P_2({T_1}a \overset{0}{\rightarrow} bT_2) = [P_2(\overset{a}{\underset{b}{\downarrow}}\overrightarrow{T_1}),\stackrel{*}{c}, P_2(\overrightarrow{T_2})] }[/math],

где [math]\displaystyle{ c }[/math] - непосредственный предок вершины [math]\displaystyle{ a }[/math] в дереве [math]\displaystyle{ \overrightarrow{T_1} }[/math]


если [math]\displaystyle{ \overrightarrow{T_1} \gt \overrightarrow{T_2} }[/math], то

[math]\displaystyle{ P_2({T_1}a \overset{0}{\rightarrow} bT_2) = [P_2(\overrightarrow{T_2}), P_2(\overset{a}{\underset{b}{\downarrow}}\overrightarrow{T_1})] }[/math],