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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 16 промежуточных версий 6 участников)
Строка 1: Строка 1:
== Помеченное дерево ==
 
{{Определение
 
|definition=
 
Помеченное дерево порядка n - дерево порядка <math>n</math>, вершинам которого взаимно однозначно соответствуют числа от 1 до n.
 
}}
 
 
== Количество помеченных деревьев ==
 
 
{{Теорема
 
{{Теорема
 
|author=Формула Кэли
 
|author=Формула Кэли
 
|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>.
 
|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>.
 
|proof=
 
|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> вершинах. Число помеченных деревьев порядка <tex>n</tex>, очевидно, равно числу остовов в полном графе <tex>K_n</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 Дискретная математика: Алгоритмы. Формула Кэли
+
*[[Матрица Кирхгофа]]
 +
*[[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
 +
*[[Связь матрицы Кирхгофа и матрицы инцидентности]]
 +
*[[Коды Прюфера]]
 +
 
 +
== Источники информации==
 +
*[http://rain.ifmo.ru/cat/view.php/theory/graph-general/cayley-2008 Дискретная математика: Алгоритмы. Формула Кэли]
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Остовные деревья ]]
 +
[[Категория: Свойства остовных деревьев ]]
 +
[[Категория: Удалить]]

Текущая версия на 19:35, 4 сентября 2022

Теорема (Формула Кэли):
Число помеченных деревьев порядка [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]

См. также

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