Изменения

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

Коды Прюфера

17 байт убрано, 21:56, 8 октября 2010
Нет описания правки
Кодирование Прюфера задаёт биекцию между множествами помеченных деревьев порядка <math>n</math> и последовательностями длиной <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex>
|proof=
<li>1. Каждому помеченному дереву соотвествует последовательность и только одна - Верно по построению кода.</li><li>2. Каждой последовательности соотвествует помеченное дерево и только одно - Верно по предыдущей лемме, т.к. восстанавливали мы однозначно.</li>
}}
Следствием из этой теоремы является [[Количество помеченных деревьев|теорема Кэли]].
Анонимный участник

Навигация