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

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

Текущая версия на 19:05, 4 сентября 2022

Помеченное дерево.

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