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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Количество помеченных деревьев.)
(Количество помеченных деревьев.)
Строка 13: Строка 13:
 
''Доказательство 1.'' С помощью [[Коды Прюфера|кодов Прюфера]].
 
''Доказательство 1.'' С помощью [[Коды Прюфера|кодов Прюфера]].
 
<br>
 
<br>
''Доказательство 2.'' С помощью [[Матрица Кирхгофа|матрицы Кирхгофа]] для полного графа на <tex>n</tex> на вершинах.
+
''Доказательство 2.'' С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> на вершинах.
 
}}
 
}}

Версия 21:46, 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]