Количество помеченных деревьв — различия между версиями
| Строка 12: | Строка 12: | ||
|proof= | |proof= | ||
''Доказательство 1.'' С помощью [[Коды Прюфера|кодов Прюфера]]. | ''Доказательство 1.'' С помощью [[Коды Прюфера|кодов Прюфера]]. | ||
| + | |||
''Доказательство 2.'' С помощью матрицы Кирхгофа для полного графа на <tex>n</tex> на вершинах. | ''Доказательство 2.'' С помощью матрицы Кирхгофа для полного графа на <tex>n</tex> на вершинах. | ||
}} | }} | ||
Версия 21:42, 8 октября 2010
Помеченное дерево.
| Определение: |
| Помеченное дерево порядка n - дерево порядка , вершинам которого взаимно однозначно соответствуют числа от 1 до n. |
Количество помеченных деревьев.
| Теорема (Формула Кэли;): |
Число помеченных деревьев порядка равно . |
| Доказательство: |
|
Доказательство 1. С помощью кодов Прюфера. Доказательство 2. С помощью матрицы Кирхгофа для полного графа на на вершинах. |
