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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 14: Строка 14:
 
* ''Доказательство 2.'' С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> вершинах. Число помеченных деревьев порядка <tex>n</tex>, очевидно, равно числу остовов в полном графе <tex>K_n</tex>, которое есть <tex>n^{n-2}</tex> по следствию теоремы Кирхгофа.
 
* ''Доказательство 2.'' С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <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 Дискретная математика: Алгоритмы. Формула Кэли

Версия 20:26, 8 декабря 2011

Помеченное дерево

Определение:
Помеченное дерево порядка n - дерево порядка [math]n[/math], вершинам которого взаимно однозначно соответствуют числа от 1 до n.


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

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

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

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

Источники

[http://rain.ifmo.ru/cat/view.php/theory/graph-general/cayley-2008 Дискретная математика: Алгоритмы. Формула Кэли