Изменения

Перейти к: навигация, поиск

Коды Прюфера

13 байт убрано, 19:23, 11 ноября 2015
Коды Прюфера
== Коды Прюфера ==
Кодирование Прюфера переводит [[Количество помеченных деревьев#Помеченное дерево|помеченные деревья порядка <tex>n</tex>]] в последовательность чисел от <tex>1</tex> до <tex>n</tex> по алгоритму:<br> Пока количество вершин больше двух {: 1. # Выбирается лист <tex>v</tex> с минимальным номером. 2. # В код Прюфера добавляется номер вершины, смежной с <tex>v</tex>. 3. # Вершина <tex>v</tex> и инцидентное ей ребро удаляются из дерева. }<br>
Полученная последовательность называется '''кодом Прюфера''' для заданного дерева.

Навигация