Изменения

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

Коды Прюфера

1 байт убрано, 22:10, 8 октября 2010
Коды Прюфера.
<br>
Пусть у нас есть последовательность: <tex>A = [a_1, a_2, ..., a_{n - 2}].</tex>
Выберем минимальное число <tex>v</tex> не лежащее в A. Это означает, что <tex>v</tex> - вершина, которую мы удалили первой, а, значит, это лист. Соединяем <tex>v</tex> и <tex>a_1</tex> ребром. Выкинем из последовательности <tex>A</tex> - <tex>a_1</tex>. Далее будем перенумеровывать вершины - , то есть - <tex>\forall i : a_i > v</tex> выполняем <tex>a_i = a_i - 1</tex>. А теперь мы можем применить предположение индукции.
}}
Анонимный участник

Навигация