Аноним

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

Материал из 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.    B:= [1 ; n];
     2.    B:= [1 : n];
     3.    для ''i'' от ''1'' до ''n-1'' цикл
     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
     всё
     '''всё'''


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


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