Количество помеченных деревьев — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Mark for delete. New page: Подсчет деревьев)
(не показаны 2 промежуточные версии 1 участника)
Строка 1: Строка 1:
== Количество помеченных деревьев ==
 
 
{{Теорема
 
{{Теорема
 
|author=Формула Кэли
 
|author=Формула Кэли
Строка 21: Строка 20:
  
 
== Источники информации==
 
== Источники информации==
# [http://rain.ifmo.ru/cat/view.php/theory/graph-general/cayley-2008 Дискретная математика: Алгоритмы. Формула Кэли]
+
*[http://rain.ifmo.ru/cat/view.php/theory/graph-general/cayley-2008 Дискретная математика: Алгоритмы. Формула Кэли]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Остовные деревья ]]
 
[[Категория: Остовные деревья ]]
 
[[Категория: Свойства остовных деревьев ]]
 
[[Категория: Свойства остовных деревьев ]]
 +
[[Категория: Удалить]]

Версия 15:45, 13 июня 2020

Теорема (Формула Кэли):
Число помеченных деревьев порядка [math]n[/math] равно [math]n^{n - 2}[/math].
Доказательство:
[math]\triangleright[/math]

Можно доказать формулу двумя способами.

Первый способ.

Так как между помеченными деревьями порядка [math]n[/math] и последовательностями длины [math]n - 2[/math] из чисел от [math]1[/math] до [math]n[/math] существует биекция (Код Прюфера), то количество помеченных деревьев совпадает с количеством последовательностей длины [math]n - 2[/math] из чисел от [math]1[/math] до [math]n = n^{n - 2}[/math].

Второй способ.

С помощью матрицы Кирхгофа для полного графа на [math]n[/math] вершинах. Число помеченных деревьев порядка [math]n[/math], очевидно, равно числу остовов в полном графе [math]K_n[/math], которое есть [math]n^{n-2}[/math] по следствию теоремы Кирхгофа.
[math]\triangleleft[/math]

См. также

Источники информации