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

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


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


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


'''функ''' РАСПАКОВКА (A: ''код'')=
    '''функ''' РАСПАКОВКА (A: ''код'')=
 
1.\quad  Пусть ''T'' состоит из вершин <math>\{\nu_1, \nu_2, ... , \nu_n)\}</math> таких, что номер вершины <math>\nu_i</math> равен <math>i</math>, где n - длина кода A плюс 2;
 
2.\quad <math>B: = [1 \; n]</math>;
 
3.\quad для <math>i</math> от <math>n+1</math> цикл
 
4.\quad\quad b:=<math>min\{k \in B \; k \neq A[j]</math> для любого <math>j \geq i\}</math>;
 
5.\quad\quad В <math>T</math> добавить ребро, соединяющее вершины с номерами <math>b</math> и <math>A[i]</math>;
 
6.\quad\quad <math>B:=B-\{b\}</math>
 
всё;
 
7. \quad возврат T


всё
    1.    Пусть ''T'' состоит из вершин <math>\{\nu_1, \nu_2, ... , \nu_n)\}</math> таких, что номер вершины <math>\nu_i</math> равен <math>i</math>, где n - длина кода A плюс 2;
    2.    <math>B: = [1 \; n]</math>;
    3.    для <math>i</math> от <math>n+1</math> цикл
    4.        b:=<math>min\{k \in B \; k \neq A[j]</math> для любого <math>j \geq i\}</math>;
    5.        В <math>T</math> добавить ребро, соединяющее вершины с номерами <math>b</math> и <math>A[i]</math>;
    6.        <math>B:=B-\{b\}</math>
          всё;
    7.    возврат T
    всё


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

Версия от 11:39, 16 мая 2017

Код Прюфера - Представление с помощью списка рёбер и кода Прюфера. Дерево при этом способе задаётся перечислением пар [math]\displaystyle{ \lt \nu_i, \nu_j\gt }[/math] или троек [math]\displaystyle{ \lt \nu_i, \nu_j, u_k\gt }[/math], если дополнительно нужна нумерация рёбер. Характер связей в списке определяется исходя из условий задачи. Например, для дерева T(см.рис X1) имеем

[math]\displaystyle{ T = \{\lt 1, 4\gt , \lt 2, 4\gt , \lt 3,4\gt ,\lt 4,5\gt , \lt 5,6\gt , \lt 5,7\gt , \lt 7,8\gt ,\lt 7,9\gt \} }[/math]

Пусть 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.    [math]\displaystyle{ B:= [1 \; n] }[/math];
   3.    для i от 1 до n-1 цикл
   4.        [math]\displaystyle{ b:=min\{k \in B; k }[/math] - номер висячей вершины[math]\displaystyle{ \} }[/math];
   5.        A[i]:= номер вершины, смежной вершине с номером [math]\displaystyle{ b }[/math];
   6.        B:= B-{b};
   7.        Удалить из T вершину с номером [math]\displaystyle{ A[i] }[/math]
         всё
   8     возврат A
   всё

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

[math]\displaystyle{ P_2(T) }[/math] = [2, 5, 5, 5, 6, 6, 10, 9, 10, 11, 13, 15, 15, 10, 13, 13, 13].

<изображение>

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

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

[Категория: Обработка и визуализация деревьев]