Количество помеченных деревьв — различия между версиями
(Новая страница: «== Помеченное дерево. == {{Определение |definition= Помеченное дерево порядка n - дерево порпядка <ma…») |
|||
| Строка 2: | Строка 2: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | Помеченное дерево порядка n - дерево | + | Помеченное дерево порядка n - дерево порядка <math>n</math>, вершинам которого взаимно однозначно соответствуют числа от 1 до n. |
}} | }} | ||
| Строка 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:38, 8 октября 2010
Помеченное дерево.
| Определение: |
| Помеченное дерево порядка n - дерево порядка , вершинам которого взаимно однозначно соответствуют числа от 1 до n. |
Количество помеченных деревьев.
| Теорема (Формула Кэли;): |
Число помеченных деревьев порядка равно . |
| Доказательство: |
|
Доказательство 1. С помощью кодов Прюфера. Доказательство 2. С помощью матрицы Кирхгофа для полного графа на на вершинах. |
