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

Версия 15:44, 13 июня 2020

Определение:

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

Теорема (Формула Кэли):

Число помеченных деревьев порядка равно .

Доказательство:

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

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

@@ Строка 8: / Строка 8: @@
 == Количество помеченных деревьев. ==
 {{Теорема
-|author=Формула Кэли;
+|author=Формула Кэли
-|statement=Число помеченных деревьев порядка <math>n</math> равно <math>n^{n - 2}</math>.
+|statement=Число помеченных деревьев порядка <tex>n</tex> равно <tex>n^{n - 2}</tex>.
 |proof=
-''Доказательство 1.'' С помощью [[кодов Прюфера]].
+''Доказательство 1.'' С помощью [[Коды Прюфера|кодов Прюфера]].
-''Доказательство 2.'' С помощью матрицы Кирхгофа для полного графа на <math>n</math> на вершинах.
+<br>
+''Доказательство 2.'' С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> на вершинах.
 }}
+[[Категория: Удалить]]