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