Количество помеченных деревьев — различия между версиями
Berkut (обсуждение | вклад) |
Cuciev (обсуждение | вклад) м (Mark for delete. New page: Подсчет деревьев) |
||
| (не показано 6 промежуточных версий 3 участников) | |||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{{Теорема | {{Теорема | ||
|author=Формула Кэли | |author=Формула Кэли | ||
|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>. | |statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>. | ||
|proof= | |proof= | ||
| − | Можно доказать формулу двумя способами | + | Можно доказать формулу двумя способами. |
| − | + | ||
| − | + | ''Первый способ.'' | |
| + | |||
| + | Так как между помеченными деревьями порядка <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 Дискретная математика: Алгоритмы. Формула Кэли] | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Остовные деревья ]] | [[Категория: Остовные деревья ]] | ||
| + | [[Категория: Свойства остовных деревьев ]] | ||
| + | [[Категория: Удалить]] | ||
Версия 15:45, 13 июня 2020
| Теорема (Формула Кэли): |
Число помеченных деревьев порядка равно . |
| Доказательство: |
|
Можно доказать формулу двумя способами. Первый способ. Так как между помеченными деревьями порядка и последовательностями длины из чисел от до существует биекция (Код Прюфера), то количество помеченных деревьев совпадает с количеством последовательностей длины из чисел от до . Второй способ. С помощью матрицы Кирхгофа для полного графа на вершинах. Число помеченных деревьев порядка , очевидно, равно числу остовов в полном графе , которое есть по следствию теоремы Кирхгофа. |
См. также
- Матрица Кирхгофа
- Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
- Связь матрицы Кирхгофа и матрицы инцидентности
- Коды Прюфера
