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

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
Строка 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>.
47

правок

Навигация