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

Материал из Викиконспекты
Версия от 22:17, 8 октября 2010; 192.168.0.2 (обсуждение) (Новая страница: «== Помеченное дерево. == {{Определение |definition= Помеченное дерево порядка n - дерево порядка <math…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Определение:
Помеченное дерево порядка 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]