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

Версия от 10:28, 30 мая 2017

Код Прюфера - Представление с помощью списка рёбер и кода Прюфера. Дерево при этом способе задаётся перечислением пар $< ν_{i}, ν_{j} >$ или троек $< ν_{i}, ν_{j}, u_{k} >$ , если дополнительно нужна нумерация рёбер. Характер связей в списке определяется исходя из условий задачи. Например, для дерева T(см.рис X1) имеем

$T = {< 1, 4 >, < 2, 4 >, < 3, 4 >, < 4, 5 >, < 5, 6 >, < 5, 7 >, < 7, 8 >, < 7, 9 >}$

Пусть T - дерево с множеством вершин ${ν_{1}, ν_{2}, . . ., ν_{n}}$ . Будем считать, что номер вершины $ν_{i}$ равен $i$ . Сопоставим дереву T последовательность $[a_{1}, a_{2}, . . ., a_{n - 2}]$ называемую кодом Прюфера, по следующему правилу:

   функ КОД_ПРЮФЕРА(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 (рис.) код Прюфера имеет вид:

$P_{2} (T)$ = [2, 5, 5, 2, 1, 3, 3].

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

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

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

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

Будем считать, что вершины двух разных деревьев нумеруются различными числами, причём номера одного дерева всегда больше или меньше любого номера другого. Это требование часто выполняется в практических реализациях, т.к для вершин каждого дерева обычно отводят последовательные массивы номеров ячеек памяти. Если все номера дерева $T_{1}$ (или ориентированного дерева $\vec{T_{1}}$ ) меньше всех номерова дерева $T_{2}$ (или $\vec{T_{2}}$ ) то пишут $T_{1}$ < $T_{2}$ (или $\vec{T_{1}}$ < $\vec{T_{2}}$ ).

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

$\overset{a}{\underset{b}{↓}}$ - операция замены номера a вершины T на номер b;

$a \overset{0}{\to} b$ - операция склеивания двух деревьев по вершинам a и b, т.е. дерево $T_{1} a \overset{0}{\to} b T_{2}$ получается из $T_{2}$ и $T_{1}$ отождествлением вершин a из $T_{1}$ b из $T_{2}$ и присвоением склеенной вершине номера b (при склеивании ордеревьев добавляется требование, чтобы вершина b была корневой).

На рис 2.22 представлен результат выполнения операции $\vec{T_{1}} 3 \overset{0}{\to} 10 T_{2}$ , где $\vec{T_{1}}$ и $\vec{T_{2}}$ - деревья, изображённые на рис. 2.20 и 2.21.

Рассмотрим некоторые вставки кода Прюфера: [] - операция формального отбрасывания квадратных скобок; определена на всех выражениях вида $[a_{1}, a_{2}, . . ., a_{n}], b, [b_{1}, b_{2}, . . ., b_{m}]$ и состоит в отбрасывании всех внутренних квадратных скобок и добавлении двух внешних;

$\overset{*}{c}$ -операция вставки кода Прюфера; если

P_{2} (\vec{T_{1}}) = [a_{1}, a_{2}, . . ., a_{k}, c, a_{k + 2}, . . ., a_{n - 1}]

и среди чисел $a_{k + 2}, a_{k + 3}, a_{n - 1}$ нет числа c, то

P_{2} (\vec{T_{1}}) \overset{*}{c} P_{2} (\vec{T_{2}}) = [a_{1}, a_{2}, . . ., a_{k}, P_{2} (\vec{T_{2}}), c, a_{k + 2}, . . ., a_{n - 1}]

.

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

если $T_{1} < T_{2}$ , то

P_{2} (T_{1} a \overset{0}{\to} b T_{2}) = [P_{2} (\overset{a}{\underset{b}{↓}} T_{1}), b, P_{2} (T_{2})];

если $T_{1} > T_{2}$ , то необходимо рассматривать дерево $T_{1} b \overset{0}{\to} a T_{2}$ , и всё сводится к предыдущему случаю;

если $\vec{T_{1}} < \vec{T_{2}}$ , то

P_{2} (T_{1} a \overset{0}{\to} b T_{2}) = [P_{2} (\overset{a}{\underset{b}{↓}} \vec{T_{1}}), \overset{*}{c}, P_{2} (\vec{T_{2}})]

,

где $c$ - непосредственный предок вершины $a$ в дереве $\vec{T_{1}}$

если $\vec{T_{1}} > \vec{T_{2}}$ , то

P_{2} (T_{1} a \overset{0}{\to} b T_{2}) = [P_{2} (\vec{T_{2}}), P_{2} (\overset{a}{\underset{b}{↓}} \vec{T_{1}})]

,

@@ Строка 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 дерево''') =
+     '''функ''' КОД_ПРЮФЕРА(''T'': '''дерево''') =
-.Пусть n - число вершин в ''T'', а ''A'' - Целочисленный вектор длины ''n''-2;
+.    Пусть n - число вершин в ''T'', а A - целочисленный вектор длины ''n''-2;
-.    B:= [1 ; n];
+.    B:= [1 : n];
-.    для ''i'' от ''1'' до ''n-1'' цикл
+.    '''для''' ''i'' '''от''' ''1'' '''до''' ''n-2'' '''цикл'''
 .        b:=min{k ∈ B; k - номер висячей вершины};
 .        A[i]:= номер вершины, смежной вершине с номером b;
 .        B:=B-{b};
 .        Удалить из ''T'' вершину с номером b
-           всё
+           '''всё'''
-     возврат A
+     '''возврат''' A
-     всё
+     '''всё'''
 Рассмотрим седующий пример. Для дерева ''T'' (рис.) код Прюфера имеет вид:
@@ Строка 27: / Строка 27: @@
 Распаковка кода  Прюфера осуществляется следующим образом:
-     '''функ''' РАСПАКОВКА (A: ''код'')=
+     '''функ''' РАСПАКОВКА (A: '''код''')=
-.    Пусть ''T'' состоит из вершин <math>\{\nu_1, \nu_2, ... , \nu_n\}</math> таких, что номер вершины <math>\nu_i</math> равен <math>i</math>, где n - длина кода A плюс 2;
+.    Пусть ''T'' состоит из вершин <math>\{\nu_1, \nu_2, ... , \nu_n\}</math> таких, что номер вершины <math>\nu_i</math> равен <math>i</math>,где n - длина кода A плюс 2;
-.     B: = [1 ; n];
+.    B: = [1 : n];
-.     для i от n+1 цикл
+.    '''для''' i '''от''' 1 '''до''' n+1 '''цикл'''
 .        b:=min{k ∈ B ; k <math>\neq</math> A[j] для любого j <math>\geq</math> i};
 .        В <math>T</math> добавить ребро, соединяющее вершины с номерами <math>b</math> и <math>A[i]</math>;
 .        B:=B-{b}
-           всё;
+          '''всё;'''
-.     возврат T
+.    '''возврат''' ''T''
      всё

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

Версия от 10:28, 30 мая 2017

Навигация

Поиск