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