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