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

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

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

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

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

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

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

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

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

@@ Строка 9: / Строка 9: @@
 {{Теорема
 |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> на вершинах.
+''Доказательство 2.'' С помощью матрицы Кирхгофа для полного графа на <tex>n</tex> на вершинах.
 }}