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