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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Количество помеченных деревьев.)
Строка 8: Строка 8:
 
== Количество помеченных деревьев. ==
 
== Количество помеченных деревьев. ==
 
{{Теорема
 
{{Теорема
|author=Формула Кэли;
+
|author=Формула Кэли
 
|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>.
 
|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>.
 
|proof=
 
|proof=

Версия 21:54, 8 октября 2010

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

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


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

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

Доказательство 1. С помощью кодов Прюфера.

Доказательство 2. С помощью матрицы Кирхгофа для полного графа на [math]n[/math] на вершинах.
[math]\triangleleft[/math]