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