Аноним

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

Материал из WEGA

Коды Прюфера (посмотреть исходный код)

Версия от 20:41, 30 мая 2017

639 байт убрано ,  30 мая 2017
нет описания правки
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
''' Код Прюфера''' - Представление с помощью списка рёбер и кода Прюфера.
Пусть 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> называемую '''кодом Прюфера''', по следующему правилу:
Дерево при этом способе задаётся перечислением пар <math><\nu_i, \nu_j></math> или троек <math><\nu_i, \nu_j, u_k></math>, если дополнительно нужна нумерация рёбер. Характер связей в списке определяется исходя из условий задачи. Например, для дерева T(см.рис X1) имеем
 
<math>T = \{<1, 4>, <2, 4>, <3,4>,<4,5>, <5,6>, <5,7>, <7,8>,<7,9>\}</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'': '''дерево''') =
Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/12443