436
правок
Изменения
м
Marked 'rooted' trees
= Помеченные деревья =
{{Теорема
|author=Формула Кэли|id=th_kelly|statement=Число помеченных деревьев порядка с <tex>n</tex> вершинами равно <tex>n^{n - 2}</tex>.
|proof=
Можно доказать формулу двумя способами.
''Второй способ.''
С помощью [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа |матрицы Кирхгофа]] для полного графа на <tex>n</tex> вершинах. Число помеченных деревьев порядка <tex>n</tex>, очевидно, равно числу остовов в полном графе <tex>K_n</tex>, которое есть <tex>n^{n-2}</tex> по следствию теоремы Кирхгофа.
}}
{{Утверждение
|statement=Число помеченных корневых деревьев с <tex>n</tex> вершинами есть <tex>T_n = n^{n - 2}</tex>.
|proof=
Данное утверждение является следствием [[#th_kelly|теоремы Кэли]].<br>
Обозначим через <tex>T_n</tex> число корневых помеченных деревьев с <tex>n</tex> вершинами, т.е. число помеченных деревьев, в которых одна из вершин выделена и названа корнем.<br>
Число корневых помеченных деревьев с <tex>n</tex> вершинами в <tex>n</tex> раз больше числа помеченных деревьев с <tex>n</tex> вершинами: в качестве корня можно выбрать любую из <tex>n</tex> различных вершин.
}}
