47
правок
Коды Прюфера: различия между версиями
Материал из WEGA
нет описания правки
ALEXM (обсуждение | вклад) Нет описания правки |
ALEXM (обсуждение | вклад) Нет описания правки |
||
| Строка 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; | ||
\ | 2. <math>B:= [1 \; n]</math>; | ||
3. для ''i'' от ''1'' до ''n-1'' цикл | |||
4. <math>b:=min\{k \in B; k</math> - номер висячей вершины<math>\}</math>; | |||
5. A[i]:= номер вершины, смежной вершине с номером <math>b</math>; | |||
6. B:= B-{b}; | |||
7. Удалить из ''T'' вершину с номером <math>A[i]</math> | |||
всё | |||
8 возврат A | |||
8 | |||
всё | всё | ||
