Аноним

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

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
Строка 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, 5, 6, 6, 10, 9, 10, 11, 13, 15, 15, 10, 13, 13, 13].
<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
47

правок