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

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