Аноним

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

Материал из WEGA

Коды Прюфера (посмотреть исходный код)

Версия от 18:55, 11 мая 2023

453 байта убрано ,  11 мая 2023
нет описания правки
Нет описания правки
Нет описания правки
 
(не показаны 23 промежуточные версии 2 участников)
Строка 1: Строка 1:
''' Код Прюфера''' - Представление с помощью списка рёбер и кода Прюфера.
Пусть 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> называемую '''кодом Прюфера''', по следующему правилу:
Дерево при этом способе задаётся перечислением пар <math><\nu_i, \nu_j></math> или троек <math><\nu_i, \nu_j, u_k></math>, если дополнительно нужна нумерация рёбер. Характер связей в списке определяется исходя из условий задачи. Например, для дерева T(см.рис X1) имеем


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


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


<math>P_2(T)</math> = [2, 5, 5, 5, 6, 6, 10, 9, 10, 11, 13, 15, 15, 10, 13, 13, 13].
<math>P_2(T) = [4, 4, 4, 5, 5, 7, 7].</math>
 
<изображение>
 
Распаковка кода  Прюфера осуществляется следующим образом:
 
'''функ''' РАСПАКОВКА (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>;
[[Файл:Priifer.mp4|360 px]]


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>;
    '''функ''' РАСПАКОВКА (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''
    '''всё'''


6.\quad\quad <math>B:=B-\{b\}</math>
[[Файл:Priifer decode.mp4|360 px]]
 
всё;
 
7. \quad возврат T
 
всё


В случае корневого ордерева процедуры построения кода Прюфера и его распаковки аналогичны. Необходимо только на последнем месте в <math>A</math> указывать корневую вершину и при распаковке кода <math>A</math> исключать номер этой вершины из множества <math>B</math>.
В случае корневого ордерева процедуры построения кода Прюфера и его распаковки аналогичны. Необходимо только на последнем месте в <math>A</math> указывать корневую вершину и при распаковке кода <math>A</math> исключать номер этой вершины из множества <math>B</math>.
Строка 66: Строка 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 была корневой).
Строка 73: Строка 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> -операция вставки кода Прюфера; если  
Строка 92: Строка 74:
если <math>T_1 > T_2</math>, то необходимо рассматривать дерево <math>T_1b \overset{0}{\rightarrow} aT_2</math>, и всё сводится к предыдущему случаю;
если <math>T_1 > T_2</math>, то необходимо рассматривать дерево <math>T_1b \overset{0}{\rightarrow} aT_2</math>, и всё сводится к предыдущему случаю;


если <math>\overrightarrow{T_1} > \overrightarrow{T_2}</math>, то
если <math>\overrightarrow{T_1} < \overrightarrow{T_2}</math>, то


: <math>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>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>,  
Строка 103: Строка 85:
: <math>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>,  
: <math>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>,  


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

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/12393...14997