Изменения

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

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

677 байт добавлено, 15:45, 13 июня 2020
м
Mark for delete. New page: Подсчет деревьев
== Помеченное дерево. ==
{{Определение
|definition=
Помеченное дерево порядка n - дерево порядка <math>n</math>, вершинам которого взаимно однозначно соответствуют числа от 1 до n.
}}
 
 
== Количество помеченных деревьев. ==
{{Теорема
|author=Формула Кэли
|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>.
|proof=
''Доказательство 1.'' Так как между помеченными деревьями порядка <tex>n</tex> и последовательностями длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> существует биекция, <br> то <tex>|</tex>множество помеченных деревьев<tex>|</tex> = <tex>|</tex>множество последовательностей длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex><tex>|</tex> = <tex>n^{n - 2}</tex>Можно доказать формулу двумя способами.
''Доказательство Первый способ.''  Так как между помеченными деревьями порядка <tex>n</tex> и последовательностями длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n</tex> существует биекция ([[Коды Прюфера|Код Прюфера]]), то количество помеченных деревьев совпадает с количеством последовательностей длины <tex>n - 2</tex> из чисел от <tex>1</tex> до <tex>n = n^{n - 2}</tex>. ''Второй способ.'' С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> на вершинах. Число помеченных деревьев порядка <tex>n</tex>, очевидно, равно числу остовов в полном графе <tex>K_n</tex>, которое есть <tex>n^{n-2}</tex> по следствию теоремы Кирхгофа.
}}
== См. также ==*[[Матрица Кирхгофа]]*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]*[[Связь матрицы Кирхгофа и матрицы инцидентности]]* [[Коды Прюфера]] == Источники информации==*[http://rain.ifmo.ru/cat/view.php/theory/graph-general/cayley-2008 Дискретная математика: Алгоритмы. Формула Кэли] [[Категория: Алгоритмы и структуры данных]][[Категория: Остовные деревья ]][[Категория: Свойства остовных деревьев ]][[Категория: Удалить]]
436
правок

Навигация