47
правок
Коды Прюфера: различия между версиями
Материал из WEGA
нет описания правки
ALEXM (обсуждение | вклад) Нет описания правки |
ALEXM (обсуждение | вклад) Нет описания правки |
||
| (не показано 10 промежуточных версий 2 участников) | |||
| Строка 4: | Строка 4: | ||
1. Пусть n - число вершин в ''T'', | 1. Пусть n - число вершин в ''T'', | ||
а A - целочисленный вектор длины ''n''-2; | а A - целочисленный вектор длины ''n''-2; | ||
2. B:= [1 : n]; | 2. B := [1 : n]; | ||
3. '''для''' ''i'' '''от''' ''1'' '''до''' ''n-2'' '''цикл''' | 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 | 8. '''возврат''' A | ||
'''всё''' | '''всё''' | ||
Рассмотрим седующий пример. Для дерева ''T'' (рис.) код Прюфера имеет вид: | Рассмотрим седующий пример. Для дерева ''T'' (рис.) код Прюфера имеет вид: | ||
<math>P_2(T) | <math>P_2(T) = [4, 4, 4, 5, 5, 7, 7].</math> | ||
[[Файл: | [[Файл:Priifer.mp4|360 px]] | ||
Распаковка кода Прюфера осуществляется следующим образом: | Распаковка кода Прюфера (или восстановление дерева по коду Прюфера) осуществляется следующим образом: | ||
'''функ''' РАСПАКОВКА (A: '''код''')= | '''функ''' РАСПАКОВКА (A: '''код''')= | ||
1. Пусть ''T'' состоит из вершин | 1. Пусть ''T'' состоит из вершин ''{ν₁, ν₂, ... , νₙ}'' таких, | ||
что номер вершины | что номер вершины ''νᵢ'' равен ''i'',где ''n'' - длина кода ''A'' плюс 2; | ||
2. B: = [1 : n]; | 2. '' B := [1 : n];'' | ||
3. '''для''' i '''от''' 1 '''до''' n | 3. '''для''' i '''от''' 1 '''до''' n-2 '''цикл''' | ||
4. b:=min{k ∈ B | 4. ''b'':=min{''k ∈ B'' : ''k ≠ A[j]'' для любого ''j ≥ i''}; | ||
5. В | 5. В ''T'' добавить ребро, соединяющее вершины | ||
с номерами ''b'' и ''A[i]''; | |||
6. B:=B-{b} | 6. ''B'' := ''B-{b}'' | ||
'''всё;''' | '''всё;''' | ||
7. '''возврат''' ''T'' | 7. В ''T'' добавить ребро, соединяющее вершины | ||
всё | с номерами, оставшимися в ''В''; | ||
8. '''возврат''' ''T'' | |||
'''всё''' | |||
[[Файл:Priifer decode.mp4|360 px]] | |||
В случае корневого ордерева процедуры построения кода Прюфера и его распаковки аналогичны. Необходимо только на последнем месте в <math>A</math> указывать корневую вершину и при распаковке кода <math>A</math> исключать номер этой вершины из множества <math>B</math>. | В случае корневого ордерева процедуры построения кода Прюфера и его распаковки аналогичны. Необходимо только на последнем месте в <math>A</math> указывать корневую вершину и при распаковке кода <math>A</math> исключать номер этой вершины из множества <math>B</math>. | ||
| Строка 44: | Строка 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 была корневой). | ||
| Строка 51: | Строка 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> -операция вставки кода Прюфера; если | ||
