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

Версия 05:08, 10 декабря 2011

Определение:

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

Теорема (Формула Кэли):

Число помеченных деревьев порядка равно .

Доказательство:

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

Доказательство 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] по следствию теоремы Кирхгофа.

@@ Строка 2: / Строка 2: @@
 {{Определение
 |definition=
-Помеченное [[Дерево, эквивалентные определения|дерево]] порядка <math>n</math> - дерево из <math>n</math> вершин, вершинам которого взаимно однозначно соответствуют числа от 1 до n.
+Помеченное дерево порядка <math>n</math> - [[Дерево, эквивалентные определения|дерево]] из <math>n</math> вершин, вершинам которого взаимно однозначно соответствуют числа от 1 до n.
 }}