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

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
Строка 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'', а  
1.Пусть n - число вершин в ''T'', а ''A'' - Целочисленный вектор длины ''n''-2;


\quad\quad''A'' - Целочисленный вектор длины ''n''-2;
2.    <math>B:= [1 \; n]</math>;


2.\quad <math>B:= [1 \; n]</math>;
3.   для ''i'' от ''1'' до ''n-1'' цикл


3.\quad для ''i'' от ''1'' до ''n-1'' цикл
4.       <math>b:=min\{k \in B; k</math> - номер висячей вершины<math>\}</math>;


4.\quad\quad <math>b:=min\{k \in B; k</math> - номер висячей вершины<math>\}</math>;
5.       A[i]:= номер вершины, смежной вершине с номером <math>b</math>;


5.\quad\quad A[i]:= номер вершины, смежной вершине с номером <math>b</math>;
6.       B:= B-{b};


6.\quad\quad B:= B-\{b\};
7.       Удалить из ''T'' вершину с номером <math>A[i]</math>


7.\quad\quad Удалить из ''T'' вершину с номером <math>A[i]</math>
      всё


\quad\quad всё
8     возврат A
 
8 \quad возврат A


всё
всё
47

правок

Навигация