Количество помеченных деревьв — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
| (не показаны 2 промежуточные версии 2 участников) | |||
| Строка 15: | Строка 15: | ||
''Доказательство 2.'' С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> на вершинах. | ''Доказательство 2.'' С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> на вершинах. | ||
}} | }} | ||
| + | |||
| + | [[Категория: Удалить]] | ||
Текущая версия на 19:05, 4 сентября 2022
Помеченное дерево.
| Определение: |
| Помеченное дерево порядка n - дерево порядка , вершинам которого взаимно однозначно соответствуют числа от 1 до n. |
Количество помеченных деревьев.
| Теорема (Формула Кэли): |
Число помеченных деревьев порядка равно . |
| Доказательство: |
|
Доказательство 1. С помощью кодов Прюфера.
|
