47
правок
Коды Прюфера: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
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] | ||
всё | всё | ||
| Строка 28: | Строка 28: | ||
'''функ''' РАСПАКОВКА (A: ''код'')= | '''функ''' РАСПАКОВКА (A: ''код'')= | ||
1. Пусть ''T'' состоит из вершин <math>\{\nu_1, \nu_2, ... , \nu_n | 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 от 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 | ||