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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Количество помеченных деревьев.)
м (Точки в конце заголовков… УБИВАТЬ!!!)
Строка 1: Строка 1:
== Помеченное дерево. ==
+
== Помеченное дерево ==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 5: Строка 5:
 
}}
 
}}
  
== Количество помеченных деревьев. ==
+
== Количество помеченных деревьев ==
 
{{Теорема
 
{{Теорема
 
|author=Формула Кэли
 
|author=Формула Кэли

Версия 03:19, 23 января 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]\triangleleft[/math]

См. также