Изменения

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

Количество помеченных деревьев

52 байта добавлено, 02:02, 9 октября 2010
Количество помеченных деревьев.
|proof=
Можно доказать формулу двумя способами:
* ''Доказательство 1.'' Так как между помеченными деревьями порядка <tex>n</tex> и последовательностями длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> существует биекция([[Коды Прюфера|Код Прюфера]]), <br> то количество помеченных деревьев = количетсво количество последовательностей длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> = <tex>n^{n - 2}</tex>.
* ''Доказательство 2.'' С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> на вершинах.
}}
Анонимный участник

Навигация