Коды Прюфера: различия между версиями
Перейти к навигации
Перейти к поиску
ALEXM (обсуждение | вклад) Нет описания правки |
ALEXM (обсуждение | вклад) Нет описания правки |
||
| Строка 12: | Строка 12: | ||
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'' вершину с номером A[i] | 7. Удалить из ''T'' вершину с номером A[i] | ||
всё | всё | ||
| Строка 20: | Строка 20: | ||
Рассмотрим седующий пример. Для дерева ''T'' (рис.) код Прюфера имеет вид: | Рассмотрим седующий пример. Для дерева ''T'' (рис.) код Прюфера имеет вид: | ||
<math>P_2(T)</math> = [2, 5, 5, | <math>P_2(T)</math> = [2, 5, 5, 2, 1, 3, 3, 9]. | ||
[[Файл:Prufer 1.gif|200px]] | |||
Распаковка кода Прюфера осуществляется следующим образом: | Распаковка кода Прюфера осуществляется следующим образом: | ||
| Строка 30: | Строка 31: | ||
2. B: = [1 ; n]; | 2. B: = [1 ; n]; | ||
3. для i от n+1 цикл | 3. для i от 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 | ||