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

Материал из Викиконспекты
Версия от 15:44, 13 июня 2020; Cuciev (обсуждение | вклад) (Mark for delete. New page: Подсчет деревьев)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Помеченное дерево.[править]

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